How to recognize what is, and what is not tail recursion?

Question

Sometimes it's simple enough (if the self call is the last statement, it's tail recursion), but there are still cases that confuse me. A professor told me that "if there's no instruction to execute after the self-call, it's tail recursion". How about these examples (disregard the fact that they don't make much sense) :

a) This one should be tail recursive, seeing how the self-call is the last statement, and there's nothing left to execute after it.

function foo(n)
{
    if(n == 0)
        return 0;
    else
        return foo(n-2);
}

b) But how about this one? It should be a tail call, because if the condition is true, nothing except it will be executed, but it's not the last statement?

function foo(n)
{
    if(n != 0)
        return foo(n-2);
    else
        return 0;
}

c) How about this one? In both cases, the self call will be the last thing executed :

function foo(n)
{
    if(n == 0)
        return 0;
    else    
    {
        if(n > 100)
            return foo(n - 2);
        else
            return foo(n - 1);
    }
}

Keil

Answer 1

It might help you to think about this in terms of how tail-call optimisations are actually implemented. That's not part of the definition, of course, but it does motivate the definition.

Typically when a function is called, the calling code will store any register values that it will need later, on the stack. It will also store a return address, indicating the next instruction after the call. It will do whatever it needs to do to ensure that the stack pointer is set up correctly for the callee. Then it will jump to the target address[*] (in this case, the same function). On return, it knows the return value is in the place specified by the calling convention (register or stack slot).

For a tail call, the caller doesn't do this. It ignores any register values, because it knows it won't need them later. It sets up the stack pointer so that the callee will use the same stack the caller did, and it doesn't set itself up as the return address, it just jumps to the target address. Thus, the callee will overwrite the same stack region, it will put its return value in the same location that the caller would have put its return value, and when it returns, it will not return to its caller, but will return to its caller's caller.

Therefore, informally, a function is tail-recursive when it is possible for a tail call optimisation to occur, and when the target of the tail call is the function itself. The effect is more or less the same as if the function contained a loop, and instead of calling itself, the tail call jumps to the start of the loop. This means there must be no variables needed after the call (and indeed no "work to do", which in a language like C++ means nothing to be destructed), and the return value of the tail call must be returned by the caller.

This is all for simple/trivial tail-recursion. There are transformations that can be used to make something tail-recursive which isn't already, for example introducing extra parameters, that store some information used by the "bottom-most" level of recursion, to do work that would otherwise be done on the "way out". So for instance:

int triangle(int n) {
    if (n == 0) return 0;
    return n + triangle(n-1);
}

can be made tail-recursive, either by the programmer or automatically by a smart enough compiler, like this:

int triangle(int n, int accumulator = 0) {
    if (n == 0) return accumulator;
    return triangle(n-1, accumulator + n);
}

Therefore, the former function might be described as "tail recursive" by someone who's talking about a smart enough language/compiler. Be prepared for that variant usage.

[*] Storing a return address, moving the stack pointer, and jumping, may or may not be wrapped up in a single opcode by the architecture, but even if not that's typically what happens.

Ecstatic

Answer 2

Yep; I think your professor meant that in any path, if the final instruction is recursive, then it is tail recursion.

So, all three examples are tail-recursive.

Assyrian

Answer 3

All your functions are tail recursive.

no instruction left after the self-call

means: After the self-call, you return from the function, i.e. no more code has to be executed, and not that there is no more line of code in the function.

Tailored

Answer 4

All three examples are tail recursive. Generally speaking, it is tail recursion, if the result of the function (the expression following the "return" keyword) is a lone call to the function itself. No other operator must be involved in the outermost level of the expression. If the call to itself is only a part of an expression then the machine must execute the call but then has to return back into the evaluation of said expression, that is, it was not at the tail of the function execution but in the middle of an expression. This however does not apply to any parameters that the recursive call may take: anything is allowed there, including recursive calls to itself (e.g. "return foo(foo(0));"). The optimization of calls to jumps is only possible for the outer call then, of course.

Pollination