Co to jest rekurencja ogona?

Kiedy zaczynałem uczyć się seplenienia, natknąłem się na termin rekurencyjny . Co to dokładnie znaczy?

Rozważ prostą funkcję, która dodaje pierwsze N ​​liczb naturalnych. (np sum(5) = 1 + 2 + 3 + 4 + 5 = 15.).

Oto prosta implementacja JavaScript, która wykorzystuje rekurencję:

function recsum(x) {
    if (x === 1) {
        return x;
    } else {
        return x + recsum(x - 1);
    }
}

Jeśli zadzwoniłeś recsum(5), to właśnie ocenia interpreter JavaScript:

recsum(5)
5 + recsum(4)
5 + (4 + recsum(3))
5 + (4 + (3 + recsum(2)))
5 + (4 + (3 + (2 + recsum(1))))
5 + (4 + (3 + (2 + 1)))
15

Zwróć uwagę, jak każde wywołanie rekurencyjne musi się zakończyć, zanim interpreter JavaScript zacznie faktycznie obliczać sumę.

Oto rekurencyjna wersja tej samej funkcji:

function tailrecsum(x, running_total = 0) {
    if (x === 0) {
        return running_total;
    } else {
        return tailrecsum(x - 1, running_total + x);
    }
}

Oto sekwencja zdarzeń, które wystąpiłyby, gdybyś zadzwonił tailrecsum(5)(co byłoby efektywne tailrecsum(5, 0)z powodu domyślnego drugiego argumentu).

tailrecsum(5, 0)
tailrecsum(4, 5)
tailrecsum(3, 9)
tailrecsum(2, 12)
tailrecsum(1, 14)
tailrecsum(0, 15)
15

W przypadku rekursywnego ogona, przy każdej ocenie wezwania rekurencyjnego, running_totalaktualizacja jest aktualizowana.

Uwaga: w oryginalnej odpowiedzi użyto przykładów z Python. Zostały one zmienione na JavaScript, ponieważ interpretery Python nie obsługują optymalizacji wywołania ogona . Jednak chociaż optymalizacja wywołania ogona jest częścią specyfikacji ECMAScript 2015 , większość interpreterów JavaScript nie obsługuje tego .

W tradycyjnej rekurencji typowym modelem jest to, że najpierw wykonujesz wywołania rekurencyjne, a następnie bierzesz wartość zwracaną wywołania rekurencyjnego i obliczasz wynik. W ten sposób nie otrzymujesz wyniku obliczeń, dopóki nie wrócisz z każdego połączenia rekurencyjnego.

W rekursji ogona najpierw wykonujesz obliczenia, a następnie wywoływanie rekurencyjne, przekazując wyniki bieżącego kroku do następnego kroku rekurencyjnego. Powoduje to, że ostatnie zdanie ma postać (return (recursive-function params)). Zasadniczo wartość zwracana dla dowolnego danego kroku rekurencyjnego jest taka sama, jak wartość zwracana następnego wywołania rekurencyjnego .

Konsekwencją tego jest to, że gdy będziesz gotowy do wykonania następnego kroku rekurencyjnego, nie potrzebujesz już bieżącej ramki stosu. Pozwala to na pewną optymalizację. W rzeczywistości przy odpowiednio napisanym kompilatorze nigdy nie powinieneś mieć snickera przepełnienia stosu z rekurencyjnym wywołaniem ogona. Po prostu ponownie użyj bieżącej ramki stosu do następnego kroku rekurencyjnego. Jestem prawie pewien, że Lisp to robi.

Ważną kwestią jest to, że rekurencja ogona jest zasadniczo równoważna zapętleniu. To nie tylko kwestia optymalizacji kompilatora, ale podstawowy fakt dotyczący ekspresji. To działa w obie strony: możesz wziąć dowolną pętlę formularza

while(E) { S }; return Q

gdzie Ei Qsą wyrażeniami i Ssą sekwencją instrukcji, i zamieniają je w funkcję rekurencji ogona

f() = if E then { S; return f() } else { return Q }

Oczywiście E, Si Qmuszą być zdefiniowane, aby obliczyć jakąś ciekawą wartość w niektórych zmiennych. Na przykład funkcja zapętlania

sum(n) {
  int i = 1, k = 0;
  while( i <= n ) {
    k += i;
    ++i;
  }
  return k;
}

jest równoważne funkcji (-om) rekurencyjnej

sum_aux(n,i,k) {
  if( i <= n ) {
    return sum_aux(n,i+1,k+i);
  } else {
    return k;
  }
}

sum(n) {
  return sum_aux(n,1,0);
}

