Programming by accident

Andrew seems to be having some troubles with recursion. The important thing to remember here is that recursive algorithms need you to implement two cases — the end condition (terminal), and everything else. Let’s take a simple case, and use C to avoid all the extra syntactic sugar which would otherwise get in the way:

Let’s write a recursive function to find the factorial of a number. That’s what you get if you take a number, and multiply it with every number smaller than itself, but greater than zero. So 3 factorial is 3 x 2 x 1 = 6. Remember — no sane person would do it this way in real life…

First, the end case is when the number gets to 1:

    if(num == 1) return 1;

The other case, is that we need to multiply by all the numbers smaller than us:

    else return num * factorial(num - 1);

To put it all together, we have:

    int factorial(int num)
      if(num == 1) return 1;
      else return num * factorial(num - 1);

One of the languages I did in first year, many years ago, was called Gopher, which is a variant of Haskell. Haskell is a functional language, which means everything is expressed in the form of mathematical functions. That means that there are no looping constructs for instance, which means you have to do everything using recursion. You get used to recursion real quick that way. What Gopher actually did under the hood was expand out all the function calls into one big formula, which it then executed. Let’s do that for the 3 factorial case using our function. We get something like:

    factorial(3) = 3 * 2 * 1;

Which is right. Doing that kind of thing is a good sanity check if you’re not too confident with recursion. So, how’s that for an attempt to explain recursion?