Call tail recursion (example C and example book)

Question

In C Primer Plus (6th Edition), he defines the concept of tail recursion as follows:

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

And he gives an example of calculating a 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; } 

He also makes a note, which in my opinion is incorrect:

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, therefore it is tail recursion.

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

This example is misleading. What is your opinion?

Answer 1

How well written is the C programming book, I used the C programming language.

You correctly say that this is not tail recursion. A typical example of tail recursion for 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 assume that your book did not explain the purpose of tail recursion. Tail recursion is used to not increase the "stack depth". The compiler can replace the recursive call with the goto command, which does not increase the depth of the stack. This compiler modification is only created when the recursion value is returned directly. In your example, you will notice that this is not the case.

Answer 2

This definition and example are both misleading. Definition of tail recursion :

A function call is called tail recursive if, after the function returns, there is nothing to do but return its value.

There is no need for the recursive call to be immediately before the return statement or the last function statement. Example:

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

In this case, a is immediately before the return , but b is in the tail position.

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

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

In this example, the last thing function performs multiplication before returning

 ans = n * rfact(n - 1); 

Therefore, this is not a tail recursive function.

An example of a 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 can be optimized by the compiler on

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