Czym jest rekurencja ogonowa?

W tradycyjna rekurencja typowy model polega na tym, ż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 powrócisz z każdego wywołania rekurencyjnego.

W rekurencja ogonowa , najpierw wykonujesz obliczenia, a następnie wykonujesz wywołanie rekurencyjne, przekazując wyniki bieżącego kroku do następnego kroku rekurencyjnego. To wynika z tego, że ostatnia wypowiedź ma postać (return (recursive-function params)). zasadniczo wartość zwracana każdego kroku rekurencyjnego jest taka sama jak wartość zwracana następnego wywołania rekurencyjnego .

Konsekwencją tego jest to, że gdy jesteś gotowy do wykonania kolejnego 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ć przepełnienia stosu snicker {[13] } z rekurencyjnym ogonem sprawdzam. Wystarczy ponownie użyć bieżącej ramki stosu do następnego kroku rekurencyjnego. Jestem pewien, że Lisp to robi.

Ważną kwestią jest to, że rekurencja ogonowa jest zasadniczo równoważna pętli. Nie jest to tylko kwestia optymalizacji kompilatora, ale fundamentalny fakt o wyrazistości. To działa w obie strony: możesz przyjąć dowolną pętlę postaci

while(E) { S }; return Q

Gdzie E i Q są wyrażeniami, a {[6] } jest sekwencją wyrażeń i przekształca ją w funkcję rekurencyjną ogona

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

Oczywiście, E, S, i Q muszą być zdefiniowane, aby obliczyć jakąś ciekawą wartość nad jakąś zmienne. Na przykład funkcja pętli

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

Jest odpowiednikiem funkcji rekurencyjnej(s)

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 ogonowo-rekurencyjnej z funkcją o mniejszej liczbie parametrów jest powszechnym idiomem funkcyjnym.)

Ten fragment książki Programowanie w Lua pokazuje Jak zrobić właściwą rekurencję ogonową (w Lua, ale powinna odnosić się również do Lispu) i dlaczego jest lepsza.

A tail call [tail recursion] to rodzaj goto dressed jako wezwanie. Wywołanie ogonowe ma miejsce, gdy funkcja wywołuje inną jako ostatnią działanie, więc nie ma nic innego do roboty. Na przykład w poniższym kodzie, wywołanie do g jest wywołaniem ogonowym:

function f (x)
  return g(x)
end

Po f wywołania g, nie ma nic innego do zrobienia. W takich sytuacjach program nie trzeba wracać do powołania funkcja gdy wywołana funkcja koniec. Dlatego po wywołaniu ogona, program nie musi utrzymywać żadnych informacje o funkcji wywołującej w stosie. ...

Ponieważ właściwe wywołanie ogonowe nie używa stack space, nie ma limitu na liczba" zagnieżdżonych " wywołań ogonowych, które a program może zrobić. Na przykład, możemy wywołanie następującej funkcji z dowolne liczba jako argument; nigdy nie będzie przepełnienie stosu:

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

... Jak powiedziałem wcześniej, połączenie ogonowe jest tak jakby goto. Jako takie, bardzo przydatne zastosowanie odpowiednich połączeń ogonowych w Lua służy do programowania maszyn stanowych. Takie aplikacje mogą reprezentować każdy stan za pomocą funkcji; aby zmienić stan jest udać się (lub zadzwonić) do konkretnego funkcja. Jako przykład, pozwól nam rozważ prostą grę Labirynt. Labirynt posiada kilka pokoi, każdy z maksymalnie four doors: north, południe, wschód i Zachód. Na każdym kroku użytkownik wprowadza kierunek ruchu. Jeśli są drzwi w tym kierunku użytkownik przechodzi do odpowiedni pokój; w przeciwnym razie, program wyświetla ostrzeżenie. Celem jest aby przejść z pokoju początkowego do finału miejsce.

Ta gra to typowa maszyna Państwowa, gdzie obecny pokój jest stanem. Możemy wdrożyć taki labirynt z jednym funkcja dla każdego pokoju. Używamy ogona rozmowy o przeprowadzce z jednego pokoju do kolejny. Mały labirynt z cztery pokoje może 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

