Ответ 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
Конечный результат - эквивалентная функция, которая экономит много пространства стека, особенно для входов, которые приводят к большому количеству рекурсивных вызовов.
В моем ответе требуется много воображения, но я думаю, что вы можете получить эту идею.