Czym jest eliminacja rekurencji ogonowej?

Eliminacja wywołań ogonowych to optymalizacja, która oszczędza miejsce na stosie. Zastępuje ona funkcję wywołania z goto . Eliminacja rekurencji ogonowej to to samo, ale z dodanym ograniczeniem, które Funkcja sama wywołuje.

Zasadniczo, jeśli ostatnią rzeczą, jaką robi Funkcja A jest return A(params...), możesz wyeliminować alokację ramki stosu i zamiast tego ustawić odpowiednie rejestry i przejść bezpośrednio do ciała funkcji.

Rozważmy (urojona) konwencja wywołująca, która przekazuje wszystkie parametry na stosie i zwraca wartość w jakimś rejestrze.

Niektóre funkcje mogą skompilować się do (w wyimaginowanym języku asemblacji):

function:
//Reading params B, C, & D off the stack
pop B
pop C
pop D
//Do something meaningful, including a base case return
...
//Pass new values for B, C, & D to a new invocation of function on the stack
push D*
push C*
push B*
call function
ret

Cokolwiek powyższe faktycznie robi, zajmuje zupełnie nową ramkę stosu dla każdego wywołania funkcji. Ponieważ jednak po wywołaniu funkcji ogonowej nic się nie dzieje, z wyjątkiem powrotu, możemy bezpiecznie zoptymalizować ten przypadek.

W wyniku:

function:
//Reading params B, C, & D off the stack (but only on the first call)
pop B
pop C
pop D
function_tail_optimized:
//Do something meaningful, including a base case return
...
//Instead of a new stack frame, load the new values directly into the registers
load B, B*
load C, C*
load D, D*
//Don't call, instead jump directly back into the function
jump function_tail_optimized

Efektem końcowym jest równoważna funkcja, która oszczędza dużo miejsca na stosie, szczególnie dla wejść, które powodują dużą liczbę wywołań rekurencyjnych.