Jak dokładnie działa rekurencja ogona?

121

Prawie rozumiem, jak działa rekurencja ogona i jaka jest różnica między nią a normalną rekurencją. Nie rozumiem tylko , dlaczego nie wymaga stosu do zapamiętania adresu zwrotnego.

// tail recursion
int fac_times (int n, int acc) {
    if (n == 0) return acc;
    else return fac_times(n - 1, acc * n);
}

int factorial (int n) {
    return fac_times (n, 1);
}

// normal recursion
int factorial (int n) {
    if (n == 0) return 1;
    else return n * factorial(n - 1);
}

Nie ma nic do zrobienia po wywołaniu samej funkcji w funkcji rekurencyjnej ogona, ale nie ma to dla mnie sensu.

Alan Coromano
źródło
16
Rekursja ogona jest rekursją „normalną”. Oznacza to tylko, że rekursja występuje na końcu funkcji.
Pete Becker
7
... Ale można to zaimplementować w inny sposób na poziomie IL niż normalna rekurencja, zmniejszając głębokość stosu.
KeithS
2
BTW, gcc może wykonać eliminację rekurencji ogona na "normalnym" przykładzie tutaj.
dmckee --- ex-moderator kitten
1
@Geek - Jestem programistą C #, więc moim „językiem asemblera” jest MSIL lub po prostu IL. W przypadku C / C ++ zamień IL na ASM.
KeithS
1
@ShannonSeverance Odkryłem, że gcc robi to przez proste, celowe badanie emitowanego kodu asemblera bez -O3. Odnośnik służy do wcześniejszej dyskusji, która obejmuje bardzo podobny temat i omawia, co jest konieczne do wdrożenia tej optymalizacji.
dmckee --- ex-moderator kitten

Odpowiedzi:

169

Kompilator jest w stanie to po prostu przekształcić

int fac_times (int n, int acc) {
    if (n == 0) return acc;
    else return fac_times(n - 1, acc * n);
}

na coś takiego:

int fac_times (int n, int acc) {
label:
    if (n == 0) return acc;
    acc *= n--;
    goto label;
}
Alexey Frunze
źródło
2
@ Panie 32 Nie rozumiem twojego pytania. Przekonwertowałem funkcję na równoważną, ale bez jawnej rekursji (to znaczy bez jawnych wywołań funkcji). Jeśli zmienisz logikę na coś innego niż ekwiwalent, możesz rzeczywiście utworzyć pętlę funkcji na zawsze w niektórych lub we wszystkich przypadkach.
Alexey Frunze
18
Czyli rekurencja ogonów jest skuteczna tylko dlatego, że optymalizuje ją kompilator ? W przeciwnym razie byłoby to to samo, co normalna rekursja pod względem pamięci stosu?
Alan Coromano
34
Tak. Jeśli kompilator nie może zredukować rekursji do pętli, utkniesz z rekurencją. Wszystko albo nic.
Alexey Frunze
3
@AlanDert: poprawne. Możesz również uznać rekurencję ogonową za szczególny przypadek „optymalizacji wywołania ogonowego”, szczególny, ponieważ wywołanie ogonowe dotyczy tej samej funkcji. Ogólnie, każde wywołanie ogonowe (z tymi samymi wymaganiami dotyczącymi „nie ma już pracy do wykonania”, jak w przypadku rekurencji ogonowej i gdzie zwracana wartość wywołania tail jest bezpośrednio zwracana) może zostać zoptymalizowane, jeśli kompilator może wykonać wywołanie w sposób, który ustawia adres zwrotny wywoływanej funkcji jako adres zwrotny funkcji wykonującej wywołanie końcowe, zamiast adresu, z którego wykonano wywołanie końcowe.
Steve Jessop
1
@AlanDert w C to po prostu optymalizacja niewymuszona przez żaden standard, więc przenośny kod nie powinien na tym polegać. Ale są języki (jednym z przykładów jest Scheme), w których optymalizacja rekurencji ogona jest wymuszana przez standard, więc nie musisz się martwić, że w niektórych środowiskach nastąpi przepełnienie stosu.
Jan Wróbel
57

Pytasz, dlaczego „nie wymaga stosu do zapamiętania swojego adresu zwrotnego”.

Chciałbym to zmienić. To nie używać stosu do zapamiętania adres zwrotny. Sztuczka polega na tym, że funkcja, w której występuje rekurencja ogona, ma swój własny adres zwrotny na stosie, a kiedy skacze do wywoływanej funkcji, potraktuje to jako swój własny adres zwrotny.