(To „zawijanie” funkcji rekurencyjnej za pomocą funkcji o mniejszej liczbie parametrów jest powszechnym idiomem funkcjonalnym).

Ten fragment książki „ Programowanie w Lua” pokazuje, jak zrobić właściwą rekurencję ogona (w Lua, ale powinien również dotyczyć Lispa) i dlaczego jest lepszy.

Połączenia ogon [koniec rekursji] jest rodzajem goto klejony jako połączenia. Wywołanie ogona ma miejsce, gdy funkcja wywołuje inną jako ostatnią akcję, więc nie ma nic innego do roboty. Na przykład w poniższym kodzie wezwanie do gto wywołanie ogonowe:

function f (x)
  return g(x)
end

Po frozmowach gnie ma nic innego do roboty. W takich sytuacjach program nie musi powracać do funkcji wywołującej po zakończeniu funkcji wywoływanej. Dlatego po wywołaniu ogona program nie musi przechowywać żadnych informacji o funkcji wywoływania na stosie. ...

Ponieważ prawidłowe wywołanie ogona nie wykorzystuje miejsca na stosie, nie ma ograniczenia liczby „zagnieżdżonych” wywołań ogona, które program może wykonać. Na przykład możemy wywołać następującą funkcję z dowolnym numerem jako argumentem; nigdy nie przepełni stosu:

function foo (n)
  if n > 0 then return foo(n - 1) end
end

... Jak powiedziałem wcześniej, ogon jest rodzajem goto. Jako takie, całkiem użyteczne zastosowanie odpowiednich wywołań ogona w Lua służy do programowania automatów stanów. Takie aplikacje mogą reprezentować każdy stan za pomocą funkcji; zmiana stanu oznacza przejście (lub wywołanie) określonej funkcji. Jako przykład rozważmy prostą grę labiryntową. Labirynt ma kilka pokoi, każde z maksymalnie czterema drzwiami: północną, południową, wschodnią i zachodnią. Na każdym kroku użytkownik wprowadza kierunek ruchu. Jeśli w tym kierunku znajdują się drzwi, użytkownik idzie do odpowiedniego pokoju; w przeciwnym razie program wypisze ostrzeżenie. Celem jest przejście z pokoju początkowego do pokoju końcowego.

Ta gra jest typową maszyną stanową, w której obecny pokój to stan. Możemy zaimplementować taki labirynt z jedną funkcją dla każdego pokoju. Używamy wezwań ogonów, aby przenosić się z jednego pokoju do drugiego. Mały labirynt z czterema pokojami mógłby wyglądać tak:

function room1 ()
  local move = io.read()
  if move == "south" then return room3()
  elseif move == "east" then return room2()
  else print("invalid move")
       return room1()   -- stay in the same room
  end
end

function room2 ()
  local move = io.read()
  if move == "south" then return room4()
  elseif move == "west" then return room1()
  else print("invalid move")
       return room2()
  end
end

function room3 ()
  local move = io.read()
  if move == "north" then return room1()
  elseif move == "east" then return room4()
  else print("invalid move")
       return room3()
  end
end

function room4 ()
  print("congratulations!")
end

Widzisz więc, kiedy wykonujesz połączenie rekurencyjne, takie jak:

function x(n)
  if n==0 then return 0
  n= n-2
  return x(n) + 1
end

Nie jest to rekurencyjne, ponieważ po wykonaniu wywołania rekurencyjnego nadal masz do zrobienia (dodaj 1) tę funkcję. Jeśli wprowadzisz bardzo dużą liczbę, prawdopodobnie spowoduje to przepełnienie stosu.

Używając zwykłej rekurencji, każde wywołanie rekurencyjne wypycha kolejny wpis na stos wywołań. Po zakończeniu rekursji aplikacja musi usunąć wszystkie wpisy z powrotem.

W przypadku rekurencji ogona w zależności od języka kompilator może zwinąć stos do jednego wpisu, co pozwala zaoszczędzić miejsce na stosie ... Duże zapytanie rekurencyjne może w rzeczywistości spowodować przepełnienie stosu.

Zasadniczo rekurencje Tail można zoptymalizować do iteracji.

Plik żargonu mówi o definicji rekurencji ogona:

rekurencja ogona /n./

Jeśli nie masz tego dość, zobacz rekurencję ogona.

Zamiast wyjaśniać to słowami, oto przykład. To jest wersja schematu funkcji silniowej:

(define (factorial x)
  (if (= x 0) 1
      (* x (factorial (- x 1)))))

Oto wersja silnia rekurencyjna:

(define factorial
  (letrec ((fact (lambda (x accum)
                   (if (= x 0) accum
                       (fact (- x 1) (* accum x))))))
    (lambda (x)
      (fact x 1))))

