Rekursion

Rekursion

> LeekScript handledning

Förutsättningar:

• Obligatorisk:
• Vet hur man definierar en funktion.
• Rekommenderas:
• Veta hur man använder anonyma funktioner/stängningar.
• Användbart:
• Ha föreställningar om vad som är abstrakta datatyper, i synnerhet stacken. cf: källa
• Vet vad [Memoisering] är(https://leekwas.com/encyclopedia/Optimisation#Pr%C3%A9parer_du_curry)

----

Rekursion, i stort sett, är ett objekts förmåga att referera till sig själv. I den verkliga världen är detta tydligast i fraktaler, såväl som när två speglar placeras ansikte mot ansikte. Vi hittar också denna föreställning i stilens meningar: "Jag drömmer att jag drömmer att jag drömmer." eller "Jag tror att jag skriver att jag drömmer att jag tror att jag skriver..." osv. I programmering manifesteras detta mest med funktioner som kallar sig:

function loop() { slinga(); }

Ovanstående funktion är den enklaste rekursiva funktionen som finns. När den ringer gör den inget annat än att ringa sig själv. Detta är samma sak som att använda en oändlig loop (t.ex. while(true);). Vi kommer att använda denna funktion som ett grundläggande skelett för alla våra framtida rekursiva funktioner.

Rekursion

Rekursion är analogt med dekonstruktion. Det finns främst i algoritmer av typen ''Divide and Conquer''. För att lösa vårt problem börjar vi med att dela upp det i enklare delproblem att lösa, vi upprepar processen tills vi hittar ett problem som vi vet hur vi ska lösa direkt, och därifrån löser vi de högre problemen genom att kombinera våra tidigare lösningar.

Ange summa från 0 till n

Vi vill definiera en funktion som tar ett heltal n som en parameter och returnerar summan av 0 till n (t.ex. 0 + 1 + ... + n). Med vårt grundläggande skelett kan vi börja med följande funktion:

funktion summaN(n) { summaN(?); lämna tillbaka?; }

För tillfället har vi följande information:

• n är känt;
• vi kan kalla sumN med ett nytt värde;
• vi kan använda returen av det nya samtalet;
• sumN måste returnera ett nummer;
• det måste finnas ett tillägg någonstans;
• När det gäller loop, slutar inte sumN. Vi måste komma på hur vi ska stoppa det.

När du arbetar rekursivt är det alltid en bra idé att börja med stopptillståndet. Vid rekursion vill vi sluta skapa delproblem när vi har hittat något vi kan lösa. I det här fallet är summan av "0" till "0" något vi vet hur vi ska lösa. 0 är därför vårt basfall, vi kan direkt returnera motsvarande summa.

funktion summaN(n) { if (n === 0) { return 0; } else { summaN(?); lämna tillbaka?; } }

Vi måste nu ta reda på hur vi når basfallet. Vi skulle kunna subtrahera n från sig själv, men i så fall skulle vi inte kunna summera heltal mellan 0 och n, vi skulle bara ha 0 och n tillgängliga. Vi kommer därför att behöva skapa ett delproblem som kan lösa en summa med ett n närmare vårt basfall.

funktion summaN(n) { if (n === 0) { return 0; } annat { summaN(n - 1); lämna tillbaka?; } }

Vi behöver nu bara göra summan, som vi bad oss om i början. Här är summan av 0 till n också summan av summan av 0 till n - 1 och n.

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

Med en ternär:

funktion summaN(n) { returnera n === 0? 0 : n + summaN(n-1); }

Testa gärna koden i din Leekwars-editor. Kanske kommer du att upptäcka huvudproblemet med rekursion. Du kan också visualisera utförandet (på ett grundläggande sätt) på denna webbplats.

Corecursion

/!\ Sektion att göra om, det som visas är mest svansrekursion. Olämplig för flera grenar. /!\ Corecursion är analogt med konstruktion. Till skillnad från i rekursion där vi försöker nå ett basfall från vårt huvudproblem, börjar vi i corecursion direkt med vårt basfall och går mot lösningen av huvudproblemet.

Ömsesidig rekursion

Vi har redan täckt ömsesidig rekursion med speglar och meningar. I programmering, med funktioner, översätts detta till att två eller flera funktioner anropar varandra. Vi presenterar nedan det enklaste fallet av ömsesidig rekursion:

function mutualLoop() { mutualHelper(); }

funktion mut