Co to jest rekurencja ogona?

Rekurencja ogonowa to szczególny przypadek rekurencji, w którym funkcja wywołująca nie wykonuje już obliczeń po wykonaniu wywołania rekurencyjnego. Na przykład funkcja

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

jest rekurencyjna z ogonem (ponieważ ostatnia instrukcja jest wywołaniem rekurencyjnym), podczas gdy ta funkcja nie jest rekurencyjna:

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

ponieważ wykonuje pewne obliczenia po powrocie wywołania rekurencyjnego.

Rekursja ogonowa jest ważna, ponieważ może być implementowana wydajniej niż rekurencja ogólna. Kiedy wykonujemy normalne wywołanie rekurencyjne, musimy wrzucić adres powrotny na stos wywołań, a następnie przeskoczyć do wywoływanej funkcji. Oznacza to, że potrzebujemy stosu wywołań, którego rozmiar jest liniowy w głębi wywołań rekurencyjnych. Kiedy mamy rekurencję ogonową, wiemy, że gdy tylko wrócimy z wywołania rekurencyjnego, „natychmiast powrócimy, więc możemy pominąć cały łańcuch funkcji rekurencyjnych powracających i powrócić bezpośrednio do pierwotnego wywołania. „nie potrzebuję w ogóle stosu wywołań dla wszystkich wywołań rekurencyjnych i może zaimplementować końcowe wywołanie jako prosty skok, co oszczędza nam miejsce.

Komentarze

• napisałeś ” Oznacza to, że ' nie potrzebujemy w ogóle stosu wywołań dla wszystkich wywołań rekurencyjnych „. Stos wywołań zawsze tam będzie, tylko że adres zwrotny nie musi być zapisywany w stosie wywołań, prawda?
• W pewnym stopniu zależy to od modelu obliczeń 🙂 Ale tak, na prawdziwym komputerze stos wywołań nadal istnieje, ' po prostu go nie używamy.
• A co, jeśli ' s jest ostateczne zadzwoń, ale w pętli for. Więc wszystkie obliczenia wykonujesz powyżej, ale niektóre z nich są wykonywane w pętli for, np. def recurse(x): if x < 0 return 1; for i in range 100{ (do calculations) recurse(x)}
• @ thed0ctor – ta rekurencja nie ' t terminate.

Krótko mówiąc, rekurencja ogona to rekurencja, w której kompilator może zastąpić wywołanie rekurencyjne z poleceniem „goto”, więc skompilowana wersja nie będzie musiała zwiększać głębokości stosu.

Czasami zaprojektowanie funkcji rekurencyjnej ogonowej wymaga stworzenia funkcji pomocniczej z dodatkowymi parametrami.

Na przykład to nie funkcja rekurencyjna ogonowa:

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

Ale to jest ogon – funkcja rekurencyjna:

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

ponieważ kompilator mógłby przepisać funkcję rekurencyjną na nierekurencyjną, używając czegoś takiego (pseudokod):

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

Reguła dla kompilatora jest bardzo prosta: gdy znajdziesz „return thisfunction(newparameters);”, zamień go na „

„. Ale można to zrobić tylko wtedy, gdy wartość zwracana przez wywołanie rekurencyjne jest zwracana bezpośrednio.

Jeśli wszystkie wywołania rekurencyjne w funkcji można zastąpić w ten sposób, to jest to koniec -recursive function.

Moja odpowiedź opiera się na wyjaśnieniu podanym w książce Struktura i interpretacja programów komputerowych . Gorąco polecam tę książkę informatykom.

Podejście A: liniowy proces rekurencyjny

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

Kształt procesu dla Podejście A wygląda następująco:

(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 

Podejście B: liniowy proces iteracyjny

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

Kształt procesu dla Podejście B wygląda następująco:

(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 

Liniowy proces iteracyjny (podejście B) przebiega w stałej przestrzeni, mimo że jest to procedura rekurencyjna. Należy również zauważyć, że w tym podejściu zbiór zmiennych definiuje stan procesu w dowolnym momencie. {product, counter, max-count}. Jest to również technika, dzięki której rekurencja ogonowa umożliwia optymalizację kompilatora.

W podejściu A jest więcej ukrytych informacji, które przechowuje interpreter, czyli w zasadzie łańcuch odroczonych operacji.

Komentarze

• Nie powinno ' być tylko (1) zamiast (* 1)?

Tail-recursion jest formą rekurencji, w której wywołania rekurencyjne są ostatnimi instrukcjami w funkcji (z których pochodzi część ogonowa). Ponadto wywołanie rekurencyjne nie może składać się z odwołań do komórek pamięci przechowujących poprzednie wartości (odwołania inne niż W ten sposób nie przejmujemy się poprzednimi wartościami i jedna ramka stosu wystarcza na wszystkie wywołania rekurencyjne; rekurencja ogona jest jednym ze sposobów optymalizacji algorytmów rekurencyjnych. Inną zaletą / optymalizacją jest to, że istnieje łatwy sposób na przekształcenie algorytmu rekurencyjnego ogonowego na równoważny algorytm, który używa iteracji zamiast rekurencji. Więc tak, algorytm szybkiego sortowania jest rzeczywiście rekurencyjny.

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

Oto wersja iteracyjna:

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