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

Viewed 1686

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);
    }
}
4 Answers
Related