Tak w prostych przystępnych słowach co to jest ta cała rekurencja ogonowa. Wiem że jest wykorzystywana jakaś dodatkowa zmienna, która powoduje że stos wywołań pozostaje taki sam. Ale jak to dokładnie działa?
0
3
Ale co chcesz wiedzieć i po co chesz wiedzieć?
Opis matematyczny rekurencji ogonowej nie mówi jak ma być zrobiona ta optymalizacja. Mówi że ma być zrobiona, dzięki czemu nie marnujemy stosu. To już problem inzynierów tworzących kompilator/interpreter żeby to zrobili.
W praktyce rezultatem jest odpowiednik pętli do while z języków imperatywnych (skok wstecz pod pewnym warunkiem). Dlatego języki funkcyjne mające rekurencje ogonową nie potrzebują pętli, co jest przydatne bo matematycy nie rozumieją idei pętli za to świetnie rozumieją ideę rekurencji.
Co jest po między tj miedzy ideą rekurencji ogonowej a petlą do while, Czyli jak wygląda to przekształcenie w kompilatorze jest pewnie w tutorialach do pisania kompilatorów języków funkcyjnych. Czytałem, jeszcze nie użyłem i jeszcze nie zrozumiałem :(
2
Jak wyżej, to jest optymalizacja robiona przez kompilator, w przypadku, gdy wywołanie rekurencyjne jest w funkcji ostatnie (sygnal dla komplatora), to reużywana jest jedna ramka stosu, jak, while, prosty przykład, silnia (acc - accumulator):
def fact_recur(n):
if n == 0:
return 1
return n * fact_recur(n - 1)
def fact_iter(n):
def helper(n, acc):
if n == 0:
return acc
return helper(n - 1, acc * n)
return helper(n, 1)
0
.
0
Ok, ale jak to nie optymalizacja, przecież powyższy kod będzie działał w zależności od języka; w Pythonie, czy Javie, dla odpowiednio dużych liczb rozwali stos, w, np. Clojure, Scheme nie - bo ich kompilatory wspierają TCO (optymalizują odpowiednio napisany kod).
0
.
2
@vpiotr: @lion137 może nie schodźmy na rozmowy o nazewnictwo, albo na kategoryzowanie. Coś mi się zdaje że nic dobrego z tego nie wyjdzie.
3
Zwykła rekurencja to funkcja, która wywołuje samą siebie po czym po tym wywołaniu coś się może dziać dalej. Rekurencja ogonowa to taka rekurencja, gdy po powrocie z wywołania nic się nie dzieje a więc można nie wracać. Normalna rekurencja musi trzymać kontekst danego wywołania jako stos, co może być problematyczne np. każde wywołanie wymaga 1kb pamięci: wystarczy milion takich wywołań i mamy gigabajt pamięci z głowy. Rekurencja ogonowa nie musi trzymać tego kontekstu, bo po co jak i tak nie będzie użyty (bo wywołanie to ostatnia instrukcja) https://en.wikipedia.org/wiki/Tail_call
0
Bo mnie właśnie interesuje ta rekurencja ogonowa w kontekście stosu wywołań. Bo w tradycyjnej rekurencji kiedy przypadek bazowy nie został spełniony, wywoływany jest przypadek rekurencyjny, który wywołuje na stosie kolejne kopie funkcji pierwotnej do momentu kiedy zostanie wywołana kopia z argumentem 0 czyli kopia, która spełniła przypadek bazowy, a następnie przekazuje go do kopii przez, którą została wcześniej wywołana i tak do momentu aż dojdzie się do kopii, która została wywołana przez funkcje pierwotną jako pierwsza, i w tym momencie ta kopia przekazuje do "oryginalnej" funkcji czyli funkcji pierwotnej ostateczny wynik. Natomiast w rekurencji ogonowej jak mam rozumieć nie ma czegoś takiego jak powrót tylko problem jest rozwiązywany w momencie kiedy zostanie wywołana kopia funkcji pierwotnej z argumentem 0. Czyli w rekurencji tradycyjnej kopia funkcji pierwotnej zwraca wynik wywołania do kopii przez którą została wcześniej wywołana, natomiast w rekurencji ogonowej nie ma żadnych "powrotów"?
0
Nie no, jak jest wywołanie funkcji to na stosie musi odłożyć się ramka. Rekurencja ogonowa polega na tym, że kompilator jest w stanie zoptymalizować kod w taki sposób, że zamiast calla jest pętla. W Scali np. trzeba było oznaczać taka metodę dodatkowa adnotacja jako informacja dla kompilatora. W Javie z kolei nie ma czegoś takiego. Procesor nie rozumie czegoś takiego jak rekurencja ogonowa.
3
piotrek1998 napisał(a):
natomiast w rekurencji ogonowej nie ma żadnych "powrotów"?
Tak, w rekurencji ogonowej nie ma powrotów i dodatkowych alokacji na stosie. Za wyjątkiem pierwszej alokacji i jednego powrotu na koniec. A wszystkie dalsze calle są zamieniane na pętle. Na tym polega cała ta optymalizacja.
A żeby jeszcze bardziej namieszać powiem że rekurencja ogonowa jest szczególnym przypadkiem Continuation-passing style. CPS jest to koncepcja takiej kompilacji języków funkcyjnych że stos powrotów w ogóle nie jest potrzebny, bo reszta kodu do wykonania jest przekazywana jako lambda (kontynuacja). W rezultacie kod
val someValue = someFunction1(1)
somefunction2(2, someValue)
Jest zamieniany na coś w rodzaju
someFunction1(1, someValue => somefunction2(2, () => theRestOfTheProgram)
Wszystkie calle zamieniają się na proste skoki i ogólnie dzieją się cuda których dalej nie rozumiem a kiedyś chciałbym zrozumieć
3
Wiem że jest wykorzystywana jakaś dodatkowa zmienna, która powoduje że stos wywołań pozostaje taki sam
Chyba mowisz o jakims accumulatorze. To jest kwestia techniczna, czasami sie dodaje wlasnie taka zmienna pomocnicza zeby wyoptymalizowac rekurencje, ktora normalnie nie jest ogonowa do ogonowej (przyklad: silnia). Ale nie zawsze potrzebujesz accumulatora zeby miec tailrec. I nie zawsze accumulator w ogole cos da :) vide chodzenie po drzewach
1
Piszę ręcznie, bez testów, więc mam nadzieję, że bez błędów, ale może się przyda:
nieogonowa_silnia:
cmp rdi, 2
jl ret_base_case
push rdi ; zwiększa użycie stosu
dec rdi
call nieogonowa_silnia ; zwiększa użycie stosu
pop rdi
imul rax, rdi
ret
ret_base_case:
mov rax, 1
ret
nieogonowa_silnia_akumulator:
mov rdi, rdi ; zbędne, ale dla klarowności
mov rsi, 1
call nieogonowa_silnia_akumulator_helper
mov rax, rax ; j.w.
ret
nieogonowa_silnia_akumulator_helper:
cmp rdi, 2
jl ret_base_case
imul rsi, rdi
dec rdi
call nieogonowa_silnia_akumulator_helper ; zwiększa użycie stosu
mov rax, rax ; j.w.
ret
ret_base_case:
mov rax, rsi
ret
ogonowa_silnia:
mov rdi, rdi
mov rsi, 1
jmp ogonowa_silnia_helper
ogonowa_silnia_helper:
cmp rdi, 2
jl ret_base_case
imul rsi, rdi
dec rdi
jmp ogonowa_silnia_helper
ret_base_case:
mov rax, rsi
ret
Czyli jedyne co się zmienia, to zamiana zbytecznej sekwencji call, ret (bo mov rax, rax jest zbędne) na po prostu skok (jmp). Kto uważniejszy, zauważy że to wygląda po prostu jak pętla. Ale nic bardziej mylnego, to że pętle tak samo wyglądają, to jest kwestia wtórna!