Is the tail-recursion example really tail-recursive?

beta · April 24th, 2013, 06:14 PM

On page 108 you first present this function:

Code:

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

You then write:

Quote:

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, the call to factorial is not immediately returned, it has to wait for it to be multiplied with n and can thus not discard this stack frame, as far as I can tell...

EricGiguere · April 26th, 2013, 07:19 AM

You are correct, that example is not really an example of tail recursion. For it to be true tail recursion it would have to call itself as the very last operation and do nothing else.

You can make it tail recursive by splitting it into two functions:

Code:

int factorial(int n){
    return factorial(n, 1);
}

int factorial(int n, int counter){
    if( n == 0 ){
        return counter;
    }
    return factorial(n-1, n * counter);
}

(Well, technically you only need the second function -- the first is a convenience function.)