kekoa vincent

In my Scheme class, we went over how tail recursion allows for nice compiler optimizations.

http://en.wikipedia.org/wiki/Tail_recursion - Great resource

I decided to code up a quick experiment of how this can work. I have a simple recursive add function that will add up all the sequential integers up to and including num. This is also a proof of Pythagoras' tetrad. So if I do add(4) the return will be 1 + 2 + 3 + 4 = 10:

add-recursive.c :

int add(int num) {
   if(num == 0) return 0;
   return (num + add(num - 1));
}

int main(int argc, char** argv) {
   int count;
   if(argc > 1) {
      sscanf(argv[1], "%i", &count);
      printf("Result: %i\n", add(count));
   }
} 

Ok, let's try it out

$ ./add-recursive 4
Result: 10
$ ./add-recursive 100
Result: 5050
$ ./add-recursive 100000
Result: 705082704
$ ./add-recursive 10000000
Segmentation fault

Uh oh. Looks like we overflowed the stack at 10000000. The solution to such a silly problem would be to use tail recursion, which is a special form of recursion where your final operation is a recursive call. Normally, each recursive call will add a stack frame for each call to add(), but since you're only returning the result of the next recursive call, the compiler can re-use the same stack frame, and reload the recursive call onto the same stack frame, thus averting any stack overflow problems.

Here's a modified function that will do the same thing, but allow for the tail recursion optimization.

add-tail-recursive.c :

int add(int num, int count) {
   if(num == 0) return count;
   count += num;
   return add(num - 1, count);
}

int main(int argc, char** argv) {
   int count;
   if(argc > 1) {
      sscanf(argv[1], "%i", &count);
      printf("Result: %i\n", add(count, 0));
   }
}

Here's the new results:

$ ./add-tail-recursive 4
Result: 10
$ ./add-tail-recursive 100
Result: 5050
$ ./add-tail-recursive 100000
Result: 705082704
$ ./add-tail-recursive 10000000
Result: -2004260032 

Hey, we got a result, our integer overflowed, but that's beside the point, we got an answer, which means the recursion ran to completion without a stack overflow.

So, the obvious response is, that's a dumb idea to use recursion for adding like that, you should use a for loop. Yes, I know, I was just trying to test out this tail recursion in hopes that I will one day find a great use for it.

Note that when you compile your C, you'll want to turn on optimizations, I used -O2 for gcc, without that option, it has the same effect of blowing the stack up.