Simpelt sagt så er det en funktion der gentagende gange kalder sig selv til en bestemt betingelse er opnået. Dette skaber en løkke. Denne teknik er særligt god i træstrukturer, søgning og sorterings algoritmer. I en rekursiv funktion er det vigtigt at man har en basistilstand der stopper rekursionen, så den ikke fortsætter i et uendeligt loop.

Lad os starte med et helt simpelt eksempel.

 
void setup() {
  tælNed(3); // Første kald til funktionen
}

void draw() {
}

void tælNed(int tæller) {
  print(tæller +" ");
  if (tæller > 0) { // basistilstanden der stopper rekursionen
    tælNed(tæller-1); //  tælNed() kalder sig selv med tæller -1.
  }
}

Hvad forventer vi at der vil ske når vi kører denne kode? Kopier koden ind i Processing og se hvad der sker.

At have et naturligt rekursivt problem betyder, at problemet i sig selv er defineret på en måde, der naturligt kan beskrives ved rekursion – altså hvor løsningen afhænger af løsningen på en mindre version af det samme problem.

Kendetegn ved naturligt rekursive problemer:

• Problemet kan opdeles i mindre delproblemer, som har samme struktur som det oprindelige problem.
• Der findes et eller flere enkle tilfælde, hvor løsningen er direkte kendt uden rekursion (basistilfælde).
• Problemet kan opdeles i mindre instanser, som gradvist nærmer sig basistilfældet.

Eksempler på naturligt rekursive problemer:

• Fibonacci-tal
• Fakultet (n!)
• Fraktaler
• Binær søgning

Både en for-løkke og rekursion bruges til at gentage en operation flere gange, de fungerer dog på forskellige måder, bliver brugt på forskellige anvendelsesområder og har forskellige konsekvenser for dit program.

En forløkke er en kontrolstruktur som tillader gentagelse af en bestemt kodeblok et bestemt antal gange. De er bygget op af tre komponenter: initialisering, betingelse og inkrement/dekrement. De er specielt nyttige hvis man på forhånd ved det nøjagtige antal iterationer der skal være.

Rekursion er, som beskrevet tidligere, når en funktion kalder sig selv inden for sin egen kode. Rekursion er rigtig god i situationer hvor problemet naturligt kan brydes ned i mindre subproblemer af samme type. Et godt eksempel på dette er beregningen af Fibonacci-tal, da hvert tal i Fibonacci-sekvensen er defineret som summen af de to foregående tal i sekvensen, med undtagelse af de to første tal 0 og 1 som er givet.

int fibonacci(int n) {
  if (n <= 1) {
    return n;  // Basistilfælde: Hvis n er 0 eller 1, returneres n simpelthen, da de første to Fibonacci-tal er 0 og 1.
  } else {
    return fibonacci(n - 1) + fibonacci(n - 2);  // Rekursivt tilfælde: Summen af de to forudgående Fibonacci-tal.
  }
}

For at illustrere, hvordan rekursive funktioner opererer, kan man anvende et rekursionstræ. Et rekursionstræ er en grafisk repræsentation, der viser de successive kald, en rekursiv funktion foretager, samt hvordan disse kald forgrener sig. Dette er særligt nyttigt for at forstå funktioner som beregning af f.eks. Fibonacci-tal eller fakultetsfunktioner. Billedet herunder viser et rekursionstræ for vores fibonacci funktion hvis n = 6. I dette træ repræsenterer hver node et funktionskald, og grenene viser de rekursive kald, der foretages. Bladene (de nederste noder) repræsenterer basistilfældene, hvor n er 0 eller 1. Ved at følge træet kan man se, hvordan funktionen nedbryder problemet i mindre dele, indtil den når basistilfældene, hvorefter resultaterne kombineres for at give det endelige resultat.

Rekursionstræer er effektive værktøjer til at visualisere og forstå flowet i rekursive funktioner, hvilket gør det lettere at følge med i, hvordan værdier beregnes gennem de forskellige kald.

Gå til opgaver