Har du nogensinde bare brug for at se kode i aktion? Det er godt at læse om, hvordan det fungerer, men kan du godt lide at se en opdeling af præcis, hvad der sker på trin 1, 2, 3 og 4? Også mig.
Jeg vil vise dig et eksempel på en rekursiv funktion i JavaScript og derefter guide dig gennem, hvordan den virker, med farverige biler og et søfart !
Hvad er rekursion
En funktion er rekursiv, når den:
- Kald sig selv.
- Har et basiscase, noget kode, der definerer, hvornår funktionen skal stoppe med at kalde sig selv. Ellers vil funktionen blive ved med at kalde sig selv uendeligt.
Kodeeksempel
Lad os sige, at vi har denne matrix, og vi vil have summen af dens værdier.
const array = [1,2,3,4];
For at få summen skal vi tilføje det første element i arrayet til næste element i arrayet og så videre.
function getSum(arr) {
return arr[0] + arr[1] + // etc.
}
// lol get some
Men der er bedre måder at opnå det på udover manuelt at angive hvert element i arrayet. En måde er med rekursion - at have selve funktionskaldet.
For at gøre funktionen rekursiv tilføjer vi det første element i arrayet til det resterende array efter det behandles af getSum-funktionen. Vi vil dække det i detaljer i næste afsnit.
function getSum(arr) {
return arr[0] + getSum(arr.slice(1)); // recursion
}
Og hvornår vil vi stoppe med at tilføje? Med andre ord, hvad skal vores base case være? Når vi kommer til det sidste element i arrayet.
const array = [1,2,3,4];
function getSum(arr) {
if (arr.length <= 1 ) return arr[0]; // base case
return arr[0] + getSum(arr.slice(1)); // recursion
}
getSum(array);
Så der er vores rekursive funktion. Du kan prøve en demo her.
Det ser måske ud til, at vi ikke har brug for en basiscase, da der ikke er noget at behandle efter afslutningen af arrayet, men du vil få en sjov maksimal opkaldsstack overskredet fejl, hvis den ikke er inkluderet.
Hvad sker der nu, når getSum-funktionen kalder sig selv?
Illustreret Play-by-Play
Første gang getSum kører, denne linje:
return arr[0] + getSum(arr.slice(1));
Evaluerer til:
return 1 + getSum([2,3,4]);
Det første element i arrayet tilføjet til getSum med det resterende array.
Men vi kender ikke resultatet af getSum([2,3,4]) endnu, hvad sker der så? Det allerførste getSum funktionskald, getSum([1,2,3,4]) , gemmes til senere på browserens opkaldsstak .
Call-stakken er en datastruktur, der holder styr på funktionskald, der skal køres. Lad os tænke på det som en færge, der vil tage biler, funktionerne, over en bugt. Det er en lille færge ved navn HMS Call Stack, der har et enkelt envejsdæk til biler.
Så vores første getSum-funktionsbil kører tilbage i færgen. Det returnerer en værdi på 1 + getSum([2,3,4]) som vil blive behandlet senere.
Derefter getSum([2,3,4] kaldes rekursivt. Hvad vil den funktion returnere? 2 + getSum([3,4]) . En anden bil bakkes ind i HMS Call Stack.
Dette fortsætter, indtil vi rammer vores basiscase, det sidste element i arrayet.
if (arr.length <= 1 ) return arr[0];
Det returnerer det første og eneste tilbageværende element i arrayet. Altså en getSum-funktionsbil, der returnerer 4 backs til HMS Call Stack.
Nu hvor vi har ramt vores base case, vil der ikke flere funktionsbiler gå ombord på HMS Call Stack. Tid for færgen at krydse bugten.
Når færgen lægger til, skal den sidste bil, der ankommer (blå) først af borde. På samme måde er Call Stack-datastrukturer Sidst ind, først ud (LIFO). Den sidst tilføjede funktion til stakken vil blive kaldt først.
Hvis den sidste funktionsbil at gå ombord går fra HMS Call Stack, hvad skal vi så have?
Den returnerer 4 til den funktion, der kaldte getSum([4]) . Og når den næste funktion kaldes:
Den returnerer 3 + 4 til den funktion, der kaldte den. Læg mærke til, hvordan vi er tilbage til, hvor vi startede? Vi tilføjer hvert element i arrayet et ad gangen, men på en mere elegant måde.
Endelig, når den første getSum-funktionsbil at gå ombord går fra HMS Call Stack, har vi vores samlede værdi. Ti!
Og der går vi. Det er sådan en rekursiv funktion fungerer som demonstreret af farverige biler og et søfart !
For yderligere læsning
At lægge værdierne af et array sammen er en god introduktion til rekursion, men det er ikke fantastisk til praktisk anvendelse. For mere dybdegående vejledninger tjek Algoritmer i JavaScript eller Recursion er ikke svært.
Forsidebillede af Zhang Fengsheng på Unsplash.