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

Question

Стив Йегге упомянул об этом в своем блоге, и я понятия не имею, что это значит, кто-то может меня заполнить?

Это то же самое, что оптимизация хвостового вызова?

Answer 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

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

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

Answer 2

отсюда:

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

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

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