Что такое устранение хвостовой рекурсии?
Добавить к ответу, в книге Языка программирования C (K& RC) они дали небольшой пример о том, как пойти о реализации ls. Они объяснили datastructures и функции, используемые очень хорошо.
2 ответа
Устранение хвостового вызова - это оптимизация, которая экономит пространство стека. Он заменяет вызов функции на 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
Что бы ни случилось на самом деле выше, для каждого вызова функции требуется целый новый кадр стека. Однако,
из здесь :
"... Устранение хвостовой рекурсии - это частный случай исключения хвостового вызова в котором хвостовой зов - это призыв к сама функция. В этом случае вызов можно заменить переходом на запуск функции после перемещения новые аргументы в пользу соответствующих регистры или расположение стека ... "
из Википедия :
" ... Когда функция вызывается, компьютер должен «запомнить» место, откуда она была вызвана, адрес возврата, чтобы он мог вернуться в это место с результатом после завершения вызова. Как правило, эта информация сохраняется в стеке, в виде простого списка мест возврата в порядке времени достижения описываемых ими точек вызова. Иногда последнее, что делает функция после завершения всех других операций, - это просто вызывает функцию, возможно, саму себя, и возвращает ее результат. При хвостовой рекурсии нет необходимости запоминать место, из которого мы вызываем - вместо этого мы можем оставить стек в покое, и вновь вызванная функция вернет свой результат непосредственно исходному вызывающему. Преобразование вызова в переход или переход в таком случае называется оптимизацией хвостового вызова. Обратите внимание, что хвостовой вызов не обязательно должен появляться лексически после всех других операторов в исходном коде; важно только, чтобы результат был немедленно возвращен, поскольку вызывающая функция никогда не получит возможности что-либо сделать после вызова, если оптимизация будет выполнена .... "