Is this function really tail-recursive?

1
votes

I read about recursion in Programming Interviews Exposed (3rd ed.) where they present the following recursive factorial function:

int factorial(int n){
    if (n > 1) { /* Recursive case */
        return factorial(n-1) * n;
    } else {     /* Base case */
        return 1;
    }
}

On the bottom of the same page (page 108) they talk about tail-recursive functions:

Note that when the value returned by the recursive call is itself immediately returned, as in the preceding definition for factorial, the function is tail-recursive.

But is this really the case here? The last call in the function is the * call, so won't this stack frame be preserved (if we don't take compiler optimization into account)? Is this really tail-recursive?

4
c++ctail-recursion
This function is indeed not tail-recursive. - Cory Nelson
The naive recursive implementation of factorial is the classic example of a recursive function that is not tail-recursive, often used to illustrate how to obtain tail-recursion by use of an accumulator ... I suggest that you get yourself a different book. - Jim Balter
You write "so won't this stack frame be preserved (if we don't take compiler optimization into account)" -- but compiler optimization is irrelevant for this function, because the stack frame cannot be eliminated ... precisely because the function isn't tail-recursive. A function that is tail-recursive, so the stack frame can be eliminated by an optimizing compiler, is given by Eric Jablow. The optimization isn't all that important for C C++, but is essential for functional language like F# and Haskell, where loops are normally implemented recursively. - Jim Balter
@JimBalter: So I take it that no compiler would optimize it to use an accumulator and thus make it tail-recursive? (Actually, that does sound a bit overreaching, now that I think about it…) - beta
I doubt it, as such a rewrite can be arbitrarily complex, depending on the function. - Jim Balter

4 Answers

4
votes

No, it's not tail-recursive. The result being returned by factorial(n-1) still has to be multiplied by n, which requires that factorial(n) regain control (thus mandating that the call to factorial(n-1) be a call rather than a jump).

With that said, even if it were tail-recursive, the compiler still might not do TCO on it. Depends on the compiler and the optimizations that you ask it to do.

5
votes

You can rewrite it to be tail-recursive:

int factorial(int n){
    return factorial2(n, 1);
}
int factorial2(int n, int accum) {
    if (n < 1) {
       return accum;
    } else {
        return factorial2(n - 1, accum * n);
    }
}
1
votes

Quoting from this link: tail recursion using factorial as example

 factorial(n) {
    if (n == 0) return 1;
    return n * factorial(n - 1);
 }//equivalent to your code

 This definition is NOT tail-recursive since the recursive call to 
 factorial is not the last thing in the function 
 (its result has to be multiplied by n)
0
votes

Tail Recursive is a special case of recursion in which the last operation of the function is a recursive call. In a tail recursive function, there are no pending operations to be performed on return from a recursive call. The function you mentioned is not a tail recursive because there is a pending operation i.e multiplication to be performed on the return from a recursive call. In case you did this:

    int factorial(int n,int result)
    {
        if (n > 1)
        { /* Recursive case */
             return factorial(n-1,n*result);
        }
        else
        {     /* Base case */
            return result;
        }
    }

would be a tail recursive function. since it has no pending operation on return from a recursive call.