Co to jest rekurencja ogona?

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 .

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.

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.

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.

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