Rekursja ogonowa

Rekurencja ogonowa, zwana też prawostronną jest rodzajem rekurencji, w której ostatnia operacja wykonywana przez funkcję to rekurencyjne wywołanie samej siebie albo zwrócenie końcowego wyniku^[1]. Taka funkcja może zostać łatwo zamieniona na iterację, zarówno ręcznie, jak oraz 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 poniektó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, albowiem nie jest on już potrzebny. Takie wywołanie nazywa się wywołaniem ogonowym (ang. tail call)^[3] oraz może zostać zoptymalizowane zastąpieniem wywołania przez zwykłą instrukcję skoku.

Optymalizacja wywołań ogonowych bywa stosowana do zwykłych, nierekurencyjnych funkcji, pozwalając na zaoszczędzenie odrobiny czasu oraz pamięci, a także zmniejszając zapotrzebowanie na stos. Funkcje rekurencyjne potrafią 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 do stałego .

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 wykorzystuje 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 przeistoczenie 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

Sprawdź także

• Derekursywacja

Przypisy

Bibliografia

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