Rekursion

> LeekScript vejledning

Forudsætninger:

Obligatorisk:
Ved, hvordan man definerer en funktion.
Anbefalede:
Vide hvordan man bruger anonyme funktioner/lukninger.
Nyttigt:
Har forestillinger om, hvad der er abstrakte datatyper, især stakken. jf: kilde
Ved, hvad [Memoisering] er (https://leekwas.com/encyclopedia/Optimisation#Pr%C3%A9parer_du_curry)

----

Rekursion er i store træk et objekts evne til at henvise til sig selv. I den virkelige verden er dette mest tydeligt i fraktaler, såvel som når to spejle er placeret ansigt til ansigt. Vi finder også denne forestilling i sætninger af stilen: "Jeg drømmer, at jeg drømmer, at jeg drømmer." eller "Jeg tror, at jeg skriver, at jeg drømmer, at jeg tror, at jeg skriver..." osv. I programmering manifesterer dette sig for det meste med funktioner, der kalder sig selv:

function loop() { loop(); }

Ovenstående funktion er den enkleste rekursive funktion, der findes. Når den kaldes, gør den ikke andet end at kalde sig selv. Dette er det samme som at bruge en uendelig løkke (f.eks. while(true);). Vi vil bruge denne funktion som et grundlæggende skelet for alle vores fremtidige rekursive funktioner.

Rekursion

Rekursion er analog med dekonstruktion. Det findes hovedsageligt i algoritmer af typen ''Del og erob''. For at løse vores problem starter vi med at underopdele det i lettere delproblemer at løse, vi gentager processen, indtil vi finder et problem, som vi ved, hvordan vi løser direkte, og derfra løser vi de højere problemer ved at kombinere vores tidligere løsninger.

Indstil Sum fra 0 til n

Vi ønsker at definere en funktion, der tager et heltal n som en parameter og returnerer summen af 0 til n (f.eks. 0 + 1 + ... + n). Tager vi vores grundlæggende skelet, kan vi starte med følgende funktion:

funktion sumN(n) { sumN(?); Vend tilbage?; }

I øjeblikket har vi følgende oplysninger:

n er kendt;
vi kan kalde 'sumN' med en ny værdi;
vi kan bruge returneringen af det nye opkald;
sumN skal returnere et tal;
der skal være en tilføjelse et sted;
hvad angår loop, stopper sumN ikke. Vi bliver nødt til at finde ud af, hvordan vi stopper det.

Når du arbejder rekursivt, er det altid en god idé at starte med standsningstilstanden. I tilfælde af rekursion ønsker vi at stoppe med at skabe delproblemer, når vi har fundet noget, vi kan løse. I dette tilfælde er summen af '0' til '0' noget, vi ved, hvordan vi løser. 0 er derfor vores basistilfælde, vi kan direkte returnere den tilsvarende sum.

funktion sumN(n) { if (n === 0) { return 0; } else { sumN(?); Vend tilbage?; } }

Vi skal nu finde ud af, hvordan vi når basissagen. Vi kunne trække n fra sig selv, men i så fald ville vi ikke være i stand til at summere de heltal mellem 0 og n, vi ville kun have 0 og n til rådighed. Vi bliver derfor nødt til at lave et delproblem, der kan løse en sum med et n tættere på vores basiscase.

funktion sumN(n) { if (n === 0) { return 0; } else { sumN(n - 1); Vend tilbage?; } }

Vi mangler nu kun at gøre summen, som vi blev bedt om i begyndelsen. Her er summen af 0 til n også summen af summen af 0 til n - 1 og n.

funktion sumN(n) { if (n === 0) { return 0; } else { returner n + sumN(n - 1); } }

Med en ternær:

funktion sumN(n) { returnere n === 0? 0 : n + sumN(n-1); }

Prøv gerne koden i din Leekwars-editor. Måske vil du opdage hovedproblemet med rekursion. Du kan også visualisere udførelsen (på en grundlæggende måde) på dette websted.

Corecursion

/!\ Sektion, der skal gentages, det, der vises, er for det meste halerekursion. Uegnet til flere grene. /!\ Corecursion er analog med konstruktion. I modsætning til i rekursion, hvor vi søger at nå et basistilfælde fra vores hovedproblem, starter vi i corecursion direkte med vores basistilfælde og bevæger os mod løsningen af hovedproblemet.

Gensidig rekursion

Vi har allerede dækket gensidig rekursion med spejle og sætninger. I programmering, med funktioner, oversættes dette til, at to eller flere funktioner kalder hinanden. Vi præsenterer nedenfor det enkleste tilfælde af gensidig rekursion:

function mutualLoop() { mutualHelper(); }

funktion mut