CODEWITHSUNDEEP
c++ctail-recursion
beta
beta

Reputation: 2550

Is this function really tail-recursive?

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?

Upvotes: 1

Views: 336

Answers (4)

Aatish Sai
Aatish Sai

Reputation: 3

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.

Upvotes: 0

cHao
cHao

Reputation: 86504

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.

Upvotes: 4

Eric Jablow
Eric Jablow

Reputation: 7899

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);
    }
}

Upvotes: 5

taocp
taocp

Reputation: 23634

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)

Upvotes: 1

Related Questions