Tail recursion call (C primer plus book example)

Question

In the C Primer Plus (6th edition), it defines the tail recursion concept in this manner:

In the simplest form of recursion, the recursive call is at the end of the function, just before the return statement. This is called tail recursion, or end recursion, because the recursive call comes at the end. Tail recursion is the simplest form because it acts like a loop.

And it gives an example of calculating the factorial in a tail recursive manner:

long rfact(int n) {
    long ans;
    if (n > 0)
        ans = n * rfact(n - 1);
    else
        ans = 1;
    return ans;
 }

It also makes a side note, which is not true in my opinion:

Note that although the recursive call to rfact() is not the last line in the function, it is the last statement executed when n > 0, so it is tail recursion.

One can clearly see that the last statement is n * rfact(n - 1) which, if you recursively expand, it will lead to a chain of deferred multiplications. The process is recursive in nature, so the implementation cannot be tail recursive as described here.

The example is misleading. What is your opinion?

Answer 1

As far a good C programming book goes, I used the C programming language.

You are correct in saying this is not tail recursion. The typical tail recursion example for a factorial is:

int factorial(int x) {
    return tailfactorial(x, 1);
}

int tailfactorial(int x, int multiplier) {
    if (x <= 0) {
        return multiplier;    
    }    
    return tailfactorial(x - 1, x * multiplier);
}

I imagine that your book did not explain the purpose for tail recursion. Tail recursion is used in order to not increase the "stack depth". The compiler can replace the recursive call with a "goto" command which does not increase the stack depth. This compiler modification is only made when the value of the recursion is returned directly. You will notice in your example that this is not the case.

Answer 2

The given definition and example both are misleading. The definition of tail recursion is:

A function call is said to be tail recursive if there is nothing to do after the function returns except return its value.

It is not not necessary that recursive call should be just before the return statement or last statement of the function. See an example:

function foo(data) {
    a(data);
    return b(data);
} 

In this case a is just before the return statement but b is in tail position.

function bar(data) {
    if ( a(data) ) {
        return b(data);
    }
    return c(data);
}

In this example, both b and c are in tail position though b is not at the end of the function bar.

In your given example, the last thing function is performing before return is multiplication

ans = n * rfact(n - 1);   

Therefore, its not a tail recursive function.

Am example of tail recursive function is

factorial1(n, accumulator) {
    if (n == 0) return accumulator;
    return factorial1(n - 1, n * accumulator);  // The last thing, before return, performed 
                                                // by factorial1 is to call itself. 
  }

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

which may be optimize by compiler to

factorial1(n, accumulator) {
    while (n != 0) {
      accumulator *= n;
      n -= 1;
    }
    return accumulator;
  }