Good recursion, bad recursion

"Go to the store, buy some more, 99 bottles of beer on the wall!" - 99 Bottles of Beer

Factorials are a common math problem used in computer programming tutorials. For those who don't remember them from 5th grade math class, factorials are integers followed by an exclamation mark. You multiply the number by all the numbers that come before it, down to 1. They go thusly:

1! = 1
2! = 2 * 1 = 2
3! = 3 * 2 * 1 = 6
4! = 4 * 3 * 2 * 1 = 24
...etc

Another way of expressing this same idea is with recursion. Recursion is basically self-reference in an expression. Let's use the euphemism "Same shit, different day" to illustrate:

shit(day) = shit(day - 1)


Today's shit is the same as yesterdays shit, and by implication of the above function, the day before that also had the same shit, as did all other days before, and all to come. Bleak. And also an infinite loop, which is bad. Q) "How much shit was there at the beginning?" A) "The same as the day before that."

A way out of that is known as a base case. To prevent infinite recursion, you define at least one value for the function's variable (day) that returns directly, with no self-reference. Like so:

shit(1) = S,
for all other integers n, shit(n) = shit(n-1)

Still bleak, but a better definition. For factorials, we can define them with a base case and a recursive definition:

factorial(1) = 1,
for all other integers n, factorial(n) = n * factorial(n - 1)

Here is what the answers from above look like under the new definition:

1! = 1, this is our base case
2! = 2 * 1! = 2, two times the previous factorial
3! = 3 * 2! = 6, three times the previous
4! = 4 * 3! = 24, four time the last one

So that's recursion and factorials. In my new favorite book, Coders at Work, I stumbled on some techie things that I had never heard of, so I went on a Wikipedia hunt to fill my knowledge gap. Along the way I read through the article on tail recursion, which asserted that using an accumulator in a recursive function could help your compiler avoid ending up knee-deep in stack usage, hence speeding things up and avoiding a possible stack overrun error.

The stack is where a running program records things about functions: local variables, what memory address to jump back to once you're finished, etc. How it works is mad science, and not worth a detailed examination here, but basically each iteration through a recursive function has to eat up more stack. The program needs to know what the variables were set to during each iteration, otherwise it would recurse down to the base case and not be able to remember how to get back up to the top.

An exception to this, apparently, is tail recusion. If the last step in a function calls itself with no other action, then a smart compiler won't eat up the stack space needlessly, but will instead just jump back to the beginning of the function with the new variables. Sounded good, so I set out to test if it actually worked.

To begin with, I had to design a basic recursive factorial calculator, and another one using tail recursion. The basic one looks like this:

function factorial(n)
if n = 1 then return 1
return n * factorial(n - 1)
end function

This is just psuedocode, made to (in theory) be easy to read by a non-programmer. Although the last step of the above function is where the recursion happens, it still needs to get that return value, so it can multiply it by n and return the result. It needs the stack to remember what n was.

The following tail-recursive function is a little more complicated, but bear with me and I'll explain:

function factorial_with_accumulator(n, acc)
if acc < 1 then acc = 1
if n = 1 then return acc
acc = acc * n
n = n - 1
return factorial_with_accumulator(n, acc)
end function

Here "acc" is an accumulator. When the function is called initially, the accumulator isn't set. The first step detects that and sets it to one. Then if the "n" value is one, it returns whatever is in the accumulator. This satisfies the base case.

Thereafter, the accumulator is multiplied by n, then n is decremented, then -- and here's the meat -- the function is called again nakedly, passing the new values of n and acc, and not manipulating the results in any way. Will the compiler (perl interpreter, in my case) be smart enough to figure that out and optimize the function? Let's see!

I created the following perl program, which can handle arbitrarily large integers, catch an input variable, and print it's factorial back out:

#!/usr/bin/perl -w
use bigint;
use strict;

sub fac {
my $n = shift;
return 1 if $n == 1;
return $n * fac($n-1);
}

$_ = shift;
print "$_! = " . fac($_) . "\n";

Not much to it, and the "sub fac" section (the subroutine for computing factorials) is similar to the basic recursion pseudocode from above. Here's a screenshot of it actually working... in case, you know, you think I just make all this stuff up:



The simplest way to check performance is to throw it a big number and see how long it takes to chew on it. I played with trying to get a real stack overflow, but perl seems to be pretty robust in that regard. I succeeded in eating up a lot of system memory, but never in getting an overflow. 1,000! is where things start to slow down, so I bumped it up to 10,000 to get some decent load to test with. The program printed the answer in 48.77 seconds. (The answer was several thousand characters long, accounting for more than the number of subatomic particles in the universe, I imagine.)

Next I reimplemented just the "fac" function to use tail recursion, like so:

sub fac {
my ($n, $acc) = @_;
$acc = 1 unless $acc;
return $acc if $n == 1;
$acc *= $n--;
fac($n,$acc);
}

A 10,000! calculation using that took only 39.01 seconds, a 20% increase in speed, while adding an additional variable and a couple extra steps to the function. Clearly some optimization is going on behind the scenes. Success!

So if you know programming, you've probably had the thought "Why make that recursive at all? You can handle decrementing a counter and multiplying with any number of basic looping constructs." Why, indeed? A quick re-write of the function to take out all recursion looks like this:

sub fac {
my $n = shift;
my $acc = 1;
$acc *= $n-- while $n;
return $acc;
}

Short and sweet, and calculating 10,000! in only 30.77 seconds. 21% faster than the tail-recursion method, 37% faster than the basic recursion method. The moral of the story is compilers can be smart, but not smarter than taking the right approach.