Co je to rekurze ocasu?

Rekurze ocasu je speciální případ rekurze, kdy volající funkce po provedení rekurzivního volání již nepočítá. Například funkce

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

je rekurzivní ocas (protože poslední instrukce je rekurzivní volání), zatímco tato funkce není rekurzivní ocas:

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

protože po provedení rekurzivního volání provede určitý výpočet.

Rekurze ocasu je důležitá, protože ji lze implementovat efektivněji než obecnou rekurzi. Když provádíme normální rekurzivní volání, musíme poslat zpáteční adresu do zásobníku volání a poté přeskočit na volanou funkci. To znamená, že potřebujeme zásobník volání, jehož velikost je lineární v hloubce rekurzivních volání. Když máme ocasní rekurzi, víme, že jakmile se vrátíme z rekurzivního volání, vrátíme se také okamžitě, takže můžeme přeskočit celý řetězec rekurzivních funkcí, které se vracejí a vrátí se přímo k původnímu volajícímu. „Pro všechna rekurzivní volání vůbec nepotřebujeme zásobník volání a poslední volání lze implementovat jako jednoduchý skok, který nám ušetří místo.

Komentáře

• napsal jste “ To znamená, že pro všechny rekurzivní hovory iv id nepotřebujeme ‚ zásobník volání vůbec = „6e15e5fda3“>

Jednoduše řečeno, rekurze ocasu je rekurze, kde by překladač mohl nahradit rekurzivní volání pomocí příkazu „goto“, takže kompilovaná verze nebude muset zvětšovat hloubku zásobníku.

Někdy návrh rekurzivní funkce ocasu vyžaduje, abyste vytvořili pomocnou funkci s dalšími parametry.

Například toto není funkce rekurzivní ocas:

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

Ale toto je ocas- rekurzivní funkce:

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

protože kompilátor mohl rekurzivní funkci přepsat na nerekurzivní pomocí něčeho podobného (pseudokódu):

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

Pravidlo pro překladač je velmi jednoduché: Když najdete „return thisfunction(newparameters);„, nahraďte jej textem „

„. To však lze provést pouze v případě, že je hodnota vrácená rekurzivním voláním vrácena přímo.

Pokud lze takto nahradit všechna rekurzivní volání ve funkci, pak jde o ocas – rekurzivní funkce.

Moje odpověď je založena na vysvětlení uvedeném v knize Struktura a interpretace počítačových programů . Tuto knihu velmi doporučuji počítačovým vědcům.

Přístup A: Lineární rekurzivní proces

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

Tvar procesu pro Přístup A vypadá takto:

(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 

Přístup B: Lineární iterační 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))) 

Tvar procesu pro přístup B vypadá takto:

(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 

Lineární iterativní proces (přístup B) běží v konstantním prostoru, přestože jde o rekurzivní postup. Je třeba také poznamenat, že v tomto přístupu nastavená proměnná definuje stav procesu v jakémkoli bodě, viz. {product, counter, max-count}. Toto je také technika, kterou rekurze ocasu umožňuje optimalizaci kompilátoru.

V přístupu A existuje více skrytých informací, které interpret udržuje, což je v zásadě řetězec odložených operací.

Komentáře

• Nemělo by ‚ být jen (1) místo (* 1)?

rekurze ocasu je forma rekurze, ve které jsou rekurzivní volání posledními instrukcemi ve funkci (z níž pochází ocasní část). Rekurzivní volání navíc nesmí být tvořeno odkazy na paměťové buňky, které ukládají předchozí hodnoty (odkazy jiné než tímto způsobem se nestaráme o předchozí hodnoty a pro všechny rekurzivní volání stačí jeden rámec zásobníku; ocasní rekurze je jedním ze způsobů optimalizace rekurzivních algoritmů. Další výhodou / optimalizací je, že existuje snadný způsob, jak transformovat ocasní rekurzivní algoritmus na ekvivalentní, který místo rekurze používá iteraci. Takže ano, algoritmus pro quicksort je skutečně rekurzivní ocas.

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

Zde je iterativní verze:

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