Więc widzisz, kiedy wykonujesz rekurencyjne wywołanie w stylu:

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

Nie jest to rekurencyjne, ponieważ po wywołaniu rekurencyjnym nadal masz rzeczy do zrobienia (dodaj 1) w tej funkcji. Jeśli wpiszesz 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 rekurencji aplikacja musi następnie usunąć każdy wpis z powrotem w dół.

Z rekurencją ogonową kompilator jest w stanie zwinąć stos do jednego wpisu, więc oszczędzasz miejsce na stosie...Duże zapytanie rekurencyjne może faktycznie spowodować przepełnienie stosu.

Zasadniczo rekurencje ogonowe można zoptymalizować do iteracji.

Zamiast tłumaczyć to słowami, oto przykład. Jest to wersja schematu funkcji czynnikowej:

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

Oto wersja czynnikowa, która jest 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 rekurencyjne wywołanie fact jest wprowadzane do wyrażenia mnożenia, a zatem stan musi być zapisany na stosie podczas wywoływania rekurencyjnego. W wersji tail-rekurencyjnej nie ma innego S-wyrażenia oczekującego na wartość wywołanie rekurencyjne, a ponieważ nie ma dalszej pracy do wykonania, stan nie musi być zapisywany na stosie. Z reguły funkcje ogonowo-rekurencyjne Scheme używają stałej przestrzeni stosu.

Plik żargonu mówi o definicji rekurencji ogonowej:

Rekurencja ogonowa / n. /

Jeśli nie masz już tego dość, zobacz rekurencję ogonową.

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

Zazwyczaj w rekurencji masz wielkość liter , która zatrzymuje wywołania rekurencyjne i zaczyna wywoływać stos wywołań. Aby użyć klasycznego przykładu, choć bardziej C-owskiego niż Lispu, funkcja factorial ilustruje rekurencję ogonową. Wywołanie rekurencyjne występuje po sprawdzeniu warunku podstawowej wielkości liter.

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

Uwaga, pierwsze wezwanie do czynnikowej musi być czynnikiem czynnikowym (n, 1), gdzie n jest liczbą, dla której czynnik ma być obliczony.

Oznacza to, że zamiast naciskać wskaźnik instrukcji na stosie, możesz po prostu przeskoczyć na szczyt funkcji rekurencyjnej i kontynuować jej wykonywanie. Pozwala to funkcjom na rekurencję w nieskończoność bez przepełnienia stosu.

Napisałem blog post 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. Pierwsza to tradycyjna rekurencja do znajdowania iloczynu danej liczby. Drugi używa rekurencji ogonowej.

Łatwo stwierdzić, czy funkcja rekurencyjna jest rekurencyjna, jeśli zwraca konkretną wartość w przypadku podstawowym. Oznacza to, że nie zwraca 1 lub true lub coś w tym stylu. To raczej zwróci jakiś wariant jednej z metod paramters.

Innym sposobem jest stwierdzenie, czy wywołanie rekurencyjne jest wolne od dodawania, arytmetyki, modyfikacji itp... Co oznacza, że jest tylko czystym rekurencyjnym wywołaniem.

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

W Javie, oto 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ównanie tego ze standardową implementacją rekurencyjną:

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

Najlepszym sposobem dla mnie, aby zrozumieć tail call recursion jest: specjalny przypadek rekurencji, gdzie ostatnie wywołanie (lub wywołanie ogonowe) jest samą funkcją.

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

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

^rekurencja

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

^REKURENCJA OGONOWA

Jak widać w ogólnej wersji rekurencyjnej, ostatnim wywołaniem w bloku kodu jest x + recsum(x - 1). Tak więc po wywołaniu metody recsum następuje kolejna operacja, którą jest x + ...

Jednak w ogonie rekurencyjnym wersja wywołanie końcowe (lub wywołanie końcowe) w bloku kodu to tailrecsum(x - 1, running_total + x), co oznacza, że ostatnie wywołanie jest wykonywane do samej metody i nie ma operacji po tym.

