Part of a series of posts explaining programming for the lay-person.

This is part of a series of posts; see the introduction to this series. This entry discusses advanced ways to use subroutines.

A Refresher

Recall that a subroutine, procedure, or function is a named block of instructions, possibly accepting parameters or arguments and sometimes returning a value. All of these terms were discussed last week. I’ve been displaying subroutines like this:

and calling or invoking them like this:

Recursion

The word recursion, from the Latin recurrere meaning “‍run again‍” or “‍come back‍”, is used in programming to mean a subroutine that invokes itself. This turns out to be a surprisingly powerful concept.

Let’s start with an example. The factorial function n!, normally defined as “‍the product of all numbers between 1 and n,‍” can be defined recursively as “‍n! = n × (n – 1)! for n greater than 1; for smaller n, n! = 1‍”. So if we start with 5!, that is equal to 5 × 4! because 5 is greater than 1. That has a 4! in it, which is equal to 4 × 3!, giving us 5 × 4 × 3!. Invoking our recursive definition of factorial again we have 5 × 4 × 3 × 2!, and once again we get 5 × 4 × 3 × 2 × 1!. Now, since 1 is not greater than 1, 1! must be just 1, so we obtain 5 × 4 × 3 × 2 × 1, which has no more factorials in it.

Let’s put that in our normal display format:

Of course, we don’t have to write factorial recursively; we can also use the other definition:

This is always true: we never have to write anything recursively, On the other hand, we can write everything using only recursion; we don’t need any blocks, types, expressions, or any of that. This is one of the unexpected outcomes of Turing completeness; I might get into it later. as every recursive function has a non-recursive version. So why would we? Sometimes it is actually easier.

Naturally Recursive

There are many problems that are rather difficult to describe without using recursion. For example, the descendants of a person is that persons children and all the descendants each of those children have. But that uses “‍descendants‍” in the definition of “‍descendants‍”, making it a recursive function.

Now, there is a way to write that without using recursion, but it is strange looking. In fact, I can’t think of any way to describe it in English, but I think reading it can be an interesting exercise, so I include it just for good measure.

Lots of Traps

Recursion is a really simple idea. A function invokes itself. But it can get rather messy in practice. For example, if we define “‍n!‍” as “‍n × (n – 1)!‍” then we have a recursive definition that never ends:

In programming parlance this definition forgot the “‍base case‍” of not recurring when n ≤ 1.

We can also make way too much work for ourselves: if we define the nth Fibonacci number as the sum of the (n – 1)th and (n – 2)th Fibonacci numbers (with appropriate base cases) then the straightforward code

will end up computing the same number many many times:

There are other problems lurking out there, but I think I’m already starting to lose my readers.

Avoiding these kinds of problems is where telling the computer what to do is more than just writing down your described solution in a programming language. It’s also one of the reasons why many programmers spend a lot more time at a white board drawing pictures of their solutions and discussing nuances with colleagues than they do actually writing the code.