Herhaling

Herhaling

> LeekScript-zelfstudie

Vereisten:

• Verplicht:
• Weet hoe je een [functie] definieert (https://leekwars.com/encyclopedia/Les_Fonctions).
• Aanbevolen:
• Weet hoe u anonieme functies/sluitingen gebruikt.
• Bruikbaar:
• Begrip hebben van wat abstracte datatypes zijn, in het bijzonder de stapel. zie: bron
• Weet wat [Memoisization] is (https://leekwars.com/encyclopedia/Optimisation#Pr%C3%A9parer_du_curry)

----

Recursie is in grote lijnen het vermogen van een object om naar zichzelf te verwijzen. In de echte wereld is dit het duidelijkst in fractals, evenals wanneer twee spiegels tegenover elkaar worden geplaatst. We vinden dit begrip ook in zinnen van de stijl: "Ik droom dat ik droom dat ik droom." of "Ik denk dat ik schrijf dat ik droom dat ik denk dat ik schrijf...", enz. Bij het programmeren manifesteert dit zich meestal met functies die zichzelf noemen:

functie lus() { lus(); }

De bovenstaande functie is de eenvoudigste recursieve functie die er is. Als het wordt gebeld, doet het niets anders dan zichzelf bellen. Dit is hetzelfde als het gebruik van een oneindige lus (bijv. while(true);). We zullen deze functie gebruiken als basisskelet voor al onze toekomstige recursieve functies.

Herhaling

Recursie is analoog aan deconstructie. Het wordt voornamelijk gevonden in algoritmen van het type ''Verdeel en heers''. Om ons probleem op te lossen, beginnen we met het onderverdelen in gemakkelijker op te lossen subproblemen, we herhalen het proces totdat we een probleem vinden waarvan we weten hoe we het direct moeten oplossen, en van daaruit lossen we de hogere problemen op door onze eerdere oplossingen te combineren.

Stel Som in van 0 tot n

We willen een functie definiëren die een geheel getal n als parameter neemt en de som van 0 teruggeeft aan n (bijv. 0 + 1 + ... + n). Als we ons basisskelet nemen, kunnen we beginnen met de volgende functie:

functie somN(n) { somN(?); opbrengst?; }

Op dit moment hebben we de volgende informatie:

• n is bekend;
• we kunnen sumN aanroepen met een nieuwe waarde;
• we kunnen het terugbellen van het nieuwe gesprek gebruiken;
• somN moet een getal teruggeven;
• er moet ergens een toevoeging zijn;
• wat betreft loop, sumN stopt niet. We zullen moeten uitzoeken hoe we het kunnen stoppen.

Als u recursief werkt, is het altijd een goed idee om te beginnen met de stopvoorwaarde. In het geval van recursie willen we stoppen met het creëren van subproblemen als we iets hebben gevonden dat we kunnen oplossen. In dit geval is de som van 0 tot 0 iets waarvan we weten hoe we het moeten oplossen. 0 is daarom ons basisgeval, we kunnen direct de overeenkomstige som teruggeven.

functie somN(n) { als (n === 0) { geef 0 terug; } else { somN(?); opbrengst?; } }

We moeten nu uitzoeken hoe we het basisscenario kunnen bereiken. We zouden n van zichzelf kunnen aftrekken, maar in dat geval zouden we de gehele getallen tussen 0 en n niet kunnen optellen, we zouden alleen 0 en n beschikbaar hebben. We zullen dus een deelprobleem moeten creëren dat een som kan oplossen met een n die dichter bij ons basisscenario ligt.

functie somN(n) { als (n === 0) { geef 0 terug; } else { somN(n - 1); opbrengst?; } }

We hoeven nu alleen nog maar de som te maken die in het begin van ons werd gevraagd. Hier is de som van 0 tot n ook de som van de som van 0 tot n - 1 en n.

functie somN(n) { als (n === 0) { geef 0 terug; } anders { geef n + somN(n - 1); } }

Met een ternair:

functie somN(n) { terug n === 0? 0 : n + somN(n - 1); }

Voel je vrij om de code in je Leekwars-editor uit te proberen. Misschien ontdek je het grootste probleem met recursie. U kunt de uitvoering ook (op een eenvoudige manier) visualiseren op deze site.

Corecursie

/!\ Sectie om opnieuw te doen, wat wordt getoond is meestal staartrecursie. Niet geschikt voor meerdere vestigingen. /!\ Corecursie is analoog aan constructie. In tegenstelling tot recursie, waarbij we proberen een basisscenario te bereiken vanuit ons hoofdprobleem, beginnen we bij corecursie direct met ons basisscenario en gaan we op weg naar de oplossing van het hoofdprobleem.

Wederzijdse recursie

We hebben wederzijdse recursie al behandeld met spiegels en zinnen. Bij het programmeren, met functies, vertaalt dit zich naar twee of meer functies die elkaar aanroepen. We presenteren hieronder het eenvoudigste geval van wederzijdse recursie:

functie mutualLoop() { wederzijdseHelper(); }

functie mut