W pierwszej wersji zauważysz, że rekursywne wywołanie faktu jest podawane do wyrażenia mnożenia, a zatem stan należy zapisać na stosie podczas wykonywania wywołania rekurencyjnego. W wersji z rekursywnym ogonem nie ma innego wyrażenia S oczekującego na wartość wywołania rekurencyjnego, a ponieważ nie trzeba wykonywać żadnej pracy, stan nie musi być zapisywany na stosie. Z reguły funkcje rekurencyjne schematu używają stałej przestrzeni stosu.

Rekurencja ogona odnosi się do ostatniego wywołania rekurencyjnego w ostatniej instrukcji logicznej w algorytmie rekurencyjnym.

Zwykle w rekurencji masz przypadek podstawowy, który zatrzymuje rekurencyjne połączenia i zaczyna wyskakiwać stos wywołań. Aby użyć klasycznego przykładu, choć bardziej C-izh niż Lisp, funkcja silnia ilustruje rekurencję ogona. Wywołanie rekurencyjne następuje po sprawdzeniu stanu podstawowego.

factorial(x, fac=1) {
  if (x == 1)
     return fac;
   else
     return factorial(x-1, x*fac);
}

Początkowe wywołanie do silnia byłoby factorial(n)gdzie fac=1(wartość domyślna), a n jest liczbą, dla której należy obliczyć silnię.

Oznacza to, że zamiast wciskać wskaźnik instrukcji na stos, możesz po prostu przeskoczyć na górę funkcji rekurencyjnej i kontynuować wykonywanie. Pozwala to funkcjom na powtarzanie się w nieskończoność bez przepełnienia stosu.

Napisałem post na blogu na ten temat, który zawiera graficzne przykłady tego, jak wyglądają ramki stosu.

Oto krótki fragment kodu porównujący dwie funkcje. Pierwszym z nich jest tradycyjna rekurencja w celu znalezienia silni danej liczby. Drugi wykorzystuje rekurencję ogona.

Bardzo prosty i intuicyjny do zrozumienia.

Łatwym sposobem na stwierdzenie, czy funkcja rekurencyjna jest rekurencyjna, jest zwrócenie konkretnej wartości w przypadku podstawowym. Oznacza to, że nie zwraca 1, prawdy ani niczego podobnego. Prawdopodobnie zwróci jakiś wariant jednego z parametrów metody.

Innym sposobem jest stwierdzenie, czy wywołanie rekurencyjne jest wolne od jakichkolwiek dodatków, arytmetyki, modyfikacji itp. Oznacza to, że jest to zwykłe wywołanie rekurencyjne.

public static int factorial(int mynumber) {
    if (mynumber == 1) {
        return 1;
    } else {            
        return mynumber * factorial(--mynumber);
    }
}

public static int tail_factorial(int mynumber, int sofar) {
    if (mynumber == 1) {
        return sofar;
    } else {
        return tail_factorial(--mynumber, sofar * mynumber);
    }
}

Najlepszym sposobem na zrozumienie tail call recursionjest szczególny przypadek rekurencji, w którym ostatnie wywołanie (lub wywołanie ogonowe) jest samą funkcją.

Porównywanie przykładów podanych w Pythonie:

def recsum(x):
 if x == 1:
  return x
 else:
  return x + recsum(x - 1)

^ REKURSJA

def tailrecsum(x, running_total=0):
  if x == 0:
    return running_total
  else:
    return tailrecsum(x - 1, running_total + x)

^ ODBICIE OGONU

Jak widać w ogólnej wersji rekurencyjnej, ostatnie wywołanie w bloku kodu to x + recsum(x - 1). Po wywołaniu recsummetody jest już inna operacja x + ...

Jednak w wersji rekurencyjnej tail ostatnie wywołanie (lub tail tail) w bloku kodu tailrecsum(x - 1, running_total + x)oznacza, że ​​ostatnie wywołanie jest wykonywane do samej metody i po tym nie następuje żadna operacja.

Ten punkt jest ważny, ponieważ pokazana tutaj rekurencja ogona nie powoduje powiększenia pamięci, ponieważ gdy leżąca pod nią maszyna wirtualna widzi funkcję wywołującą się w pozycji ogona (ostatnie wyrażenie, które ma być ocenione w funkcji), eliminuje bieżącą ramkę stosu, która jest znany jako Optymalizacja wezwania ogona (TCO).

EDYTOWAĆ

NB Pamiętaj, że powyższy przykład został napisany w języku Python, którego środowisko wykonawcze nie obsługuje TCO. To tylko przykład na wyjaśnienie tego. TCO jest obsługiwany w językach takich jak Scheme, Haskell itp

