Rekursion er ikke svært: en trinvis gennemgang af denne nyttige programmeringsteknik

Jeg vil sige dette lige uden for flagermusen. Kender du de begivenheder, der sker ved funktionsopkald? Ingen? Så det er her, vi starter.

Funktionskaldelse

Når vi kalder en funktion, placeres en udførelseskontekst på udførelsesstakken. Lad os nedbryde dette mere.

For det første, hvad er en stak?

En stak er en datastruktur, der fungerer på basis af "Last In, First Out". En genstand “skubbes” på en stak for at tilføje den, og en genstand “poppes” ud af stakken for at fjerne den.

Brug af en stak er en metode til at bestille bestemte operationer til udførelse.

Nu, tilbage til hvad er en eksekveringskontekst? En eksekveringskontekst dannes ved en funktionsopkald. Denne sammenhæng placerer sig på en udførelsesstak, en rækkefølge af operationer. Det element, der altid er først i denne stak, er den globale udførelseskontekst. Dernæst er enhver funktion oprettet sammenhæng.

Disse eksekveringskontekster har egenskaber, et aktiveringsobjekt og en "dette" binding. Den "denne" binding er en henvisning tilbage til denne eksekveringskontekst. Aktiveringsobjektet inkluderer: passerede parametre, erklærede variabler og funktionserklæringer.

Så hver gang vi placerer en ny kontekst på stakken, har vi normalt alt, hvad vi har brug for til at udføre kode.

Hvorfor siger jeg normalt ?

Med rekursion venter vi på returværdier, der kommer fra andre udførelsessammenhænge. Disse andre sammenhænge er højere op i stakken. Når det sidste element i stakken er færdig med udførelsen, genererer denne kontekst en returværdi. Denne returværdi overføres som en returværdi fra den rekursive sag til den næste vare. Denne udførelseskontekst poppes derefter ud af stakken.

Rekursion

Så hvad er rekursion?

En rekursiv funktion er en funktion, der kalder sig selv, indtil en "basistilstand" er sand, og udførelsen stopper.

Mens det er falsk, fortsætter vi med at placere eksekveringskontekster oven på stakken. Dette kan ske, indtil vi har et "stackoverløb". Et stakoverløb er, når vi løber tør for hukommelse for at holde emner i stakken.

Generelt har en rekursiv funktion mindst to dele: en basistilstand og mindst en rekursiv sag.

Lad os se på et klassisk eksempel.

Faktor

const factorial = function(num) { debugger; if (num === 0 || num === 1) { return 1 } else { return num * factorial(num - 1) }}
factorial(5)

Her forsøger vi at finde 5! (fem faktor). Faktorafunktionen er defineret som produktet af alle positive heltal mindre end eller lig med dets argument.

Den første betingelse siger: “hvis den passerede parameter er lig med 0 eller 1, forlader vi og returnerer 1”.

Dernæst siger den rekursive sag:

“Hvis parameteren ikke er 0 eller 1, vil vi videregive værdien af numgange returværdien for at kalde denne funktion igen med num-1som argument”.

Så hvis vi ringer factorial(0), returnerer funktionen 1 og rammer aldrig den rekursive sag.

Det samme gælder factorial(1).

Vi kan se, hvad der sker, hvis vi indsætter en fejlretningserklæring i koden og bruger devtools til at træde igennem den og se opkaldsstakken.

  1. Eksekveringsstakken placeres factorial()med 5, når argumentet blev bestået. Basissagen er falsk, så indtast den rekursive tilstand.
  2. Eksekveringsstakken placerer factorial()en anden gang med num-1= 4 som argument. Basissagen er falsk, indtast rekursiv tilstand.
  3. Eksekveringsstakken placerer factorial()en tredje gang med num-1(4–1) = 3 som argument. Basissagen er falsk, indtast rekursiv tilstand.
  4. Eksekveringsstakken placerer factorial()en fjerde gang med num-1(3–1) = 2 som argument. Basissagen er falsk, indtast rekursiv tilstand.
  5. Eksekveringsstakken placerer factorial()en femte gang med num-1(2–1) = 1 som argument. Nu er basissagen sand, så returner 1.

