What is tail-recursion elimination?

Question

Steve Yegge mentioned it in a blog post and I have no idea what it means, could someone fill me in?

Is it the same thing as tail call optimization?

Answer 1

Tail call elimination is an optimization that saves stack space. It replaces a function call with a goto. Tail recursion elimination is the same thing, but with the added constraint that the function is calling itself.

Basically, if the very last thing a function A does is return A(params...) then you can eliminate the allocation of a stack frame and instead set the appropriate registers and jump directly into the body of the function.

Consider an (imaginary) calling convention that passes all parameters on the stack and returns the value in some register.

Some function could compile down to (in an imaginary assembly language):

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

Whatever the above actually does, it takes up a whole new stack frame for each call to function. However, since nothing occurs after the tail call to function except a return we can safely optimize that case away.

Resulting in:

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

The end result is an equivalent function that saves a lot of stack space, especially for inputs that result in a large number of recursive calls.

There's a lot of imagination required in my answer, but I think you can get the idea.