W Javie jest możliwa możliwa rekurencyjna implementacja funkcji Fibonacciego:

public int tailRecursive(final int n) {
    if (n <= 2)
        return 1;
    return tailRecursiveAux(n, 1, 1);
}

private int tailRecursiveAux(int n, int iter, int acc) {
    if (iter == n)
        return acc;
    return tailRecursiveAux(n, ++iter, acc + iter);
}

Porównaj to ze standardową implementacją rekurencyjną:

public int recursive(final int n) {
    if (n <= 2)
        return 1;
    return recursive(n - 1) + recursive(n - 2);
}

Nie jestem programistą Lisp, ale myślę, że to pomoże.

Zasadniczo jest to styl programowania, w którym wywołanie rekurencyjne jest ostatnią rzeczą, którą robisz.

Oto przykład Common Lisp, który wykonuje silnię przy użyciu rekurencji ogona. Z powodu natury bez stosów można było wykonywać szalenie duże obliczenia czynnikowe ...

(defun ! (n &optional (product 1))
    (if (zerop n) product
        (! (1- n) (* product n))))

A potem dla zabawy możesz spróbować (format nil "~R" (! 25))

W skrócie, rekursja ogona ma wywołanie rekurencyjne jako ostatnią instrukcję w funkcji, dzięki czemu nie musi czekać na wywołanie rekurencyjne.

Jest to więc rekurencja ogona, tj. N (x - 1, p * x) jest ostatnią instrukcją w funkcji, w której kompilator jest sprytny, aby dowiedzieć się, że można go zoptymalizować do pętli for (silnia). Drugi parametr p przenosi wartość pośrednią produktu.

function N(x, p) {
   return x == 1 ? p : N(x - 1, p * x);
}

Jest to nierekurencyjny sposób pisania powyższej funkcji silni (chociaż niektóre kompilatory C ++ i tak mogą ją zoptymalizować).

function N(x) {
   return x == 1 ? 1 : x * N(x - 1);
}

ale to nie jest:

function F(x) {
  if (x == 1) return 0;
  if (x == 2) return 1;
  return F(x - 1) + F(x - 2);
}

Napisałem długi post zatytułowany „ Zrozumienie rekurencji ogona - Visual Studio C ++ - widok zespołu ”

tutaj jest wersja Perla 5 tailrecsumwspomnianej wcześniej funkcji.

sub tail_rec_sum($;$){
  my( $x,$running_total ) = (@_,0);

  return $running_total unless $x;

  @_ = ($x-1,$running_total+$x);
  goto &tail_rec_sum; # throw away current stack frame
}

Jest to fragment Struktury i interpretacji programów komputerowych dotyczący rekurencji ogona.

W przeciwieństwie do iteracji i rekurencji musimy uważać, aby nie pomylić pojęcia procesu rekurencyjnego z pojęciem procedury rekurencyjnej. Kiedy opisujemy procedurę jako rekurencyjną, mamy na myśli składniowy fakt, że definicja procedury odnosi się (bezpośrednio lub pośrednio) do samej procedury. Ale kiedy opisujemy proces jako zgodny ze wzorem, powiedzmy, liniowo rekurencyjnym, mówimy o tym, jak ten proces ewoluuje, a nie o składni tego, jak procedura jest pisana. Może wydawać się niepokojące, że odwołujemy się do procedury rekurencyjnej, takiej jak iteracja, jako generowanie procesu iteracyjnego. Jednak proces jest naprawdę iteracyjny: jego stan jest całkowicie przechwytywany przez trzy zmienne stanu, a tłumacz musi śledzić tylko trzy zmienne, aby wykonać proces.

Jednym z powodów, dla których rozróżnienie między procesem a procedurą może być mylące, jest to, że większość implementacji popularnych języków (w tym Ada, Pascal i C) jest zaprojektowana w taki sposób, że interpretacja dowolnej procedury rekurencyjnej zużywa ilość pamięci, która rośnie wraz z liczba wywołań procedur, nawet jeśli opisany proces jest w zasadzie iteracyjny. W konsekwencji języki te mogą opisywać procesy iteracyjne tylko poprzez uciekanie się do specjalnych „zapętlonych konstrukcji”, takich jak czynność powtarzania, powtarzanie, aż do, for i while. Wdrożenie programu nie ma tej wady. Wykona iteracyjny proces w stałej przestrzeni, nawet jeśli proces iteracyjny jest opisany przez procedurę rekurencyjną. Implementacja z tą właściwością nazywa się rekurencyjną. W przypadku implementacji rekurencyjnej, iterację można wyrazić za pomocą zwykłego mechanizmu wywoływania procedury, dzięki czemu specjalne konstrukty iteracyjne są użyteczne tylko jako cukier syntaktyczny.

