Wat is staartrecursie?

Staartrecursie is een speciaal geval van recursie waarbij de aanroepende functie geen berekeningen meer uitvoert na het maken van een recursieve aanroep. De functie

 int f(int x, int y) { if (y == 0) { return x; } return f(x*y, y-1); } 

is bijvoorbeeld tail recursief (aangezien de laatste instructie een recursieve aanroep is) terwijl deze functie niet tail recursief is:

 int g(int x) { if (x == 1) { return 1; } int y = g(x-1); return x*y; } 

aangezien het enige berekeningen uitvoert nadat de recursieve aanroep is teruggekeerd.

Tail-recursie is belangrijk omdat het efficiënter kan worden geïmplementeerd dan algemene recursie. Wanneer we een normale recursieve oproep doen, moeten we het retouradres op de oproepstapel duwen en vervolgens naar de aangeroepen functie springen. Dit betekent dat we een call-stack nodig hebben waarvan de grootte lineair is in de diepte van de recursieve calls. Als we staartrecursie hebben, weten we dat zodra we terugkeren van de recursieve oproep, we ook onmiddellijk terugkeren, zodat we de hele reeks recursieve functies die terugkeren kunnen overslaan en direct terugkeren naar de oorspronkelijke beller. Dat betekent dat we niet “Ik heb helemaal geen call-stack nodig voor alle recursieve calls, en kan de laatste call implementeren als een simpele sprong, wat ons ruimte bespaart.

Reacties

• je schreef ” Dat betekent dat we ‘ helemaal geen call-stack nodig hebben voor alle recursieve calls “. De call-stack zal er altijd zijn, alleen dat het retouradres niet in de call-stack hoeft te worden geschreven, toch?
• Het hangt tot op zekere hoogte af van je rekenmodel 🙂 Maar ja, op een echte computer call stack is er nog steeds, we ‘ gebruiken het gewoon niet.
• Wat als het ‘ de laatste is bel maar in voor lus. Dus je doet al je bovenstaande berekeningen, maar sommige ervan in een for-lus zoals def recurse(x): if x < 0 return 1; for i in range 100{ (do calculations) recurse(x)}
• @ thed0ctor – dit recursieve doet niet ‘ t terminate.

Simpel gezegd, staartrecursie is een recursie waarbij de compiler zou kunnen vervangen de recursieve aanroep met een “goto” -commando, zodat de gecompileerde versie de stapeldiepte niet hoeft te vergroten.

Soms vereist het ontwerpen van een staartrecursieve functie dat u een hulpfunctie met aanvullende parameters moet maken.

Dit is bijvoorbeeld niet een staartrecursieve functie:

int factorial(int x) { if (x > 0) { return x * factorial(x - 1); } return 1; } 

Maar dit is een staartrecursieve functie: recursieve functie:

int factorial(int x) { return tailfactorial(x, 1); } int tailfactorial(int x, int multiplier) { if (x > 0) { return tailfactorial(x - 1, x * multiplier); } return multiplier; } 

omdat de compiler de recursieve functie zou kunnen herschrijven naar een niet-recursieve functie, met zoiets als dit (een pseudocode):

int tailfactorial(int x, int multiplier) { start: if (x > 0) { multiplier = x * multiplier; x--; goto start; } return multiplier; } 

De regel voor de compiler is heel eenvoudig: als je “return thisfunction(newparameters);” vindt, vervang deze dan door “

“. Maar dit kan alleen worden gedaan als de waarde die wordt geretourneerd door de recursieve aanroep direct wordt geretourneerd.

Als alle recursieve aanroepen in een functie op deze manier kunnen worden vervangen, dan is het een staart -recursieve functie.

Mijn antwoord is gebaseerd op de uitleg in het boek Structuur en interpretatie van computerprogrammas . Ik kan dit boek ten zeerste aanbevelen aan computerwetenschappers.

Benadering A: lineair recursief proces

(define (factorial n) (if (= n 1) 1 (* n (factorial (- n 1))))) 

De vorm van het proces voor Benadering A ziet er als volgt uit:

(factorial 5) (* 5 (factorial 4)) (* 5 (* 4 (factorial 3))) (* 5 (* 4 (* 3 (factorial 2)))) (* 5 (* 4 (* 3 (* 2 (factorial 1))))) (* 5 (* 4 (* 3 (* 2 (* 1))))) (* 5 (* 4 (* 3 (* 2)))) (* 5 (* 4 (* 6))) (* 5 (* 24)) 120 

Benadering B: lineair iteratief proces

(define (factorial n) (fact-iter 1 1 n)) (define (fact-iter product counter max-count) (if (> counter max-count) product (fact-iter (* counter product) (+ counter 1) max-count))) 

Vorm van het proces voor Benadering B ziet er als volgt uit:

(factorial 5) (fact-iter 1 1 5) (fact-iter 1 2 5) (fact-iter 2 3 5) (fact-iter 6 4 5) (fact-iter 24 5 5) (fact-iter 120 6 5) 120 

Het lineaire iteratieve proces (benadering B) wordt in constante ruimte uitgevoerd, ook al is het proces een recursieve procedure. Er moet ook worden opgemerkt dat bij deze benadering een reeks variabelen de toestand van het proces op elk punt bepalen, namelijk. {product, counter, max-count}. Dit is ook een techniek waarmee staartrecursie optimalisatie van de compiler mogelijk maakt.

In benadering A is er meer verborgen informatie die de interpreter bijhoudt, wat in feite de keten van uitgestelde bewerkingen is.

Reacties

• Mag niet ‘ t gewoon (1) in plaats van (* 1)?

Tail-recursion is een vorm van recursie waarbij de recursieve aanroepen de laatste instructies in de functie zijn (dat is waar het staartgedeelte vandaan komt). Bovendien mag de recursieve aanroep niet zijn samengesteld met verwijzingen naar geheugencellen die eerdere waarden opslaan (andere verwijzingen dan de parameters van de functie) Op deze manier geven we niet om eerdere waarden en volstaat één stapelframe voor alle recursieve aanroepen; staartrecursie is een manier om recursieve algoritmen te optimaliseren. Het andere voordeel / optimalisatie is dat er een gemakkelijke manier is om een staart-recursief algoritme om te zetten in een equivalent algoritme dat iteratie gebruikt in plaats van recursie. Dus ja, het algoritme voor quicksort is inderdaad tail-recursief.

QUICKSORT(A, p, r) if(p < r) then q = PARTITION(A, p, r) QUICKSORT(A, p, q–1) QUICKSORT(A, q+1, r) 

Hier is de iteratieve versie:

QUICKSORT(A) p = 0, r = len(A) - 1 while(p < r) q = PARTITION(A, p, r) r = q - 1 p = 0, r = len(A) - 1 while(p < r) q = PARTITION(A, p, r) p = q + 1