Feb. 10, 2009 8:10 p.m.

I’ve been learning about how tail recursion allows for nice compiler optimizations. I decided to code up a quick experiment of how this works.

First, check out the great Wikipedia article on Tail Recursion. 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:

```
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.

```
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.

comments powered by Disqus