Funkcja rekurencyjna jest funkcją, która sama się wywołuje

Pozwala programistom pisać wydajne programy przy użyciu minimalnej ilości kodu .

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

Wyjaśnię zarówno funkcję Simple Recursive, jak i Tail Recursive

Aby napisać Prostą funkcję rekurencyjną

1. Pierwszą kwestią do rozważenia jest, kiedy powinieneś zdecydować się na wyjście z pętli, która jest pętlą if
2. Drugi to proces, który należy wykonać, 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, kiedy wyjść z pętli

else 
     return n * fact(n-1);

Czy faktyczne przetwarzanie ma zostać wykonane

Pozwólcie, że podzielę to zadanie jeden po drugim dla łatwego zrozumienia.

Zobaczmy, co się stanie wewnętrznie, jeśli uruchomię fact(4)

1. Podstawienie 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, więc wraca4 * fact(3)

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

   Podstawienie n = 3

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

Ifpętla zawodzi, więc przechodzi do elsepętli

więc wraca 3 * fact(2)

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

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

Do tej pory stos miał 4 * fact(3) = 4 * 3 * fact(2)

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

   Podstawienie n = 2

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

Ifpętla zawodzi, więc przechodzi do elsepętli

więc wraca 2 * fact(1)

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

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

Do tej pory stos miał 4 * 3 * fact(2) = 4 * 3 * 2 * fact(1)

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

   Podstawienie 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 zadzwoniliśmy 4 * 3 * 2 * fact(1)

Dane wyjściowe dla fact(1) = 1

Do tej pory stos miał 4 * 3 * 2 * fact(1) = 4 * 3 * 2 * 1

Wreszcie 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. Podstawienie 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, więc wracafact(3, 4)

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

   Podstawienie 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 do elsepętli

więc wraca fact(2, 12)

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

   Podstawienie 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 do elsepętli

więc wraca fact(1, 24)

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

   Podstawienie 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

Wreszcie wynik faktu (4,1) = 24

Rekurencja ogona to życie, w którym żyjesz teraz. Ciągle przetwarzasz tę samą ramkę stosu w kółko, ponieważ nie ma powodu ani środków, aby powrócić do „poprzedniej” ramki. Przeszłość się skończyła, więc można ją odrzucić. Dostajesz jedną klatkę, która zawsze przenosi się w przyszłość, dopóki proces nieuchronnie umrze.

_{Analogia jest załamana, gdy weźmie się pod uwagę, że niektóre procesy mogą wykorzystywać dodatkowe ramki, ale nadal uważa się je za rekurencyjne, jeśli stos nie rośnie nieskończenie.}

Rekurencja ogona to funkcja rekurencyjna, w której funkcja wywołuje się na końcu („ogon”) funkcji, w której po powrocie wywołania rekurencyjnego nie jest wykonywane żadne obliczenie. Wiele kompilatorów optymalizuje się, aby zmienić wywołanie rekurencyjne na rekursywne ogonowe lub iteracyjne.

Rozważ problem obliczania silni liczby.

Prostym podejściem byłoby:

  factorial(n):

    if n==0 then 1

    else n*factorial(n-1)

Załóżmy, że wywołujesz silnię (4). Drzewem rekurencyjnym byłoby:

       factorial(4)
       /        \
      4      factorial(3)
     /             \
    3          factorial(2)
   /                  \
  2                factorial(1)
 /                       \
1                       factorial(0)
                            \
                             1    

Maksymalna głębokość rekurencji w powyższym przypadku wynosi O (n).

Rozważ jednak następujący przykład:

factAux(m,n):
if n==0  then m;
else     factAux(m*n,n-1);

factTail(n):
   return factAux(1,n);

Drzewo rekurencji dla factTail (4) byłoby:

factTail(4)
   |
factAux(1,4)
   |
factAux(4,3)
   |
factAux(12,2)
   |
factAux(24,1)
   |
factAux(24,0)
   |
  24

Tutaj również maksymalna głębokość rekurencji wynosi O (n), ale żadne z wywołań nie dodaje żadnej dodatkowej zmiennej do stosu. Dlatego kompilator może pozbyć się stosu.

Rekurencja ogona jest dość szybka w porównaniu do normalnej rekurencji. Jest szybki, ponieważ dane wyjściowe wywołania przodków nie będą zapisywane w stosie, aby zachować ścieżkę. Ale w normalnej rekurencji wszystkie wywołania przodka zapisywane są w stosie, aby zachować ścieżkę.

