Co to jest rekurencja ogona?

52

Znam ogólną koncepcję rekurencji. Zetknąłem się z koncepcją rekurencji ogona podczas studiowania algorytmu Quicksort. W tym filmie z algorytmem szybkiego sortowania z MIT o godzinie 18:30 profesor mówi, że jest to algorytm rekurencyjny ogona. Nie jest dla mnie jasne, co tak naprawdę oznacza rekurencja ogona.

Czy ktoś może wyjaśnić tę koncepcję odpowiednim przykładem?

Niektóre odpowiedzi udzielone przez społeczność SO tutaj .

Maniak
źródło
Powiedz nam więcej o kontekście, w którym spotkałeś się z terminem rekurencja ogona . Połączyć? Cytat?
A.Schulz
@ A.Schulz Umieściłem link do kontekstu.
Geek
5
Spójrz na „ Co to jest rekurencja ogona? ” Na
przepełnieniu stosu
2
@ajmartin Pytanie dotyczy granicy przepełnienia stosu, ale zdecydowanie dotyczy tematu informatyki , więc w zasadzie informatyka powinna dawać lepsze odpowiedzi. To się tutaj nie zdarzyło, ale nadal można ponownie zapytać tutaj w nadziei na lepszą odpowiedź. Geek, powinieneś jednak wspomnieć o swoim wcześniejszym pytaniu na temat SO, aby ludzie nie powtarzali tego, co już zostało powiedziane.
Gilles „SO- przestań być zły”,
1
Powinieneś również powiedzieć, co jest niejednoznaczną częścią lub dlaczego nie jesteś zadowolony z poprzednich odpowiedzi, myślę, że w SO ludzie udzielają dobrych odpowiedzi, ale co spowodowało, że zapytałeś ponownie?

Odpowiedzi:

52

Rekurencja ogona jest szczególnym przypadkiem rekurencji, w której funkcja wywołująca nie wykonuje już obliczeń po wykonaniu wywołania rekurencyjnego. Na przykład funkcja

int f (int x, int y) {
  jeśli (y == 0) {
    zwraca x;
  }

  zwraca f (x * y, y-1);
}

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

int g (int x) {
  jeśli (x == 1) {
    zwraca 1;
  }

  int y = g (x-1);

  zwraca x * y;
}

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

Rekurencja ogona jest ważna, ponieważ można ją wdrożyć bardziej efektywnie niż rekurencja ogólna. Kiedy wykonujemy normalne wywołanie rekurencyjne, musimy wcisnąć adres zwrotny na stos wywołań, a następnie przejść do wywoływanej funkcji. Oznacza to, że potrzebujemy stosu wywołań, którego rozmiar jest liniowy na głębokości wywołań rekurencyjnych. Kiedy mamy rekurencję ogona, wiemy, że jak tylko wrócimy z wywołania rekurencyjnego, natychmiast również wrócimy, więc możemy pominąć cały łańcuch funkcji rekurencyjnych powracających i powrócić bezpośrednio do pierwotnego wywołującego. Oznacza to, że w ogóle nie potrzebujemy stosu wywołań dla wszystkich wywołań rekurencyjnych i możemy zrealizować ostateczne wywołanie jako zwykły skok, który oszczędza nam miejsce.

Matt Lewis
źródło
2
napisałeś „To oznacza, że ​​wcale nie potrzebujemy stosu wywołań dla wszystkich wywołań rekurencyjnych”. Stos wywołań będzie zawsze tam, tylko że adres zwrotny nie musi być zapisany w stosie wywołań, prawda?
Geek
2
W pewnym stopniu zależy to od twojego modelu obliczeniowego :) Ale tak, na prawdziwym komputerze stos wywołań wciąż tam jest, po prostu go nie używamy.
Matt Lewis
Co jeśli jest to ostatnie wezwanie, ale z pętlą for. def recurse(x): if x < 0 return 1; for i in range 100{ (do calculations) recurse(x)}
Robisz
13

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

Czasami zaprojektowanie funkcji rekurencyjnej ogona wymaga utworzenia funkcji pomocniczej z dodatkowymi parametrami.

Na przykład nie jest to funkcja rekurencyjna:

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

Ale jest to 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 może 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 kompilatora jest bardzo prosta: gdy znajdziesz „ return thisfunction(newparameters);”, zamień go na „ parameters = newparameters; goto start;”. Można to jednak zrobić tylko wtedy, gdy wartość zwrócona przez wywołanie rekurencyjne zostanie zwrócona bezpośrednio.

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

Viliam Búr
źródło
13

Moja odpowiedź opiera się na wyjaśnieniach podanych w książce Struktura i interpretacja programów komputerowych . Bardzo 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 podejścia 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ścia 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) działa w stałej przestrzeni, mimo że proces ten jest procedurą rekurencyjną. Należy również zauważyć, że w tym podejściu ustawione zmienne określają stan procesu w dowolnym punkcie, a mianowicie. {product, counter, max-count}. Jest to również technika, dzięki której rekurencja ogona umożliwia optymalizację kompilatora.

W podejściu A jest więcej ukrytych informacji, które interpreter utrzymuje, a mianowicie łańcuch odroczonych operacji.

ajmartin
źródło
5

Rekursja ogona jest formą rekurencji, w której wywołania rekurencyjne są ostatnimi instrukcjami funkcji (stąd pochodzi część ogona). Ponadto wywołanie rekurencyjne nie może składać się z odniesień do komórek pamięci przechowujących poprzednie wartości (odniesienia inne niż parametry funkcji). W ten sposób nie dbamy o poprzednie wartości i jedna ramka stosu wystarcza dla wszystkich wywołań rekurencyjnych; rekursja ogona jest jednym ze sposobów optymalizacji algorytmów rekurencyjnych. Inną zaletą / optymalizacją jest to, że istnieje prosty sposób na przekształcenie algorytmu rekurencyjnego ogona na równoważny, który używa iteracji zamiast rekurencji. Tak więc, 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
saadtaame
źródło