Rekursion og stak

Lad os vende tilbage til funktioner og studere dem mere grundigt.

Vores første emne vil være rekursion.

Hvis du ikke er ny i programmering, så er det sandsynligvis kendt og du kan springe dette kapitel over.

Rekursion er et programmeringsmønster, som er nyttigt i situationer hvor en opgave kan opdeles i flere opgaver af samme type, men mere simple. Eller når en opgave kan formindskes til en enkel handling plus en mere simpel variant af samme opgave. Eller, som vi vil se snart, for at håndtere bestemte datastrukturer.

Når en funktion løser en opgave, kan den i processen kalde mange andre funktioner. En delmængde heraf er når en funktion kalder sig selv. Det kaldes rekursion.

To måder at tænke på

For noget simpelt at starte med – lad os skrive en funktion pow(x, n) som hæver x til en naturlig potens af n. Med andre ord, multiplicerer x med sig selv n gange.

pow(2, 2) = 4
pow(2, 3) = 8
pow(2, 4) = 16

Der er to måder at implementere det.

1. Iterativ tankegang: for-loopet:

   function pow(x, n) {
     let result = 1;
   
     // Gang resultatet med x n gange i loopet
     for (let i = 0; i < n; i++) {
       result *= x;
     }
   
     return result;
   }
   
   alert( pow(2, 3) ); // 8

2. Rekursiv tænkning: Simplificer opgaven og kald dig selv:

   function pow(x, n) {
     if (n == 1) {
       return x;
     } else {
       return x * pow(x, n - 1);
     }
   }
   
   alert( pow(2, 3) ); // 8

Bemærk hvordan den rekursive variant er grundiglæggende anderledes.

Når pow(x, n) kaldes splittes udførelsen til to forgreninger:

              if n==1  = x
             /
pow(x, n) =
             \
              else     = x * pow(x, n - 1)

1. Hvis n == 1, så er alt trivielt. Dette kaldes basen for rekursion, fordi den fordi den umiddelbart producerer det obviouse resultat: pow(x, 1) er lig med x.
2. Ellers kan vi repræsentere pow(x, n) som x * pow(x, n - 1). I matematik ville man skrive xn = x * xn-1. Dette kaldes et rekursivt trin: vi transformerer opgaven til en enkel handling (multiplication med x) og et mere simpelt kald af samme opgave (pow med lavere n). Næste trin forenkler det yderligere og yderligere indtil n når 1.

Vi kan også sige at pow kalder sig selv rekursivt indtil n == 1.

For eksempel, for at udregne pow(2, 4) vil den rekursive variant gøre disse trin:

1. pow(2, 4) = 2 * pow(2, 3)
2. pow(2, 3) = 2 * pow(2, 2)
3. pow(2, 2) = 2 * pow(2, 1)
4. pow(2, 1) = 2

så rekursionen reducerer et funktionskald til et mere simpelt, og så videre, indtil resultatet bliver åbenlyst.

function pow(x, n) {
  return (n == 1) ? x : (x * pow(x, n - 1));
}

Det maksimalt antal indlejrede kald (inklusive det første) kaldes rekursionsdybde. I vores tilfælde vil det være præcis n.

Den maksimale rekursionsdybde er begrænset af JavaScript-motoren. Vi kan stole på, at den er 10.000, nogle motorer tillader mere, men 100.000 er sandsynligvis uden for grænsen for de fleste af dem. Der er automatiske optimeringer, der hjælper med at optimere antallet af kald (“tail calls optimizations”), men de er ikke endnu understøttet overalt og virker kun i simple tilfælde.

Det begrænser anvendelsen af rekursion, men den forbliver stadig meget bred. Der er mange opgaver hvor den rekursive måde at tænke giver enklere kode der er nemmere at vedligeholde.

Eksekveringens kontekst og stak

Lad os undersøge hvordan rekursive kald fungerer. For det vil vi kigge under huden på funktioner.

Informationen om processen for eksekvering af en kørende funktion er gemt i dens eksekveringskontekst.

Eksekveringskonteksten er en intern datastruktur, der indeholder detaljer om eksekveringen af en funktion: hvor kontrolløbet er nu, de aktuelle variabler, værdien af this (vi bruger det ikke her) og andre interne detaljer.

Et funktionskald har præcis én eksekveringskontekst forbundet med det.

Når en funktion udfører et indlejret kald, sker følgende:

• Den nuværende funktion pauses.
• Den eksekveringskontekst, der er forbundet med den, huskes i en speciel datastruktur kaldet execution context stack.
• Det indlejrede kald udføres.
• Når det er færdigt, hentes den gamle eksekveringskontekst fra stakken og den ydre funktion genoptages fra hvor den stoppede.

Lad os se hvad der sker under kaldet pow(2, 3).

pow(2, 3)

I begyndelsen af kaldet pow(2, 3) vil eksekveringskonteksten gemme variablerne: x = 2, n = 3, og kontrolløbet er på linje 1 i funktionen.

Vi kan skitsere det som:

• Context: { x: 2, n: 3, at line 1 } pow(2, 3)

Det er her funktionen begynder at eksekvere. Betingelsen n == 1 er falsk, så flowet fortsætter til den anden gren af if:

function pow(x, n) {
  if (n == 1) {
    return x;
  } else {
    return x * pow(x, n - 1);
  }
}

alert( pow(2, 3) );

Variablene er de samme, men linjen ændres, så konteksten er nu:

• Context: { x: 2, n: 3, at line 5 } pow(2, 3)

For at udregne x * pow(x, n - 1), vi skal lave et indlejret kald af pow med nye argumenter pow(2, 2).

pow(2, 2)

For at udføre et indlejret kald, husker JavaScript den nuværende eksekveringskontekst i execution context stack.

Her kalder vi den samme funktion