Does gcc optimize recursive functions? How to do it? [closed]

Question

I found a interesting quize today about gcc http://ridiculousfish.com/blog/posts/will-it-optimize.html

How come this code

int factorial(int x) {
   if (x > 1) return x * factorial(x-1);
   else return 1;
}

can be translated by compiler into

int factorial(int x) {
   int result = 1;
   while (x > 1) result *= x--;
   return result;
}

Is this true? How gcc does it?

Answer 1

You already know that gcc can optimize a tail-recursive function into a loop. The other thing that gcc can do (and is mentioned in your link) is try to optimize a non-tail-recursive function into a tail-recursive function.

Your factorial function is here:

int factorial(int x) {
   if (x > 1) return x * factorial(x-1);
   else return 1;
}

Now I'm going to try to make as few changes as possible and rewrite this as tail-recursive. First, I'll flip the if test:

int factorial(int x) {
   if (!(x > 1)) return 1;
   else return x * factorial(x-1);
}

Next, I'll remove the unneeded else:

int factorial(int x) {
   if (!(x > 1)) return 1;
   return x * factorial(x-1);
}

This is almost tail-recursive, but it is returning x * factorial() and not just factorial(). The typical way to make this tail recursive is to include a second parameter, which is an accumulator.

int factorial(int x, int accumulator = 1) {
   if (!(x > 1)) return accumulator;
   return factorial(x - 1, x * accumulator);
}

Now this is a tail-recursive function, and it can be optimized into a loop.