Funkcja rekurencyjna typu tail jest funkcją rekurencyjną, w której ostatnią operacją wykonywaną przed powrotem jest wywołanie funkcji rekurencyjnej. Oznacza to, że zwracana wartość rekurencyjnego wywołania funkcji jest natychmiast zwracana. Na przykład kod wyglądałby tak:

def recursiveFunction(some_params):
    # some code here
    return recursiveFunction(some_args)
    # no code after the return statement

Kompilatory i interpretery, które wdrażają optymalizację ogona lub eliminację ogona mogą zoptymalizować kod rekurencyjny, aby zapobiec przepełnieniu stosu. Jeśli Twój kompilator lub interpreter nie implementuje optymalizacji wywołania ogona (takiego jak interpreter CPython), pisanie kodu w ten sposób nie przynosi dodatkowych korzyści.

Na przykład jest to standardowa rekurencyjna funkcja silnia w Pythonie:

def factorial(number):
    if number == 1:
        # BASE CASE
        return 1
    else:
        # RECURSIVE CASE
        # Note that `number *` happens *after* the recursive call.
        # This means that this is *not* tail call recursion.
        return number * factorial(number - 1)

A to jest rekurencyjna wersja funkcji silniakowej:

def factorial(number, accumulator=1):
    if number == 0:
        # BASE CASE
        return accumulator
    else:
        # RECURSIVE CASE
        # There's no code after the recursive call.
        # This is tail call recursion:
        return factorial(number - 1, number * accumulator)
print(factorial(5))

(Należy pamiętać, że chociaż jest to kod Python, interpreter CPython nie wykonuje optymalizacji wywołania ogona, więc takie ułożenie kodu nie zapewnia korzyści w czasie wykonywania).

Być może będziesz musiał uczynić kod nieco bardziej nieczytelnym, aby skorzystać z optymalizacji wywołania ogona, jak pokazano na przykładzie silni. (Na przykład przypadek podstawowy jest teraz nieco nieintuicyjny, a accumulatorparametr jest skutecznie wykorzystywany jako rodzaj zmiennej globalnej).

Ale zaletą optymalizacji wywołania ogona jest to, że zapobiega błędom przepełnienia stosu. (Zwrócę uwagę, że tę samą korzyść można uzyskać, stosując algorytm iteracyjny zamiast rekurencyjnego).

Przepełnienie stosu powstaje, gdy stos wywołań ma narzucone zbyt wiele obiektów ramki. Obiekt ramki jest wypychany na stos wywołań, gdy funkcja jest wywoływana, i wyskakuje ze stosu wywołań, gdy funkcja zwraca Obiekty ramki zawierają informacje, takie jak zmienne lokalne i wiersz wiersza kodu, do którego należy wrócić po powrocie funkcji.

Jeśli funkcja rekurencyjna wykonuje zbyt wiele wywołań rekurencyjnych bez zwracania, stos wywołań może przekroczyć limit obiektu ramki. (Liczba zależy od platformy; w Pythonie jest to domyślnie 1000 obiektów ramki.) To powoduje błąd przepełnienia stosu . (Hej, stąd pochodzi nazwa tej strony!)

Jeśli jednak ostatnią rzeczą, którą wykonuje funkcja rekurencyjna, jest wywołanie rekurencyjne i zwrócenie jego wartości zwracanej, nie ma powodu, dla którego musiałby utrzymywać bieżący obiekt ramki w celu pozostania na stosie wywołań. W końcu, jeśli po rekurencyjnym wywołaniu funkcji nie ma kodu, nie ma powodu, aby trzymać się zmiennych lokalnych bieżącego obiektu ramki. Dzięki temu możemy natychmiast pozbyć się bieżącego obiektu ramki, zamiast trzymać go na stosie wywołań. Efektem końcowym jest to, że stos wywołań nie powiększa się, a zatem nie może przepełnić stosu.

Kompilator lub interpreter musi mieć funkcję optymalizacji wywołania ogona jako funkcję, aby mogła rozpoznać, kiedy można zastosować optymalizację wywołania ogona. Nawet wtedy możesz zmienić układ kodu w funkcji rekurencyjnej, aby skorzystać z optymalizacji wywołania ogonowego, i to od Ciebie zależy, czy ten potencjalny spadek czytelności jest wart optymalizacji.

Aby zrozumieć niektóre podstawowe różnice między rekurencją typu tail-call a rekurencją typu non-tail-tail, możemy zapoznać się z implementacjami tych technik .NET.