På dette tidspunkt har vi reduceret argumentet med et på hvert funktionsopkald, indtil vi når en betingelse for at returnere 1.

6. Herfra fuldføres den sidste udførelseskontekst,, num === 1så funktionen returnerer 1.

7. Herefter num === 2er returværdien 2. (1 × 2).

8. Derefter num === 3skal returværdien være 6, (2 × 3).

Indtil videre har vi 1 × 2 × 3.

9. Dernæst, num === 4(4 × 6). 24 er returværdien til den næste kontekst.

10. Endelig, num === 5(5 × 24), og vi har 120 som den endelige værdi.

Rekursion er ret pæn, ikke?

Vi kunne have gjort det samme med en for eller et stykke tid. Men brug af rekursion giver en elegant løsning, der er mere læselig.

Derfor bruger vi rekursive løsninger.

Mange gange er et problem opdelt i mindre dele mere effektivt. Opdeling af et problem i mindre dele hjælper med at erobre det. Derfor er rekursion en kløft-og-erobre tilgang til løsning af problemer.

  • Underproblemer er lettere at løse end det oprindelige problem
  • Løsninger på delproblemer kombineres for at løse det oprindelige problem

"Opdel-og-erobre" bruges oftest til at krydse eller søge datastrukturer såsom binære søgetræer, grafer og dynger. Det fungerer også for mange sorteringsalgoritmer, som quicksort og heapsort.

Lad os gennemgå følgende eksempler. Brug devtools til at få en konceptuel forståelse af, hvad der sker hvor og hvornår. Husk at bruge fejlfindingserklæringer og trin gennem hver proces.

Fibonacci

const fibonacci = function(num) { if (num <= 1) { return num } else { return fibonacci(num - 1) + fibonacci(num - 2) }}fibonacci(5);

Rekursive arrays

function flatten(arr) { var result = [] arr.forEach(function(element) { if (!Array.isArray(element)) { result.push(element) } else { result = result.concat(flatten(element)) } }) return result}
flatten([1, [2], [3, [[4]]]]);

Vender en streng om

function reverse(str) { if (str.length === 0) return '' return str[str.length - 1] + reverse(str.substr(0, str.length - 1))}
reverse('abcdefg');

Quicksort

function quickSort(arr, lo, hi) { if (lo === undefined) lo = 0 if (hi === undefined) hi = arr.length - 1
 if (lo 
    
      partition: ' + p) // sort subarrays quickSort(arr, lo, p - 1) quickSort(arr, p + 1, hi) } // for initial call, return a sorted array if (hi - lo === arr.length - 1) return arr}
    
function partition(arr, lo, hi) { // choose last element as pivot var pivot = arr[hi] // keep track of index to put pivot at var pivotLocation = lo // loop through subarray and if element <= pivot, place element before pivot for (var i = lo; i < hi; i++) { if (arr[i] <= pivot) { swap(arr, pivotLocation, i) pivotLocation++ } } swap(arr, pivotLocation, hi) return pivotLocation}
function swap(arr, index1, index2) { if (index1 === index2) return var temp = arr[index1] arr[index1] = arr[index2] arr[index2] = temp console.log('swapped' + arr[index1], arr[index2], +' in ', arr) return arr}
quickSort([1, 4, 3, 56, 9, 8, 7, 5])

Det er vigtigt at øve på rekursive teknikker. For indlejrede datastrukturer som træer, grafer og dynger er rekursion uvurderlig.

I en fremtidig artikel vil jeg diskutere optimering af haleopkald og memoization-teknikker, da de vedrører rekursion. Tak for læsningen!

Yderligere ressourcer

Wikipedia

Software Engineering

En anden god artikel

MIT åbent kursusudstyr