Een recursieve functie is een functie die zichzelf opnieuw oproept, tot er aan één of meerdere voorwaarden wordt voldaan. Je kan het ook zien als een bijzondere soort herhaling: door zichzelf telkens opnieuw aan te roepen, ontstaat er immers een herhaling van dezelfde code.

Dat klinkt misschien vreemd: een functie die zichzelf oproept? Zou die dan niet eeuwig blijven doorlopen? Dat zou gebeuren als we niet oppassen. Daarom heeft elke recursieve functie twee delen.

Basisgeval en recursief geval

Elke goede recursieve functie bestaat uit twee delen:

Het basisgeval is dus onmisbaar: zonder basisgeval stopt de recursie nooit en loopt het programma vast.

Voorbeeld 1 — de som van alle getallen

Bekijk de functie SomGetallen. Ze berekent de som van alle gehele getallen van 0 tot en met een gegeven getal. Zo is SomGetallen(3) gelijk aan 3 + 2 + 1 + 0.

static int SomGetallen(int getalTot)
{
    int uitkomst;
    if (getalTot == 0)
    {
        uitkomst = 0;
    }
    else
    {
        uitkomst = getalTot + SomGetallen(getalTot - 1);
    }
    return uitkomst;
}

De functie heeft een if-statement dat controleert of de waarde van de parameter gelijk is aan 0:

• Is getalTot gelijk aan 0, dan is de uitkomst meteen 0. Dit is het basisgeval: de functie roept zichzelf niet meer op.
• In het andere geval is de uitkomst het getal zelf, opgeteld bij een nieuwe oproep van de functie met een waarde die net één kleiner is (SomGetallen(getalTot - 1)). Dit is het recursieve geval.

Telkens onderbreekt de functie zichzelf en wordt ze opnieuw opgeroepen met een iets kleinere waarde, tot het basisgeval bereikt is. Voor SomGetallen(3) gebeurt het volgende:

SomGetallen(3) = 3 + SomGetallen(2)
              = 3 + (2 + SomGetallen(1))
              = 3 + (2 + (1 + SomGetallen(0)))
              = 3 + (2 + (1 + 0))
              = 6

Voor kleine getallen verloopt dit probleemloos. Geef je een heel groot getal in (bijvoorbeeld 500000), dan stapelen er zo veel openstaande oproepen op dat het programma foutloopt (een stack overflow). Recursie werkt dus best op problemen die snel kleiner worden.

Voorbeeld 2 — printFun(3)

Een recursieve oproep heeft eigenlijk twee momenten: het stuk code vóór de recursieve oproep, en het stuk code erna. Het volgende voorbeeld maakt dat mooi zichtbaar.

static void printFun(int test)
{
    if (test >= 1)
    {
        Console.Write(test + " ");
        printFun(test - 1);
        Console.Write(test + " ");
    }
}

Roep je deze functie aan met printFun(3), dan drukt het programma als resultaat af:

3 2 1 1 2 3

Op het eerste zicht een vreemd resultaat. Stap voor stap gebeurt het volgende:

1. We starten met de initiële oproep printFun(3).
2. Omdat test gelijk is aan 3 en groter dan of gelijk aan 1, wordt eerst het getal 3 afgedrukt.
3. Vervolgens wordt de functie printFun opnieuw aangeroepen met test verminderd met 1, dus printFun(2).
4. Binnen printFun(2) wordt opnieuw het getal 2 afgedrukt, omdat test nog steeds groter is dan of gelijk aan 1.
5. Opnieuw wordt printFun opgeroepen met test - 1, wat resulteert in printFun(1).
6. Binnen printFun(1) wordt het getal 1 afgedrukt.
7. Nu wordt printFun opnieuw opgeroepen met test - 1, wat dit keer printFun(0) oplevert.
8. Aangezien test gelijk is aan 0, wordt het basisgeval bereikt en wordt de recursie gestopt.

Tot hier is dus 3 2 1 afgedrukt. Maar de functie is nog niet klaar: bij elke oproep moet immers ook het tweede Console.Write(test + " ") nog uitgevoerd worden. De openstaande oproepen worden nu, in omgekeerde volgorde, afgewerkt:

• De oproep van printFun(0) is voltooid en de controle keert terug naar de oproep van printFun(1) waar we gebleven waren.
• Nu wordt het tweede gedeelte van printFun(1) uitgevoerd, waarbij opnieuw het getal 1 wordt afgedrukt.
• Vervolgens wordt de functieoproep printFun(1) afgerond en de controle keert terug naar de oproep van printFun(2).
• Binnen printFun(2) wordt het tweede gedeelte uitgevoerd, waarbij opnieuw het getal 2 wordt afgedrukt.
• Daarna wordt de functieoproep printFun(2) afgerond en de controle keert terug naar de oproep van printFun(3).
• Binnen printFun(3) wordt het tweede gedeelte uitgevoerd, waarbij voor de laatste keer het getal 3 wordt afgedrukt.

Uiteindelijk zijn alle functieoproepen afgerond en zijn de getallen afgedrukt in zowel oplopende als aflopende volgorde, wat de uitvoer 3 2 1 1 2 3 verklaart.

Het stuk code vóór de recursieve oproep voert uit op de heenweg (van de grote naar de kleine waarde); het stuk code erna voert uit op de terugweg (van de kleine waarde terug naar de grote). Hou dat in het achterhoofd bij de oefeningen.

Onthoud

• Een recursieve functie roept zichzelf opnieuw op.
• Het basisgeval stopt de recursie (geen oproep meer). Vergeet het nooit.
• Het recursieve geval maakt het probleem kleiner en roept de functie opnieuw op.