Ce este recursiunea cozii?

Recursiunea de coadă este un caz special de recursivitate în care funcția de apelare nu mai calculează după efectuarea unui apel recursiv. De exemplu, funcția

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

este recursivă la coadă (deoarece instrucțiunea finală este un apel recursiv) în timp ce această funcție nu este recursivă la coadă:

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

deoarece face unele calcule după ce apelul recursiv a revenit.

Recursiunea de coadă este importantă deoarece poate fi implementată mai eficient decât recursivitatea generală. Când efectuăm un apel recursiv normal, trebuie să împingem adresa de retur pe teancul de apeluri, apoi să trecem la funcția apelată. Aceasta înseamnă că avem nevoie de o stivă de apeluri a cărei dimensiune este liniară în profunzimea apelurilor recursive. Când avem recursivitate la coadă, știm că, de îndată ce ne întoarcem de la apelul recursiv, vom reveni imediat și, astfel încât să putem sări peste întregul lanț de funcții recursive care revin și să ne întoarcem direct la apelantul original. „Nu aveți deloc nevoie de o stivă de apeluri pentru toate apelurile recursive și puteți implementa apelul final ca un simplu salt, care ne economisește spațiu.

Comentarii

• ați scris ” Asta înseamnă că nu avem ‘ deocamdată nevoie de o stivă de apeluri pentru toate apelurile recursive „. Stiva de apeluri va fi întotdeauna acolo, doar că adresa de returnare nu trebuie să fie scrisă în stiva de apeluri, nu?
• Depinde într-o oarecare măsură de modelul dvs. de calcul 🙂 Dar da, pe un computer real, stiva de apeluri este încă acolo, ‘ nu o folosim.
• Ce se întâmplă dacă ‘ este finalul apel, dar pentru buclă. Deci, vă faceți toate calculele de mai sus, dar unele dintre ele într-o buclă for, cum ar fi def recurse(x): if x < 0 return 1; for i in range 100{ (do calculations) recurse(x)}
• @ thed0ctor – acest recursiv nu ‘ t terminați.

Pur și simplu spus, recursiunea de coadă este o recursiune în care compilatorul ar putea înlocui apelul recursiv cu o comandă „go”, deci versiunea compilată nu va trebui să mărească adâncimea stivei.

Uneori, pentru a proiecta o funcție recursivă de coadă este necesar să creați o funcție de ajutor cu parametri suplimentari.

De exemplu, aceasta nu este nu o funcție recursivă:

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

Dar aceasta este o coadă funcție recursivă:

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

deoarece compilatorul ar putea rescrie funcția recursivă într-una nerecursivă, folosind ceva de genul acesta (un pseudocod):

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

Regula pentru compilator este foarte simplă: când găsiți „return thisfunction(newparameters);„, înlocuiți-l cu „

„. Dar acest lucru se poate face numai dacă valoarea returnată de apelul recursiv este returnată direct.

Dacă toate apelurile recursive dintr-o funcție pot fi înlocuite astfel, atunci este o coadă -funcție recursivă.

Răspunsul meu se bazează pe explicația dată în carte Structura și interpretarea programelor de calculator . Recomand cu tărie această carte informaticienilor.

Abordarea A: Procesul recursiv liniar

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

Forma procesului pentru Abordarea A arată astfel:

(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 

Abordarea B: Procesul iterativ liniar

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

Forma procesului pentru Abordarea B arată astfel:

(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 

Procesul iterativ liniar (abordarea B) rulează în spațiu constant, chiar dacă procesul este o procedură recursivă. De asemenea, trebuie remarcat faptul că în această abordare un set de variabile definește starea procesului în orice moment și anume. {product, counter, max-count}. Aceasta este, de asemenea, o tehnică prin care recursivitatea cozii permite optimizarea compilatorului.

În abordarea A există mai multe informații ascunse pe care interpretul le menține, care este în esență lanțul operațiilor amânate.

Comentarii

• Nu ar trebui să ‘ să fie doar (1) în loc de (* 1)?

Coadă-recursivitate este o formă de recursivitate în care apelurile recursive sunt ultimele instrucțiuni din funcție (de unde provine partea din spate). parametrii funcției). În acest fel, nu ne pasă de valorile anterioare și un cadru de stivă este suficient pentru toate apelurile recursive; recursiunea cozii este o modalitate de optimizare a algoritmilor recursivi. Celălalt avantaj / optimizare este că există o modalitate ușoară de a transforma un algoritm recursiv în coadă într-un echivalent care folosește iterația în loc de recursivitate. Deci da, algoritmul pentru quicksort este într-adevăr recursiv.

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

Iată versiunea iterativă:

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