Ten punkt jest ważny, ponieważ rekurencja ogonowa nie powoduje wzrostu pamięci, ponieważ gdy bazowa maszyna wirtualna widzi funkcję wywołującą się w pozycji ogonowej (ostatnie wyrażenie, które ma być obliczone w funkcji), eliminuje bieżącą ramkę stosu, która jest znana jako wywołanie ogonowe Optymalizacja (TCO).

EDIT

NB. Należy pamiętać, że powyższy przykład jest napisany w Pythonie, którego środowisko uruchomieniowe nie obsługuje TCO. To tylko przykład, aby wyjaśnić sprawę. TCO jest obsługiwane w językach takich jak Scheme, Haskell itp

Oto przykład Common Lispu, który wykonuje factorials używając rekurencji ogonowej. Ze względu na charakter bez stosu, można wykonać 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, rekurencja ogonowa ma wywołanie rekurencyjne jako polecenie last w funkcji, dzięki czemu nie musi czekać na wywołanie rekurencyjne.

Więc jest to rekurencja ogonowa, tzn. N (x - 1, p * x) jest ostatnim stwierdzeniem w funkcji, gdzie kompilator jest sprytny, aby dowiedzieć się, że można ją zoptymalizować do pętli for (czynnikowej). Drugi parametr p niesie wartość produktu pośredniego.

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

Jest to nie-rekurencyjny sposób zapisu powyższego funkcja czynnikowa (chociaż niektóre kompilatory C++ mogą być w stanie 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 " Understanding Tail Recursion-Visual Studio C++ - Assembly View"

Oto wersja Perla 5 wspomnianej wcześniej funkcji tailrecsum.

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
}

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

Zasadniczo jest to styl programowania taki, że wywołanie rekurencyjne jest ostatnią rzeczą, którą robisz.

Aby zrozumieć niektóre z podstawowych różnic między rekurencją wywołania ogonowego i rekurencją wywołania nie ogonowego, możemy zbadać implementacje tych technik. NET.

Oto artykuł z przykładami w C#, F# i C++\CLI: przygody rekurencji ogonowej w C#, F# I C++ \ CLI.

C#nie optymalizuje rekurencji wywołania ogonowego, podczas gdy F#.

Różnice zasad dotyczą pętli a rachunku Lambda. C# jest zaprojektowany z myślą o pętlach, podczas gdy F# zbudowany jest z zasad rachunku Lambda. Bardzo dobra (i darmowa) książka o zasadach rachunku Lambda znajduje się w: struktura i interpretacja programów komputerowych, autorstwa Abelsona, Sussmana i Sussmana .

Jeśli chodzi o wywołania ogonowe W F#, bardzo dobry artykuł wprowadzający znajduje się w: szczegółowe wprowadzenie do wywołań ogonowych W F#. Na koniec, oto artykuł, który opisuje różnicę między rekurencją nie-ogonową a rekurencją wywołania ogona (w F#): Tail-recursion vs. rekurencja bez ogona w Fi sharp .

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

Jeśli zależy ci na tym, aby wiedzieć, jakie warunki uniemożliwiają kompilatorowi C# wykonywanie optymalizacji wywołań ogonowych, zapoznaj się z tym artykułem: JIT CLR Tail-call conditions.

Jest to fragment struktury i interpretacji programów komputerowych o rekurencji ogonowej.

