Rekurencja ogonowa: Różnice pomiędzy wersjami

Dodane 25 bajtów ,  11 lat temu
m
WP:SK, poprawa linków
m (drobne redakcyjne)
m (WP:SK, poprawa linków)
'''Rekursja ogonowa''' (albo '''rekurencja prawostronna''') to [[Rekurencja|rekursja]], po której nie następuje już powrót do [[podprogram|funkcji]]. Stosując taką rekursję można w ogóle nie używać stosu - jest równie wydajna jak [[programowanie imperatywne|imperatywna]] [[pętla (informatyka)|pętla]].
 
Często funkcja wykorzystująca rekursję ogonową ma dwa argumenty - właściwy argument oraz dotychczasowy wynik. Jako warunek bazowy ma zwrócenie dotychczasowego wyniku jako wyniku ostatecznego. Np. ([[OCaml]]):
 
Obliczenia które zachodzą dla <tt>suma 0 [1;2;3;4]</tt> to:
: <tt>suma 0 [1;2;3;4]</tt> - wywołanie funkcji
: <tt>suma 0 1::[2;3;4]</tt> - [[dopasowanie do wzorca]]
: <tt>suma (1+0) [2;3;4]</tt> - obliczenie wyrażenia
: <tt>suma 1 [2;3;4]</tt> - rekursja ogonowa
: <tt>suma 1 2::[3;4]</tt> - [[dopasowanie do wzorca]]
: <tt>suma (2+1) [3;4]</tt> - obliczenie wyrażenia
: <tt>suma 3 [3;4]</tt> - rekursja ogonowa
: <tt>suma 3 3::[4]</tt> - [[dopasowanie do wzorca]]
: <tt>suma (3+3) [4]</tt> - obliczenie wyrażenia
: <tt>suma 6 [4]</tt> - rekursja ogonowa
: <tt>suma 6 4::[]</tt> - [[dopasowanie do wzorca]]
: <tt>suma (4+6) []</tt> - obliczenie wyrażenia
: <tt>suma 10 []</tt> - przypadek bazowy
: <tt>10</tt> - koniec obliczeń
 
[[Kategoria:Rekursja]]
54 501

edycji