Rekursjon

> LeekScript-veiledning

Forutsetninger:

Påbudt, bindende:
Vet hvordan du definerer en funksjon.
Anbefalt:
Kunne bruke anonyme funksjoner/stenginger.
Nyttig:
Har forestillinger om hva som er abstrakte datatyper, spesielt stakken. cf: kilde
Vet hva [Memoisering] er (https://leekwas.com/encyclopedia/Optimisation#Pr%C3%A9parer_du_curry)

----

Rekursjon er i store trekk et objekts evne til å referere til seg selv. I den virkelige verden er dette mest tydelig i fraktaler, så vel som når to speil er plassert ansikt til ansikt. Vi finner også denne forestillingen i setninger av 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 seg for det meste med funksjoner som kaller seg:

funksjon loop() { Løkke(); }

Funksjonen ovenfor er den enkleste rekursive funksjonen som finnes. Når den kalles, gjør den ikke annet enn å ringe seg selv. Dette er det samme som å bruke en uendelig løkke (f.eks. while(true);). Vi vil bruke denne funksjonen som et grunnleggende skjelett for alle våre fremtidige rekursive funksjoner.

Rekursjon

Rekursjon er analogt med dekonstruksjon. Det finnes hovedsakelig i algoritmer av typen ''Del og hersk''. For å løse problemet vårt starter vi med å dele det inn i lettere delproblemer å løse, vi gjentar prosessen til vi finner et problem som vi vet hvordan vi skal løse direkte, og derfra løser vi de høyere problemene ved å kombinere våre tidligere løsninger.

Sett sum fra 0 til n

Vi ønsker å definere en funksjon som tar et heltall n som en parameter og returnerer summen av 0 til n (f.eks. 0 + 1 + ... + n). Ved å ta vårt grunnleggende skjelett, kan vi starte med følgende funksjon:

funksjon sumN(n) { sumN(?); komme tilbake?; }

For øyeblikket har vi følgende informasjon:

n er kjent;
vi kan kalle sumN med en ny verdi;
vi kan bruke returen av den nye samtalen;
sumN må returnere et tall;
det må være et tillegg et sted;
når det gjelder loop, stopper ikke sumN. Vi må finne ut hvordan vi skal stoppe det.

Når du jobber rekursivt, er det alltid en god idé å starte med stopptilstanden. Ved rekursjon ønsker vi å slutte å skape delproblemer når vi har funnet noe vi kan løse. I dette tilfellet er summen av "0" til "0" noe vi vet hvordan vi skal løse. 0 er derfor vårt grunntilfelle, vi kan direkte returnere den tilsvarende summen.

funksjon sumN(n) { if (n === 0) { return 0; } else { sumN(?); komme tilbake?; } }

Vi må nå finne ut hvordan vi skal nå basissaken. Vi kunne subtrahere n fra seg selv, men i så fall ville vi ikke kunne summere heltallene mellom 0 og n, vi ville bare ha 0 og n tilgjengelig. Vi blir derfor nødt til å lage et delproblem som kan løse en sum med en n nærmere grunnfallet vårt.

funksjon sumN(n) { if (n === 0) { return 0; } annet { sumN(n - 1); komme tilbake?; } }

Vi trenger nå bare å gjøre summen, som ble spurt av oss i begynnelsen. Her er summen av 0 til n også summen av summen av 0 til n - 1 og n.

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

Med en ternær:

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

Prøv gjerne koden i Leekwars-editoren din. Kanskje vil du oppdage hovedproblemet med rekursjon. Du kan også visualisere utførelsen (på en enkel måte) på denne siden.

Corecursion

/!\ Seksjon for å gjøre om, det som vises er for det meste halerekursjon. Uegnet for flere grener. /!\ Corecursion er analogt med konstruksjon. I motsetning til i rekursjon hvor vi søker å nå et basistilfelle fra hovedproblemet vårt, starter vi i corecursion direkte med vårt basistilfelle, og beveger oss mot løsningen av hovedproblemet.

Gjensidig rekursjon

Vi har allerede dekket gjensidig rekursjon med speil og setninger. I programmering, med funksjoner, oversettes dette til at to eller flere funksjoner kaller hverandre. Vi presenterer nedenfor det enkleste tilfellet av gjensidig rekursjon:

funksjon mutualLoop() { mutualHelper(); }

funksjon mut