W kontrastowej iteracji i rekurencji musimy uważać, aby nie mylić pojęcie procesu rekurencyjnego z pojęciem procedura rekurencyjna. Kiedy opisujemy procedurę jako rekurencyjną, jesteśmy odwołując się do faktu składniowego, że definicja procedury odnosi (bezpośrednio lub pośrednio) do samej procedury. Ale kiedy my opisz proces zgodnie z wzorem, który jest, powiedzmy, liniowo rekurencyjnym, mówimy o tym, jak ten proces ewoluuje, a nie o składnia zapisu procedury. Może wydawać się niepokojące, że odnosimy się do procedury rekurencyjnej, takiej jak fact-ITER, jako generującej proces iteracyjny. Jednak proces ten jest naprawdę iteracyjny: jego stan jest całkowicie wychwytywany przez trzy zmienne stanu, a interpreter musi śledzić tylko trzy zmienne, aby wykonaj 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 (m.in. Ada, Pascal i C) są zaprojektowane w taki sposób, aby interpretacja dowolnego rekurencyjnego procedura zużywa ilość pamięci, która rośnie wraz z liczbą wywołania procedury, nawet jeśli opisany proces jest w zasadzie, iteracyjne. W konsekwencji języki te mogą opisywać iteracyjnie procesy tylko poprzez uciekanie się do specjalnego przeznaczenia "konstrukcje pętelkowe" takie jak do, repeat, until, for I while. realizacja Schemat nie ma tej wady. Informatyka przeprowadzi proces iteracyjny w stałej przestrzeni, nawet jeśli proces iteracyjny jest opisany przez procedurę rekurencyjną. Na implementacja z tą właściwością nazywa się tail-recursive. z tail-rekurencyjna implementacja, iteracja może być wyrażona za pomocą zwykły mechanizm wywołania procedury, dzięki czemu specjalna iteracja konstrukty są użyteczne tylko jako cukier składniowy.

Rekurencja ogona to życie, którym teraz żyjesz. Ciągle przetwarzasz tę samą klatkę stosu, ponieważ nie ma powodu ani sposobu na powrót do" poprzedniej " klatki. Przeszłość jest skończona i skończona, więc można ją odrzucić. Dostajesz jedną klatkę, na zawsze przenosząc się w przyszłość, aż twój proces nieuchronnie umrze.

_{analogia załamuje się, gdy weźmiemy pod uwagę, że niektóre procesy mogą używać dodatkowych ramek, ale nadal są uważane za rekurencyjne, jeśli stos nie rosnąć w nieskończoność.}

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

W rekurencji głowicy funkcja wykonuje rekurencyjne wywołanie, a następnie wykonuje kolejne obliczenia, być może wykorzystując wynik na przykład wywołanie rekurencyjne.

W funkcji rekurencyjnej wszystkie obliczenia następują najpierw i wywołanie rekurencyjne jest ostatnią rzeczą, która się wydarzy.

Wzięte z to super zajebiste poczta. Proszę rozważyć przeczytanie go.

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

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

Rekurencja ogonowa oznacza rekurencję kończącą funkcję:

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

Widzisz, ostatnią rzeczą, która nie jest skończona funkcja (procedura, w żargonie Scheme), jest wywołanie samej 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 pomocniczej ostatnią rzeczą, jaką robi, jeśli left nie jest nil, jest wywołanie się (po cons coś i cdr coś). W ten sposób mapujesz listę.

The rekurencja ogonowa ma wielką zaletę, że interperter (lub kompilator, zależny od języka i dostawcy) może ją zoptymalizować i przekształcić w coś równoważnego pętli while. W rzeczywistości, w tradycji Scheme, większość pętli "for" I "while" jest wykonywana w sposób rekurencyjny (nie ma for I while, o ile wiem).

To pytanie ma wiele świetnych odpowiedzi... ale nie mogę pomóc, ale zastanawiam się, jak zdefiniować "rekurencję ogonową", lub przynajmniej " właściwą rekurencję ogonową."Mianowicie: czy należy patrzeć na to jako na właściwość określonego wyrażenia w programie? A może należy spojrzeć na to jako na właściwość implementacji języka programowania?

Aby dowiedzieć się więcej o tym ostatnim widoku, jest klasyczny papier autorstwa Willa Clingera, " właściwa Rekurencja ogonowa i wydajność przestrzeni" (PLDI 1998), który zdefiniował "właściwą rekurencję ogonową" jako właściwość implementacji języka programowania. Definicja jest skonstruowana tak, aby umożliwić ignorowanie szczegółów implementacji (takich jak to, czy stos wywołań jest faktycznie reprezentowany przez stos runtime czy przez powiązaną listę ramek przydzielonych stercie).

