Что такое устранение хвостовой рекурсии?

Устранение хвостовых вызовов — это оптимизация, которая экономит место в стеке. Он заменяет функцию вызов на goto. Устранение хвостовой рекурсии — это то же самое, но с добавленным ограничением, что функция вызывает сама себя.

По сути, если самое последнее, что делает функция A, это return A(params...), то вы можете отказаться от выделения кадра стека и вместо этого установить соответствующие регистры и перейти непосредственно к телу функции.

Рассмотрим (воображаемое) соглашение о вызовах, которое передает все параметры в стек и возвращает значение в некотором регистре.

Некоторая функция может быть скомпилирована (на воображаемом языке ассемблера):

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

Что бы на самом деле ни делал вышеприведенный код, он занимает совершенно новый кадр стека для каждого вызова функции. Однако, поскольку после хвостового вызова функции ничего не происходит, кроме возврата, мы можем безопасно оптимизировать этот случай.

В результате чего:

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

Конечным результатом является эквивалентная функция, которая экономит много места в стеке, особенно для входных данных, которые приводят к большому количеству рекурсивных вызовов.

В моем ответе требуется много воображения, но я думаю, вы можете понять идею.

из здесь:

"...Устранение хвостовой рекурсии - это частный случай исключения хвостового вызова, в котором хвостовой вызов является вызовом самой функции. В этом случае вызов может быть заменен переходом к началу функции после перемещения новых аргументов. в соответствующие регистры или места в стеке..."

из Википедии:

"...Когда вызывается функция, компьютер должен "запомнить" место, откуда она была вызвана, обратный адрес, чтобы он мог вернуться в это место с результатом после завершения вызова. Обычно эта информация сохраняется. в стеке простой список мест возврата в порядке времени, когда были достигнуты места вызова, которые они описывают.Иногда последнее, что делает функция после завершения всех других операций, — это просто вызывает функцию, возможно, саму себя, и возвращает его результат. При хвостовой рекурсии нет необходимости запоминать место, откуда мы вызываем — вместо этого мы можем оставить стек в покое, и вновь вызванная функция вернет свой результат непосредственно исходному вызывающему объекту. Преобразование вызова к переходу или переходу в таком случае называется оптимизацией хвостового вызова. Обратите внимание, что хвостовой вызов не обязательно должен лексически появляться после всех других операторов в исходном коде; важно только, чтобы его результат был немедленно вернулся, так как калли ng никогда не сможет что-либо сделать после вызова, если оптимизация будет выполнена...."