I’ve been learning about 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.