Aby to osiągnąć, wykorzystuje analizę asymptotyczną: Nie czasu wykonania programu, jak zwykle widzi się, ale raczej wykorzystanie przestrzeni programu . W ten sposób wykorzystanie przestrzeni heap-alloced linked list vs runtime call stack kończy się asymptotycznie równoważny; 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ę zabłocić wodę, gdy próbuje się ustalić, czy dana implementacja spełnia wymóg bycia "rekurencyjną właściwością ogona")

Praca jest warta uważnego przestudiowania z wielu powodów:

• Daje indukcyjny definicja tail expressions i tail calls programu. (Taka definicja i dlaczego takie rozmowy są ważne, wydaje się być przedmiotem większości innych udzielonych tutaj odpowiedzi.)

  Oto te definicje, aby zapewnić smak tekstu:

  Definicja 1 wyrażenia ogonowe programu napisanego w Core Scheme są indukcyjnie zdefiniowane w następujący sposób.

  1. ciało wyrażenia lambda jest ogonem wyrażenie
  2. Jeśli (if E0 E1 E2) jest wyrażeniem ogonowym, to zarówno E1, jak i E2 są wyrażeniami ogonowymi.
  3. nic innego nie jest wyrażeniem ogona.

  Definicja 2 a wywołanie ogonowe jest wyrażeniem ogonowym, które jest wywołaniem procedury.

(rekurencyjne wywołanie ogonowe, lub jak mówi artykuł, "wywołanie samoogonowe" jest szczególnym przypadkiem wywołania ogonowego, w którym procedura jest wywoływana sama.)

• Zawiera formalne definicje dla sześciu różne "maszyny" do oceny schematu podstawowego, gdzie każda maszyna ma takie samo obserwowalne zachowanie z wyjątkiemdla asymptotycznej klasy złożoności przestrzeni, w której każda jest.

  Na przykład po podaniu definicji dla maszyn z odpowiednio, 1. zarządzanie pamięcią opartą na stosie, 2. zbiórka śmieci, ale bez ogonów, 3. usuwanie śmieci i wywołania ogonowe, artykuł kontynuuje pracę z jeszcze bardziej zaawansowanymi strategiami zarządzania pamięcią masową, takimi jak 4. "evlis rekurencja ogonowa", jeżeli środowisko nie musi być zachowane w trakcie oceny ostatniego argumentu pod-wyrażenia w wywołaniu ogonowym, 5. redukcja otoczenia zamknięcia do tylko wolnych zmiennych tego zamknięcia, oraz 6. tak zwana semantyka "bezpieczna dla przestrzeni" zdefiniowana przez appela i Shao.

• Aby udowodnić, że maszyny rzeczywiście należą do sześciu różnych klas złożoności przestrzeni, papier, dla każdej pary maszyn do porównania, dostarcza konkretnych przykłady programów, które będą eksponować asymptotyczne wysadzenie przestrzeni na jednej maszynie, ale nie na drugiej.

(czytając teraz moją odpowiedź, nie jestem pewien, czy udało mi się uchwycić kluczowe punkty papieru Clinger . Niestety, nie mogę teraz poświęcić więcej czasu na opracowanie tej odpowiedzi.)

Rekurencja ogonowa jest funkcją rekurencyjną, w której funkcja wywołuje się na końcu ("ogonie") funkcji, w której żadne obliczenia nie wykonywane po zwróceniu wywołania rekurencyjnego. Wiele kompilatorów optymalizuje do Zmień wywołanie rekurencyjne na wywołanie rekurencyjne ogonowe lub iteracyjne.

Rozważmy problem obliczania liczby.

Proste podejście byłoby:

  factorial(n):

    if n==0 then 1

    else n*factorial(n-1)

Załóżmy, że wywołujesz factorial (4). Drzewo rekurencyjne be:

       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żmy 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 rekurencyjne dla factTail (4) będzie następujące:

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. Stąd kompilator może pozbyć się stosu.