Tail Recursion in C++ with multiple recursive function calls

Question

I was reading this post on tail recursion.

I'll copy the posted solution:

unsigned int f( unsigned int a ) {
   if ( a == 0 ) {
      return a;
   }
   return f( a - 1 );   // tail recursion
}

I was wondering, what about if the result depends on several recursive function calls? For example:

unsigned int f( unsigned int a ) {
    if ( a == 0 ) {
          return a;
       }
    return f(a -1) + f( a - 1 );   
}

Would the code above be optimized by the compiler?

Answer 1

As it stands, tail recursion doesn't apply. But if you look at the end of the second answer on the question you linked to, you can see how to rewrite the function appropriately. Starting with

unsigned int f( unsigned int a ) {
    if ( a == 0 ) {
          return a;
    }
    return f(a-1) + f(a-1);   
}

rewrite it as follows:

unsigned int f( unsigned int a ) {
    if ( a == 0 ) {
          return a;
    }
    return 2 * f(a-1);  
}

Even now, tail recursion still isn't directly applicable. We need to make sure the return is strictly of the form return f(....). Rewrite the function again:

unsigned int f( unsigned int a, unsigned int multiplicative_accumulator = 1 ) {
    if ( a == 0 ) {
          return multiplicative_accumulator * a;
    }
    return f(a-1, multiplicative_accumulator * 2 );   
}

Now, tail recursion is applicable. This uses a default value for the multiplicative_accumulator (thanks @Pubby) in order that the first call to f can simply be f(x), otherwise you would have to write something f(x,1).

A couple of final notes thanks to @SteveJessop:

• It was safe to change f(a+1)+f(a+1) to 2*f(a+1) because f has no side effects (printing, modifying the heap, that kind of thing). If f did have side effects, that rewrite wouldn't be valid.
• The original was equivalent to (2*(2*(2*a)) (or more precisely, (((a+a)+(a+a))+((a+a)+(a+a)))) whereas the current version is more like (((2*2)*2)*a). This is fine, especially for ints, because multiplication is associative and distributive. But this wouldn't be exact equivalent for float, where you would probably get small rounding discrepancies. With floating point arithmetic, sometimes a*b*c can be slightly different from c*b*a.

Answer 2

The second function is not tail-recursive and can't be easily replaced with a loop, so most probably the compiler won't do so.

Answer 3

This is not a tail recursion (where the result of the function is the result of a recursive call): there is an operation to do after the recursion (the addition). There is a more complex transformation (which depends on the commutativity of addition) to get a tail recursion: add an auxilliary function with an accumulator:

unsigned int f_helper(unsigned int a, unsigned int acc)
{
   if (a == 0) {
      return acc;
   }
   return f_helper(a-1, f(a-1)+acc);
}

unsigned int f(unsigned int a) {
    if (a == 0) {
          return a;
    }
    return f_helper(a-1, f(a-1));
}

which you can transform into a loop

unsigned int f_helper(unsigned int a, unsigned int acc)
{
   while (a != 0) {
      acc += f(a-1);
      a = a-1;
   }
   return acc;
}

unsigned int f(unsigned int a) {
    if (a == 0) {
       return a;
    }
    return f_helper(a-1, f(a-1));
}

then put it back into f

unsigned int f( unsigned int a ) {
  if (a == 0) {
      return a;
   }
   unsigned acc = f(a-1);
   a = a-1;
   while (a != 0) {
      acc += f(a-1);
      a = a-1;
   }
   return acc;
}

Answer 4

I would expect that it won't be optimized, as mentioned by others, but often these types of issues can be resolved by using memoization, which trades off using memory instead of making another recursive call.

For a nice explanation using C++ you can look at http://marknelson.us/2007/08/01/memoization/.

In your example the last call could be replaced with

return 2 * f(a - 1);

and that would be optimizable.

In many cases where it appears that tail-recursion won't work, it may be that you just need to look at your algorithm, and make some changes to help get this optimization.