Różnica między rekurencją głowy i ogona [duplikat]

Question

Różnica między rekurencją głowy i ogona [duplikat]

To pytanie ma już odpowiedź tutaj:

Czym jest rekurencja ogonowa? 23 odpowiedzi

Próbuję zrozumieć różnicę między tymi 2 rekurencyjnymi strategiami.

Powiedziano mi, że definicja jest następująca:

Rekursja ogonowa: wywołanie jest rekursywne ogonowo, jeśli nie trzeba nic zrobić po powrocie wywołania, tzn. gdy wywołanie zwraca, zwracana wartość jest natychmiast zwracana z funkcji wywołującej

Rekurencja Głowy: wywołanie jest rekurencyjne, gdy pierwsze polecenie funkcji jest wywołaniem rekurencyjnym.

16

java recursion difference

Author: Eric Leschinski, 2014-01-29

Source

1 answers

score 25 · Accepted Answer

W head recursion, wywołanie rekurencyjne, kiedy to się dzieje, pojawia się przed innym przetwarzaniem w funkcji(pomyśl o tym, że dzieje się to na górze lub na głowie funkcji).

W tail recursion jest odwrotnie-przetwarzanie odbywa się przed wywołaniem rekurencyjnym. Wybór pomiędzy dwoma stylami rekurencyjnymi może wydawać się arbitralny, ale wybór może mieć znaczenie.

Funkcja ze ścieżką z pojedynczym wywołaniem rekurencyjnym na początku ścieżki używa tak zwanego head recursion. Na funkcja czynnikowa poprzedniej wystawy wykorzystuje rekurencję głowy. Pierwszą rzeczą, jaką robi, gdy stwierdzi, że potrzebna jest rekurencja, jest wywołanie się z parametrem decremented. Funkcja z pojedynczym rekurencyjnym wywołaniem na końcu ścieżki używa rekurencji ogonowej. zobacz ten artykuł

Przykładowa Rekurencja:

public void tail(int n)         |     public void head(int n)
{                               |     {
    if(n == 1)                  |         if(n == 0)
        return;                 |             return;
    else                        |         else
        System.out.println(n);  |             head(n-1);
                                |
    tail(n-1);                  |         System.out.println(n);
}                               |     }

Jeśli wywołanie rekurencyjne występuje na końcu metody, nazywa się ją tail recursion. Rekurencja ogonowa to similar to a loop. method executes all the statements before jumping into the next recursive call.

Jeśli wywołanie rekurencyjne występuje w beginning of a method, it is called a head recursion. method saves the state before jumping into the next recursive call.