Oto artykuł z kilkoma przykładami w C #, F # i C ++ \ CLI: Adventures in Tail Recursion w C #, F # i C ++ \ CLI .

C # nie optymalizuje się pod kątem rekurencji wywołania ogona, podczas gdy F # robi to.

Różnice zasad dotyczą pętli a rachunku Lambda. C # jest zaprojektowany z myślą o pętlach, podczas gdy F # jest zbudowany na zasadach rachunku Lambda. Aby uzyskać bardzo dobrą (i darmową) książkę na temat zasad rachunku Lambda, zobacz: Struktura i interpretacja programów komputerowych autorstwa Abelsona, Sussmana i Sussmana .

Jeśli chodzi o wezwania ogona w F #, bardzo dobry artykuł wprowadzający, zobacz Szczegółowe wprowadzenie do ogonów w F # . Na koniec, oto artykuł, który omawia różnicę między rekurencją bez ogona a rekurencją przywołania ogona (w F #): Rekurencja ogona vs. rekurencja bez ogona w Fis .

Jeśli chcesz przeczytać o niektórych różnicach projektowych rekurencji wywołania ogona między C # i F #, zobacz Generowanie kodu operacji ogona w C # i F # .

Jeśli zależy ci na tym, aby wiedzieć, jakie warunki uniemożliwiają kompilatorowi C # przeprowadzanie optymalizacji wywołania ogonowego, zobacz ten artykuł: Warunki wywołania ogonowego JIT CLR .

Istnieją dwa podstawowe rodzaje rekurencji: rekurencja głowy i rekurencja.

W przypadku rekurencji głowy funkcja wykonuje swoje wywołanie rekurencyjne, a następnie wykonuje dodatkowe obliczenia, na przykład wykorzystując wynik wywołania rekurencyjnego.

W funkcji rekurencyjnej ogona wszystkie obliczenia odbywają się najpierw, a wywołanie rekurencyjne jest ostatnią rzeczą, która się dzieje.

Zaczerpnięte z tego super niesamowitego postu. Proszę, przeczytaj to.

Rekurencja oznacza funkcję wywołującą samą siebie. Na przykład:

