Mi az a farok rekurzió?

A farokrekurzió a rekurzió speciális esete, amikor a hívó funkció nem végez több számítást rekurzív hívás után. Például a

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

függvény farok rekurzív (mivel a végső utasítás rekurzív hívás), míg ez a függvény nem farok rekurzív:

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

mivel a rekurzív hívás visszatérése után végez számítást.

A farokrekurzió azért fontos, mert hatékonyabban valósítható meg, mint az általános rekurzió. Ha normál rekurzív hívást kezdeményezünk, akkor a visszaküldési címet a hívásveremre kell tolnunk, majd a hívott funkcióra kell ugranunk. Ez azt jelenti, hogy szükségünk van egy olyan híváskötegre, amelynek mérete lineáris a rekurzív hívások mélységében. Amikor farokrekurziónk van, tudjuk, hogy amint visszatérünk a rekurzív hívásból, azonnal visszatérünk is, így kihagyhatjuk a visszatérő rekurzív függvények teljes láncolatát, és egyenesen visszatérhetünk az eredeti hívóhoz. Ez azt jelenti, hogy nem “Nincs szükség hívásveremre az összes rekurzív híváshoz, és az utolsó hívást egyszerű ugrásként hajthatja végre, így helyet spórolunk meg.

Megjegyzések

• te írt ” Ez azt jelenti, hogy nincs szükségünk ‘ minden rekurzív hívásra “. A hívásverem mindig ott lesz, csak hogy a visszaküldési címet nem kell beírni a híváskötegbe, igaz?
• Ez bizonyos mértékben függ a számítási modelltől 🙂 De igen, egy valódi számítógépen a a hívásköteg még mindig ott van, ‘ csak nem használjuk.
• Mi van, ha ‘ s az utolsó hívás, de a hurokért. Tehát az összes fenti számítást elvégzi, de néhányat egy for ciklusban, például def recurse(x): if x < 0 return 1; for i in range 100{ (do calculations) recurse(x)}
• @ thed0ctor – ez a rekurzív nem ‘ t megszűnik.

Egyszerűen szólva a farokrekurzió olyan rekurzió, amelyet a fordító helyettesíthet a rekurzív hívást egy “goto” paranccsal, így a lefordított verziónak nem kell növelnie a verem mélységét.

A farok-rekurzív függvény megtervezéséhez időnként további paraméterekkel rendelkező segítő funkciót kell létrehozni.

Ez például nem farok-rekurzív függvény:

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

De ez egy farok- rekurzív függvény:

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

mert a fordító átírhatta a rekurzív függvényt nem rekurzívra, ilyesmi (álkód) használatával:

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

A fordító szabálya nagyon egyszerű: Ha megtalálja a “return thisfunction(newparameters);” szót, cserélje le a következőre: “

“. De ezt csak akkor lehet megtenni, ha a rekurzív hívás által visszaadott értéket közvetlenül visszaküldjük.

Ha egy függvény minden rekurzív hívását így lehet helyettesíteni, akkor ez egy farok rekurzív függvény.

Válaszom a A számítógépes programok felépítése és értelmezése . Nagyon ajánlom ezt a könyvet informatikusoknak.

A megközelítés: Lineáris rekurzív folyamat

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

A folyamat alakja a Az A megközelítés így néz ki:

(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 

B megközelítés: Lineáris ismétlődő folyamat

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

A B megközelítés folyamatának alakja így néz ki:

(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 

A lineáris iteratív folyamat (B megközelítés) állandó térben fut, annak ellenére, hogy a folyamat rekurzív eljárás. Azt is meg kell jegyezni, hogy ebben a megközelítésben egy halmaz változó meghatározza a folyamat állapotát bármikor, azaz {product, counter, max-count}. Ez egy olyan technika is, amellyel a farokrekurzió lehetővé teszi a fordító optimalizálását.

Az A megközelítésben több rejtett információ van, amelyet az értelmező fenntart, ami alapvetően a halasztott műveletek láncolata.

Megjegyzések

• Nem szabad, hogy ‘ legyen csak (1) helyett (* 1)?

Farok-rekurzió olyan rekurziós forma, amelyben a rekurzív hívások a függvény utolsó utasításai (ahonnan a farokrész származik). Ezenkívül a rekurzív hívás nem tartalmazhat olyan hivatkozásokat, amelyek a korábbi értékeket tároló memória cellákra vonatkoznak Ilyen módon nem törődünk a korábbi értékekkel, és egy rekeszkeret elegendő az összes rekurzív híváshoz; a farok-rekurzió a rekurzív algoritmusok optimalizálásának egyik módja. A másik előny / optimalizálás az, hogy van egy egyszerű módszer a farok-rekurzív algoritmus átalakítására egyenértékűvé, amely rekurzió helyett iterációt használ. Tehát igen, a quicksort algoritmusa valóban farrekurzív.

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

Íme az iteratív verzió:

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