CODEWITHSUNDEEP
recursiontail-recursion
Giorgio Mossa
Giorgio Mossa

Reputation: 245

Problems understanding if the following is a tail-recursive function

Quoting from wikipedia

...a tail call is a subroutine call performed as the final action of a procedure. If a tail call might lead to the same subroutine being called again later in the call chain, the subroutine is said to be tail-recursive, which is a special case of recursion.

Now I've the following routine written in C

 int foo (int x){
      if ( x > 100)
          return x-10;
      else 
          return foo(foo(x+11));
 }

Based on the definition above, it seems to me that foo should be a tail recursive function since it recursive call is the final action of the procedure, but somewhere I've once read that this is not a tail recursive function.

Hence the question:

why isn't this function tail-recursive?

Upvotes: 1

Views: 39

Answers (1)

Philipp Wendler
Philipp Wendler

Reputation: 11423

This function is typically not considered tail-recursive, because it involves multiple recursive calls to foo.

Tail recursion is particularly interesting because it can be trivially rewritten (for example by a compiler optimization) into a loop. It is not possible to completely eliminate recursion with this tail-call-optimization technique in your example, and thus one would not consider this function as tail-recursive, even if its last statement is a recursive call.

Upvotes: 1

Related Questions