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?

Gamboa

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.

Bigler

So is this the same thing as tail call optimization? – Gamboa

Yeah, just with the added constraint that the call is to the function in which it originates. Sorry that isn't perfectly clear. – Bigler

Answer 2

from here:

"...Tail recursion elimination is a special case of tail call elimination in which the tail call is a call to the function itself. In that case the call can be replaced by a jump to the start of the function after moving the new arguments to the appropriate registers or stack locations..."

from Wikipedia:

"...When a function is called, the computer must "remember" the place it was called from, the return address, so that it can return to that location with the result once the call is complete. Typically, this information is saved on the stack, a simple list of return locations in order of the times that the call locations they describe were reached. Sometimes, the last thing that a function does after completing all other operations is to simply call a function, possibly itself, and return its result. With tail recursion, there is no need to remember the place we are calling from — instead, we can leave the stack alone, and the newly called function will return its result directly to the original caller. Converting a call to a branch or jump in such a case is called a tail call optimization. Note that the tail call doesn't have to appear lexically after all other statements in the source code; it is only important that its result be immediately returned, since the calling function will never get a chance to do anything after the call if the optimization is performed...."

Bergerac