Konkretnie, bez optymalizacji wywołań końcowych:

f: ...
   CALL g
   RET
g:
   ...
   RET

W tym przypadku, gdy gzostanie wywołany, stos będzie wyglądał następująco:

   SP ->  Return address of "g"
          Return address of "f"

Z drugiej strony, z optymalizacją połączeń ogonowych:

f: ...
   JUMP g
g:
   ...
   RET

W tym przypadku, gdy gzostanie wywołany, stos będzie wyglądał następująco:

   SP ->  Return address of "f"

Oczywiście, po gpowrocie, wróci do lokalizacji, z której fzostał wywołany.

EDYCJA : W powyższym przykładzie wykorzystano przypadek, w którym jedna funkcja wywołuje inną funkcję. Mechanizm jest identyczny, gdy funkcja wywołuje samą siebie.

Lindydancer
źródło
8
To znacznie lepsza odpowiedź niż inne odpowiedzi. Kompilator najprawdopodobniej nie ma jakiegoś magicznego specjalnego przypadku do konwersji rekurencyjnego kodu tail. Po prostu wykonuje normalną optymalizację ostatniego połączenia, która przypadkiem przechodzi do tej samej funkcji.
Art
12

Rekurencję ogonową można zwykle przekształcić w pętlę przez kompilator, zwłaszcza gdy używane są akumulatory.

// tail recursion
int fac_times (int n, int acc = 1) {
    if (n == 0) return acc;
    else return fac_times(n - 1, acc * n);
}

skompilowałoby się do czegoś takiego jak

// accumulator
int fac_times (int n) {
    int acc = 1;
    while (n > 0) {
        acc *= n;
        n -= 1;
    }
    return acc;
}
mepcotterell
źródło
3
Nie tak sprytny jak implementacja Alexeya ... i tak, to komplement.
Matthieu M.
1
Właściwie wynik wygląda na prostszy, ale myślę, że kod implementujący tę transformację byłby O wiele bardziej "sprytny" niż eliminacja typu label / goto lub po prostu eliminacja wywołań końcowych (patrz odpowiedź Lindydancer).
Phob
Jeśli to wszystko jest rekurencja ogona, to dlaczego ludzie tak się tym ekscytują? Nie wydaje mi się, żeby ktokolwiek ekscytował się pętlami while.
Buh Buh
@BuhBuh: To nie ma przepełnienia stosu i zapobiega wypychaniu / wyskakiwaniu stosu parametrów. W przypadku takiej ciasnej pętli może to zrobić ogromną różnicę. Poza tym ludzie nie powinni się ekscytować.
Mooing Duck
11

W funkcji rekurencyjnej muszą występować dwa elementy:

  1. Wywołanie rekurencyjne
  2. Miejsce do zliczania zwracanych wartości.

„Zwykła” funkcja rekurencyjna utrzymuje (2) w ramce stosu.

Zwracane wartości w zwykłej funkcji rekurencyjnej składają się z dwóch typów wartości:

  • Inne wartości zwracane
  • Wynik obliczenia funkcji własnej

Spójrzmy na twój przykład:

int factorial (int n) {
    if (n == 0) return 1;
    else return n * factorial(n - 1);
}

