Vad är svansrekursion?

Svansrekursion är ett speciellt fall av rekursion där anropsfunktionen inte längre beräknar efter att ha gjort ett rekursivt samtal. Till exempel är funktionen

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

svansrekursiv (eftersom den slutliga instruktionen är ett rekursivt samtal) medan den här funktionen inte är svansrekursiv:

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

eftersom det gör en viss beräkning efter att det rekursiva samtalet har återvänt.

Tail-rekursion är viktigt eftersom det kan implementeras mer effektivt än allmän rekursion. När vi gör ett normalt rekursivt samtal måste vi trycka returadressen till samtalsstacken och sedan hoppa till den anropade funktionen. Det betyder att vi behöver en samtalsstack vars storlek är linjär i djupet av de rekursiva samtalen. När vi har svansrekursion vet vi att så snart vi återvänder från det rekursiva samtalet kommer vi omedelbart att återvända också, så vi kan hoppa över hela kedjan av rekursiva funktioner som återvänder och återvänder direkt till den ursprungliga uppringaren. Det betyder att vi inte ”behöver inte alls en samtalsstack för alla rekursiva samtal och kan implementera det slutliga samtalet som ett enkelt hopp, vilket sparar utrymme.

Kommentarer

• du skrev ” Det betyder att vi inte behöver ’ alls inte behöver en samtalsstack för alla rekursiva samtal ”. Samtalsstacken kommer alltid att finnas där, bara att returadressen inte behöver skrivas in i samtalsstacken, eller hur?
• Det beror på din beräkningsmodell i viss mån 🙂 Men ja, på en riktig dator är samtalsstacken finns kvar, vi ’ använder bara den inte.
• Vad händer om den ’ är finalen ring men in för loop. Så du gör alla dina beräkningar ovan men några av dem i en for loop som def recurse(x): if x < 0 return 1; for i in range 100{ (do calculations) recurse(x)}
• @ thed0ctor – den här rekursiva inte ’ t avslutas.

Enkelt sagt är svansrekursion en rekursion där kompilatorn kan ersätta det rekursiva samtalet med ett ”goto” -kommando, så att den kompilerade versionen inte behöver öka stackdjupet.

Ibland behöver du skapa en hjälpfunktion med ytterligare parametrar för att utforma en svansrekursiv funktion.

Till exempel är detta inte en svansrekursiv funktion:

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

Men det här är en svans- rekursiv funktion:

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; } 

eftersom kompilatorn kunde skriva om den rekursiva funktionen till en icke-rekursiv, med något liknande (en pseudokod):

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

Regeln för kompilatorn är mycket enkel: När du hittar ”return thisfunction(newparameters);”, ersätt den med ”

”. Men detta kan bara göras om värdet som returneras av det rekursiva samtalet returneras direkt.

Om alla rekursiva samtal i en funktion kan ersättas så här är det en svans -rekursiv funktion.

Mitt svar baseras på förklaringen i boken Struktur och tolkning av datorprogram . Jag rekommenderar den här boken till dataloger.

Tillvägagångssätt A: Linjär rekursiv process

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

Processens form för Tillvägagångssätt A ser ut så här:

(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 

Tillvägagångssätt B: Linjär Iterativ process

(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))) 

Processen för Metod B ser ut så här:

(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 

Den linjära Iterativa processen (metod B) körs i konstant utrymme även om processen är en rekursiv procedur. Det bör också noteras att i detta tillvägagångssätt definierar en uppsättning variabler processens tillstånd vid vilken punkt som helst. {product, counter, max-count}. Detta är också en teknik genom vilken svansrekursion möjliggör optimering av kompilatorn.

I tillvägagångssätt A finns mer dold information som tolken upprätthåller som i grunden är kedjan av uppskjutna operationer.

Kommentarer

• Bör ’ t bara vara (1) istället för (* 1)?

Tail-rekursion är en form av rekursion där de rekursiva samtalen är de sista instruktionerna i funktionen (det är där svansdelen kommer ifrån). Dessutom får det rekursiva samtalet inte bestå av referenser till minnesceller som lagrar tidigare värden (andra referenser än parametrarna för funktionen). På det här sättet bryr vi oss inte om tidigare värden och en stapelram räcker för alla rekursiva samtal; tail-rekursion är ett sätt att optimera rekursiva algoritmer. Den andra fördelen / optimeringen är att det finns ett enkelt sätt att omvandla en svansrekursiv algoritm till en motsvarande som använder iteration istället för rekursion. Så ja, algoritmen för quicksort är verkligen svansrekursiv.

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

Här är den iterativa versionen:

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