Recursie

Een Toren van Hanoi met 64 schijven verplaatsen kost 18 446 744 073 709 551 615 zetten; een recursieve functie beschrijft de oplossing in vier regels.

Een functie die zichzelf aanroept

Sommige problemen bevatten een kleinere kopie van zichzelf. De faculteit van 5, geschreven als 5!, is 5 × 4 × 3 × 2 × 1 = 120. Kijk opnieuw: het is 5 × (4 × 3 × 2 × 1), dus 5 × 4!. In het algemeen geldt n! = n × (n − 1)!, dus om een faculteit te berekenen kun je een kleinere faculteit berekenen en vermenigvuldigen. Een functie die een probleem oplost door zichzelf op een kleinere versie aan te roepen is recursief.

function factorial(n) {
  if (n <= 1) return 1;          // base case: stop here
  return n * factorial(n - 1);   // recursive case: a smaller problem
}
console.log(factorial(5)); // 120

Elke recursieve functie heeft twee delen nodig. Het basisgeval is invoer die klein genoeg is om direct te beantwoorden zonder nieuwe aanroep: hier is de faculteit van 1 gelijk aan 1. Het recursieve geval verkleint het probleem en roept de functie opnieuw aan. Elke aanroep moet dichter bij het basisgeval komen. Anders, bijvoorbeeld als je per ongeluk factorial(n + 1) schrijft, eindigen de aanroepen nooit.

De aanroepstapel

Hoe houdt de computer al die onafgemaakte aanroepen bij? Als factorial(5) wordt uitgevoerd, bereikt het 5 * factorial(4) en moet het wachten op het antwoord. De computer zet de wachtende aanroep op een stapel: wat er als laatste op komt, gaat er als eerste af. factorial(4) wacht op factorial(3), enzovoort tot factorial(1), dat meteen 1 teruggeeft. Dan wordt de stapel afgewikkeld: factorial(2) geeft 2 terug, factorial(3) geeft 6, factorial(4) geeft 24 en factorial(5) geeft 120.

De stapel heeft een beperkte omvang. Recursie die het basisgeval nooit bereikt, blijft aanroepen toevoegen totdat de ruimte op is en JavaScript met een fout stopt; in Chrome en Node.js is de melding "RangeError: Maximum call stack size exceeded". Door dezelfde beperking schrijf je heel diepe recursie, met honderdduizenden niveaus, beter als lus.

De Torens van Hanoi

De Torens van Hanoi is een puzzel die de Franse wiskundige Édouard Lucas in 1883 publiceerde. Er zijn drie pinnen en op de eerste ligt een stapel schijven van verschillende grootte, de grootste onderaan. Het doel is de hele stapel naar de derde pin te verplaatsen. Je mag maar één schijf tegelijk verplaatsen, alleen de bovenste van een pin, en nooit een grotere op een kleinere leggen.

Stap voor stap bedenken waar elke schijf heen moet wordt snel verwarrend. Recursief denken maakt het kort. Om n schijven van A naar C te verplaatsen: verplaats eerst de bovenste n − 1 schijven van A naar B, uit de weg. Verplaats dan de grootste van A naar C. Verplaats daarna de n − 1 schijven van B erop bij C. n − 1 schijven verplaatsen is dezelfde puzzel, één maat kleiner, en één schijf verplaatsen is het basisgeval. Voor 3 schijven geeft dit 7 zetten; in het lab zie je bij elke zet de stapel wachtende aanroepen.

function hanoi(n, from, to, via) {
  if (n === 0) return;
  hanoi(n - 1, from, via, to);
  console.log("disk " + n + ": " + from + " -> " + to);
  hanoi(n - 1, via, to, from);
}
hanoi(3, "A", "C", "B");  // 7 moves

Hoeveel zetten kosten n schijven? n schijven verplaatsen kost tweemaal het verplaatsen van n − 1 schijven plus één: M(n) = 2M(n − 1) + 1, met M(1) = 1. Dat geeft 1, 3, 7, 15, 31, dus M(n) = 2ⁿ − 1, en geen oplossing kan minder zetten gebruiken. Tien schijven kosten 1023 zetten. Vierenzestig schijven kosten 2⁶⁴ − 1 = 18 446 744 073 709 551 615 zetten; bij één zet per seconde is dat ongeveer 585 miljard jaar. Dit is de O(2ⁿ)-groei uit het vorige hoofdstuk.

Recursie, lussen en herhaald werk

Alles wat je met recursie schrijft, kun je schrijven met een lus en een eigen stapel. Eenvoudige gevallen zoals faculteiten zijn vaak duidelijker als lus. Recursie blinkt uit wanneer het probleem zelf een boomvorm heeft: een lijst splitsen in mergesort, mappen binnen mappen verkennen of een doolhof doorzoeken, het onderwerp van het laatste hoofdstuk. Een valkuil is herhaald werk. De Fibonacci-getallen 0, 1, 1, 2, 3, 5, 8, … volgen fib(n) = fib(n − 1) + fib(n − 2). Direct als recursie geschreven doet fib(10) = 55 in totaal 177 aanroepen, fib(20) doet er 21 891 en fib(30) 2 692 537, omdat dezelfde kleinere waarden steeds opnieuw worden berekend. Reeds gevonden antwoorden onthouden of met een lus van onderaf opbouwen voorkomt die verspilling.