Rekurencja ogonowa

Rekurencja ogonowa (rekurencja prawostronna, ang. tail call) – rodzaj rekurencji, w której ostatnia operacja wykonywana przez funkcję to rekurencyjne wywołanie samej siebie lub zwrócenie końcowego wyniku^[1]. Taka funkcja może zostać łatwo zamieniona na iterację, zarówno ręcznie, jak i automatycznie, co redukuje wielkość stosu oraz zwiększa wydajność. Ta technika iteracyjnego wykonywania obliczeń jest powszechna w programowaniu funkcyjnym promującym używanie rekurencji, która w przeciwnym wypadku zajęłaby cały dostępny stos.

Opis

Wywołanie funkcji z danego kawałka kodu oznacza dla komputera wykonanie skoku w inne miejsce. Zanim go wykona, musi zapamiętać m.in. adres powrotu, wartości rejestrów oraz zmiennych. Najczęściej wykorzystywana jest do tego struktura danych zwana stosem, w której przechowywane są informacje o wszystkich aktualnie wykonywanych funkcjach zgodnie z kolejnością ich zagnieżdżenia, przy czym każda funkcja zajmuje pojedynczą ramkę stosu. Każdy program rezerwuje na potrzeby stosu ściśle określoną ilość pamięci, co narzuca ograniczenie na maksymalną ilość zagnieżdżonych wywołań funkcji. W przypadku niektórych funkcji ostatnia wykonywana w nich operacja przed zwróceniem wyniku to wywołanie innej funkcji (w szczególności – siebie samej), bez wykonywania żadnych dodatkowych obliczeń^[2]. W tym przypadku zapamiętywanie adresu powrotu oraz stanu na stosie jest zbędne, ponieważ nie jest on już potrzebny. Takie wywołanie nazywa się wywołaniem ogonowym (ang. tail call)^[3] i może zostać zoptymalizowane zastąpieniem wywołania przez zwykłą instrukcję skoku.

Optymalizacja wywołań ogonowych może być stosowana do zwykłych, nierekurencyjnych funkcji, pozwalając na zaoszczędzenie odrobiny czasu i pamięci, a także zmniejszając zapotrzebowanie na stos. Funkcje rekurencyjne mogą wywoływać siebie bardzo dużą liczbę razy, a w szczególnych przypadkach potencjalnie w nieskończoność. Wielkość stosu jest fizycznie ograniczona z góry przez zasoby komputera. Optymalizacja ogonowa sprawia, że rekurencyjne wywołanie może korzystać z już istniejącej ramki, przez co zapotrzebowanie na stos maleje z liniowego O(n) do stałego O(1).

Przykład

Rozważmy przykład obliczania silni w języku Ocaml. Klasyczny program rekurencyjny będzie wyglądał następująco:

let rec silnia n =
  if n = 0 then
    1
  else
    n * silnia (n - 1)
;;

Nie korzysta on z rekurencji ogonowej, przez co obliczenie od strony interpretera będzie wyglądać następująco:

Wywołaj silnia(3)
  Wywołaj silnia(2)
    Wywołaj silnia(1)
      Wywołaj silnia(0)
      Zwróć 1
    Zwróć 1
  Zwróć 2
Zwróć 6

Możemy wprowadzić tutaj rekurencję ogonową, zauważając że w przypadku mnożenia kolejność wykonywania obliczeń nie gra żadnej roli. Stworzymy zatem funkcję pomocniczą, z dodatkowym argumentem (akumulatorem), w którym do kolejnych wywołań będzie przekazywany aktualny wynik. Gdy licznik dojdzie do zera, funkcja zwróci wartość akumulatora jako wynik końcowy:

let rec sil n acc =
  if n = 0 then
    acc
  else
    sil (n-1) (n*acc)
;;

let rec silnia n =
  sil n 1
;;

Działanie programu będzie wyglądać następująco:

Wywołaj silnia(3)
  Wywołaj sil(3,1)
  Zastąp argumenty (3,1) przez (2,3), skocz na początek sil
  Zastąp argumenty (2,3) przez (1,6), skocz na początek sil
  Zastąp argumenty (1,6) przez (0,6), skocz na początek sil
  Zwróć 6 jako wynik
Zwróć 6

Zobacz też

derekursywacja

Przypisy

↑ Tail recursion. HaskellWiki on haskell.org. [dostęp 2010-10-11]. (ang.).
↑ Steven S. Muchnick: Advanced compiler design and implementation. Morgan Kaufmann, 1997, s. 461. ISBN 978-1558603202.
↑ John C. Mitchell: Concepts in programming languages. Cambridge University Press, 2003, s. 180. ISBN 978-0521780988. (ang.).

Bibliografia

Joshua B. Smith: Practical Ocaml. Apress, 2006. ISBN 978-1590596203.

[1] Tail recursion. HaskellWiki on haskell.org. [dostęp 2010-10-11]. (ang.).

[2] Steven S. Muchnick: Advanced compiler design and implementation. Morgan Kaufmann, 1997, s. 461. ISBN 978-1558603202.

[3] John C. Mitchell: Concepts in programming languages. Cambridge University Press, 2003, s. 180. ISBN 978-0521780988. (ang.).

[1]

[2]

[3]