Rekurencja ogonowa: Różnice pomiędzy wersjami

'''Rekurencja ogonowa''', zwana też '''prawostronną''' jest rodzajem [[Rekurencja|rekurencji]], w której ostatnia operacja wykonywana przez [[Funkcja|funkcję]] to rekurencyjne wywołanie samej siebie lub zwrócenie końcowego wyniku<ref>{{cytuj stronę | url = http://www.haskell.org/haskellwiki/Tail_recursion | tytuł = Tail recursion | opublikowany = [http://www.haskell.org/haskellwiki/Haskell HaskellWiki on haskell.org] | data dostępu = 2010-10-11 | język = en}}</ref>. Taka funkcja może zostać łatwo zamieniona na iterację, zarówno ręcznie, jak i automatycznie, co redukuje wielkość [[Stos (informatyka)|stosu]] oraz zwiększa wydajność. Ta technika iteracyjnego wykonywania obliczeń jest powszechna w [[Programowanie funkcyjne|programowaniu funkcyjnym]] promującym używanie rekurencji, która w przeciwnym wypadku zajęłaby cały dostępny stos.

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 [[Stos (informatyka)|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ń<ref>{{cytuj książkę | tytuł = Advanced compiler design and implementation | autor = Steven S. Muchnick | wydawca = Morgan Kaufmann | rok = 1997 | strony = 461 | isbn = 978-1558603202}}</ref>. 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'')<ref>{{cytuj książkę | tytuł = Concepts in programming languages | autor = John C. Mitchell | rok = 2003 | wydawca = Cambridge University Press | język = en | isbn = 978-0521780988 | strona = 180}}</ref> i może zostać zoptymalizowane zastąpieniem wywołania przez zwykłą instrukcję skoku.