Ramka f (5) „przechowuje”, na przykład, wynik własnego obliczenia (5) i wartość f (4). Jeśli wywołam silnię (5), tuż przed tym, jak wywołania stosu zaczną się zwijać, mam:

 [Stack_f(5): return 5 * [Stack_f(4): 4 * [Stack_f(3): 3 * ... [1[1]]

Zauważ, że każdy stos przechowuje, oprócz wartości, o których wspomniałem, cały zakres funkcji. Tak więc użycie pamięci dla funkcji rekurencyjnej f wynosi O (x), gdzie x jest liczbą wywołań rekurencyjnych, które muszę wykonać. Tak więc, jeśli potrzebuję 1kb pamięci RAM do obliczenia silni (1) lub silni (2), potrzebuję ~ 100k do obliczenia silni (100) i tak dalej.

Funkcja rekurencyjna ogona umieszcza (2) w swoich argumentach.

W rekursji ogonowej przekazuję wynik obliczeń częściowych w każdej klatce rekurencyjnej do następnej za pomocą parametrów. Zobaczmy nasz przykład silni, Tail Recursive:

int factorial (int n) {int helper (int num, intumulated) {if num == 0 returnumulated else return helper (num - 1 ,umulated * num)} return helper (n, 1)
}

Spójrzmy na jego ramki w silni (4):

[Stack f(4, 5): Stack f(3, 20): [Stack f(2,60): [Stack f(1, 120): 120]]]]

Widzisz różnice? W „zwykłych” wywołaniach rekurencyjnych funkcje zwracające rekursywnie tworzą wartość końcową. W Tail Recursion odwołują się tylko do przypadku podstawowego (ostatni oceniany) . Nazywamy akumulator argumentem, który śledzi starsze wartości.

Szablony rekursji

Zwykła funkcja rekurencyjna wygląda następująco:

type regular(n)
    base_case
    computation
    return (result of computation) combined with (regular(n towards base case))

Aby przekształcić go w rekurencję ogonową:

  • Wprowadź funkcję pomocniczą, która przenosi akumulator
  • uruchom funkcję pomocniczą wewnątrz funkcji głównej, z akumulatorem ustawionym na obudowę podstawową.

Popatrz:

type tail(n):
    type helper(n, accumulator):
        if n == base case
            return accumulator
        computation
        accumulator = computation combined with accumulator
        return helper(n towards base case, accumulator)
    helper(n, base case)

Zobacz różnicę?

Optymalizacja Tail Call

Ponieważ żaden stan nie jest przechowywany na stosach Non-Border-Cases of the Tail Call, nie są one tak ważne. Niektóre języki / tłumacze zastępują stary stos nowym. Tak więc, bez ramek stosu ograniczających liczbę wywołań, wywołania ogonowe zachowują się w takich przypadkach jak pętla for .

Optymalizacja zależy od kompilatora lub nie.

Lucas Ribeiro
źródło
6

Oto prosty przykład, który pokazuje, jak działają funkcje rekurencyjne:

long f (long n)
{

    if (n == 0) // have we reached the bottom of the ocean ?
        return 0;

    // code executed in the descendence

    return f(n-1) + 1; // recurrence

    // code executed in the ascendence

}

Rekursja ogona jest prostą funkcją rekurencyjną, w której rekurencja jest wykonywana na końcu funkcji, a zatem żaden kod nie jest wykonywany we wznoszeniu, co pomaga większości kompilatorów języków programowania wysokiego poziomu w wykonywaniu tego, co jest znane jako Optymalizacja rekurencji ogona , ma również bardziej złożona optymalizacja znana jako modulo rekurencji ogona

Khaled.K
źródło
1

Funkcja rekurencyjna to funkcja, która sama się wywołuje

Umożliwia programistom pisanie wydajnych programów przy użyciu minimalnej ilości kodu .

Wadą jest to, że mogą powodować nieskończone pętle i inne nieoczekiwane wyniki, jeśli nie zostaną poprawnie napisane .

Wyjaśnię zarówno prostą funkcję rekurencyjną, jak i funkcję rekurencyjną ogona

Aby napisać prostą funkcję rekurencyjną

  1. Pierwszą kwestią do rozważenia jest to, kiedy należy zdecydować się na wyjście z pętli, która jest pętlą if
  2. Po drugie, co należy zrobić, jeśli jesteśmy naszą własną funkcją

Z podanego przykładu:

public static int fact(int n){
  if(n <=1)
     return 1;
  else 
     return n * fact(n-1);
}

Z powyższego przykładu

if(n <=1)
     return 1;

Decyduje o tym, kiedy wyjść z pętli

else 
     return n * fact(n-1);

Czy faktyczne przetwarzanie ma zostać wykonane

Pozwólcie, że podzielę zadanie po kolei, aby ułatwić zrozumienie.

Zobaczmy, co się dzieje wewnętrznie, gdy biegnę fact(4)

  1. Podstawiając n = 4
public static int fact(4){
  if(4 <=1)
     return 1;
  else 
     return 4 * fact(4-1);
}

Ifpętla kończy się niepowodzeniem, więc przechodzi do elsepętli i zwraca4 * fact(3)

  1. W pamięci stosu mamy 4 * fact(3)

    Podstawiając n = 3

public static int fact(3){
  if(3 <=1)
     return 1;
  else 
     return 3 * fact(3-1);
}

Ifpętla zawodzi, więc przechodzi w elsepętlę

więc wraca 3 * fact(2)

Pamiętaj, że nazwaliśmy `` 4 * fakt (3) ''

Dane wyjściowe dla fact(3) = 3 * fact(2)

Jak dotąd stos ma 4 * fact(3) = 4 * 3 * fact(2)

  1. W pamięci stosu mamy 4 * 3 * fact(2)

    Podstawiając n = 2

public static int fact(2){
  if(2 <=1)
     return 1;
  else 
     return 2 * fact(2-1);
}

Ifpętla zawodzi, więc przechodzi w elsepętlę

więc wraca 2 * fact(1)

Pamiętaj, że dzwoniliśmy 4 * 3 * fact(2)

Dane wyjściowe dla fact(2) = 2 * fact(1)

Jak dotąd stos ma 4 * 3 * fact(2) = 4 * 3 * 2 * fact(1)

  1. W pamięci stosu mamy 4 * 3 * 2 * fact(1)

    Podstawiając n = 1

public static int fact(1){
  if(1 <=1)
     return 1;
  else 
     return 1 * fact(1-1);
}

If pętla jest prawdziwa

więc wraca 1

Pamiętaj, że dzwoniliśmy 4 * 3 * 2 * fact(1)

Dane wyjściowe dla fact(1) = 1

Jak dotąd stos ma 4 * 3 * 2 * fact(1) = 4 * 3 * 2 * 1

Ostatecznie wynik faktu (4) = 4 * 3 * 2 * 1 = 24

wprowadź opis obrazu tutaj

Recursion Tail byłoby

public static int fact(x, running_total=1) {
    if (x==1) {
        return running_total;
    } else {
        return fact(x-1, running_total*x);
    }
}
  1. Podstawiając n = 4
public static int fact(4, running_total=1) {
    if (x==1) {
        return running_total;
    } else {
        return fact(4-1, running_total*4);
    }
}

Ifpętla kończy się niepowodzeniem, więc przechodzi do elsepętli i zwracafact(3, 4)

  1. W pamięci stosu mamy fact(3, 4)

    Podstawiając n = 3

public static int fact(3, running_total=4) {
    if (x==1) {
        return running_total;
    } else {
        return fact(3-1, 4*3);
    }
}

Ifpętla zawodzi, więc przechodzi w elsepętlę

więc wraca fact(2, 12)

  1. W pamięci stosu mamy fact(2, 12)

    Podstawiając n = 2

public static int fact(2, running_total=12) {
    if (x==1) {
        return running_total;
    } else {
        return fact(2-1, 12*2);
    }
}

Ifpętla zawodzi, więc przechodzi w elsepętlę

więc wraca fact(1, 24)

  1. W pamięci stosu mamy fact(1, 24)

    Podstawiając n = 1

public static int fact(1, running_total=24) {
    if (x==1) {
        return running_total;
    } else {
        return fact(1-1, 24*1);
    }
}

If pętla jest prawdziwa

więc wraca running_total

Dane wyjściowe dla running_total = 24

Ostatecznie wynik faktu (4,1) = 24

wprowadź opis obrazu tutaj

Nursnaaz
źródło
0

Moja odpowiedź jest raczej domysłem, ponieważ rekurencja jest czymś związanym z wewnętrzną implementacją.

W rekurencji ogonowej funkcja rekurencyjna jest wywoływana na końcu tej samej funkcji. Prawdopodobnie kompilator może zoptymalizować w następujący sposób:

  1. Pozwól, aby trwająca funkcja zakończyła się (tzn. Zostanie przywołany używany stos)
  2. Przechowuj zmienne, które będą używane jako argumenty funkcji w pamięci tymczasowej
  3. Następnie wywołaj ponownie funkcję z tymczasowo przechowywanym argumentem

Jak widać, zamykamy oryginalną funkcję przed następną iteracją tej samej funkcji, więc w rzeczywistości nie „używamy” stosu.

Ale uważam, że jeśli wewnątrz funkcji są wywoływane destruktory, to ta optymalizacja może nie mieć zastosowania.

iammilind
źródło
0

Kompilator jest wystarczająco inteligentny, aby zrozumieć rekurencję ogonową, w przypadku, gdy podczas powrotu z wywołania rekurencyjnego nie ma operacji oczekującej, a wywołanie rekurencyjne jest ostatnią instrukcją, należy do kategorii rekurencji ogonowej. Kompilator zasadniczo przeprowadza optymalizację rekurencji ogona, usuwając implementację stosu. Rozważ poniższy kod.

void tail(int i) {
    if(i<=0) return;
    else {
     system.out.print(i+"");
     tail(i-1);
    }
   }

Po przeprowadzeniu optymalizacji powyższy kod jest konwertowany na poniższy.

void tail(int i) {
    blockToJump:{
    if(i<=0) return;
    else {
     system.out.print(i+"");
     i=i-1;
     continue blockToJump;  //jump to the bolckToJump
    }
    }
   }

W ten sposób kompilator wykonuje optymalizację rekurencji ogona.

Varunnuevothoughts
źródło