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

Ответ 1

Исключение вызова хвоста - это оптимизация, которая экономит пространство стека. Он заменяет функцию вызов на 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

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

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

Ответ 2

из здесь:

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

из Wikipedia:

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