(define (un-ended name)
  (un-ended 'me)
  (print "How can I get here?"))

Rekonstrukcja ogona oznacza rekursję kończącą funkcję:

(define (un-ended name)
  (print "hello")
  (un-ended 'me))

Widzisz, ostatnią rzeczą, jaką nieskończona funkcja (procedura, w żargonie Schematu) jest wywołanie siebie. Innym (bardziej użytecznym) przykładem jest:

(define (map lst op)
  (define (helper done left)
    (if (nil? left)
        done
        (helper (cons (op (car left))
                      done)
                (cdr left))))
  (reverse (helper '() lst)))

W procedurze pomocnika OSTATNIM, co robi, gdy lewica nie jest zero, jest nazywanie siebie (PO czymś przeciw i coś cdr). Jest to w zasadzie sposób mapowania listy.

Rekurencja ogona ma tę wielką zaletę, że interpreter (lub kompilator, w zależności od języka i dostawcy) może go zoptymalizować i przekształcić w coś równoważnego pętli while. W rzeczywistości, w tradycji schematu, większość pętli „for” i „while” odbywa się w sposób rekurencyjny (o ile wiem, nie ma ani chwili, ani czasu).

To pytanie ma wiele świetnych odpowiedzi ... ale nie mogę nie poradzić sobie z alternatywnym podejściem do definiowania „rekurencji ogona” lub przynajmniej „właściwej rekurencji ogona”. Mianowicie: czy należy na to patrzeć jako właściwość określonego wyrażenia w programie? A może należy na to spojrzeć jako właściwość implementacji języka programowania ?

Aby uzyskać więcej informacji na temat tego drugiego widoku, istnieje klasyczny papier Willa Clingera „Prawidłowa rekurencja ogona i efektywność przestrzeni” (PLDI 1998), w którym zdefiniowano „właściwą rekurencję ogona” jako właściwość implementacji języka programowania. Definicja jest tak skonstruowana, aby pozwolić na zignorowanie szczegółów implementacji (takich jak to, czy stos wywołań jest faktycznie reprezentowany przez stos środowiska wykonawczego, czy poprzez przydzieloną stertę połączoną listę ramek).

Aby to osiągnąć, wykorzystuje analizę asymptotyczną: nie czasu wykonywania programu, jak się zwykle widzi, ale raczej wykorzystania przestrzeni programowej . W ten sposób wykorzystanie miejsca przez połączoną listę przydzieloną do stosu w porównaniu do stosu wywołań środowiska wykonawczego kończy się asymptotycznie; więc można zignorować ten szczegół implementacji języka programowania (szczegół, który z pewnością ma duże znaczenie w praktyce, ale może trochę zamazać wody, gdy próbuje się ustalić, czy dana implementacja spełnia wymóg „rekurencyjnego ogona właściwości” )

Artykuł warto uważnie przestudiować z kilku powodów:

• Daje indukcyjną definicję wyrażeń ogona i wywołań ogona programu. (Taka definicja i dlaczego takie połączenia są ważne, wydaje się być przedmiotem większości innych odpowiedzi tutaj podanych).

  Oto te definicje, aby zapewnić smak tekstu:

  Definicja 1 W wyrażenia ogon z programu napisanego na schemacie rdzenia są zdefiniowane w następujący sposób indukcyjnie.

  1. Ciało wyrażenia lambda jest wyrażeniem ogona
  2. Jeśli (if E0 E1 E2)jest wyrażeniem ogona, a następnie oba E1i E2są wyrażeniami ogon.
  3. Nic innego nie jest wyrazem ogona.

  Definicja 2 ogon wywołanie jest wyrażeniem ogon jest to wywołanie procedury.

(rekursywne wywołanie ogona lub, jak mówi gazeta, „wywołanie samo-ogona” jest szczególnym przypadkiem wywołania ogona, w którym procedura jest wywoływana sama).

• Zapewnia formalne definicje dla sześciu różnych „maszyn” dla oceny Programu rdzenia, gdzie każda maszyna ma taką samą zaobserwowania zachowanie z wyjątkiem dla asymptotycznej klasie przestrzeń złożoności, że każdy znajduje.

  Na przykład po podaniu definicji odpowiednio dla maszyn z: 1. zarządzaniem pamięcią stosu, 2. zbieraniem śmieci, ale bez wywołań ogona, 3. zbieraniem śmieci i wywołaniami ogona, papier kontynuuje pracę z jeszcze bardziej zaawansowanymi strategiami zarządzania pamięcią, takimi jak 4. „rekurencja ogona evlis”, w której środowisko nie musi być zachowane podczas oceny ostatniego argumentu wyrażenia podrzędnego w wywołaniu ogona, 5. zredukowanie środowiska zamknięcia do samych zmiennych zmiennych tego zamknięcia, oraz 6. tak zwana semantyka „bezpieczna dla przestrzeni kosmicznej” zgodnie z definicją Appela i Shao .

• Aby udowodnić, że maszyny faktycznie należą do sześciu różnych klas złożoności przestrzeni, w artykule dla każdej porównywanej pary maszyn podano konkretne przykłady programów, które ujawnią asymptotyczne powiększenie przestrzeni na jednej maszynie, ale nie na drugiej.

(Czytając teraz moją odpowiedź, nie jestem pewien, czy udało mi się uchwycić kluczowe punkty artykułu Clingera . Ale niestety nie mogę teraz poświęcić więcej czasu na opracowanie tej odpowiedzi.)

Wiele osób już wyjaśniło tutaj rekurencję. Chciałbym przytoczyć kilka przemyśleń na temat zalet, jakie rekurencja daje z książki „Współbieżność w .NET, Nowoczesne wzorce programowania współbieżnego i równoległego” Riccardo Terrella:

„Rekurencja funkcjonalna jest naturalnym sposobem na iterację w FP, ponieważ pozwala uniknąć mutacji stanu. Podczas każdej iteracji do konstruktora pętli przekazywana jest nowa wartość, która ma zostać zaktualizowana (zmutowana). Ponadto można utworzyć funkcję rekurencyjną, dzięki czemu program będzie bardziej modułowy, a także wprowadzi możliwości wykorzystania równoległości ”.

Oto także kilka interesujących uwag z tej samej książki na temat rekurencji ogona:

Rekurencja wywołania ogona jest techniką, która przekształca zwykłą funkcję rekurencyjną w zoptymalizowaną wersję, która może obsługiwać duże nakłady bez ryzyka i skutków ubocznych.

UWAGA Podstawowym powodem optymalizacji ogona jako optymalizacji jest poprawa lokalizacji danych, zużycia pamięci i pamięci podręcznej. Wykonując wywołanie ogona, osoba odbierająca używa tego samego miejsca na stosie co osoba dzwoniąca. To zmniejsza presję pamięci. To nieznacznie poprawia pamięć podręczną, ponieważ ta sama pamięć jest ponownie wykorzystywana dla kolejnych rozmówców i może pozostać w pamięci podręcznej, zamiast eksmitować starszą linię pamięci podręcznej, aby zrobić miejsce dla nowej linii pamięci podręcznej.