Jak dokładnie działa rekurencja ogona?

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.

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

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.

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

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.

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

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)

2. 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)

3. 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)

3. 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

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)

2. 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)

2. 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)

3. 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

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.

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.