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