Unlocking Programming: Recursion
Licensed under Creative Commons: other posts

Unlocking Programming

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:

(how to find) the sum of two numbers
return the 1st number + the 2nd number

and calling or invoking them like this:

…;let x be the sum of 3 and 4;…

# 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:

(how to find) n!
if n > 1 { return n × (n – 1)! } otherwise { return 1 }

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

(how to find) n!
start a as 1; for each number b from 1 to n { replace a with a × b }; return a

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.

(how to find) the descendants of a person
start with a list of the person’s children; for each child of the person { add the descendants of the child to the list }; return the list

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.

(how to find) the descendants of a progenitor
make a list of descendants, initially empty; make a working list, initially having only the progenitor; as long as the working list isn’t empty { take a person off the working list; add that person’s children to the list of descendants; also add that person’s children to the working list }; return the list of descendants

# 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:

2! = 2 × 1! = 2 × 1 × 0! = 2 × 1 × 0 × –1! = …

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

(how to find) the nth Fibonacci number
if n ≤ 2 { return 1 } otherwise { return the (n – 1)th Fibonacci number + the (n – 2)th Fibonacci number }

will end up computing the same number many many times:

Summary of illustration: the 9th Fibonacci number uses 67 invocations this way, not just nine. The 100th uses 708,449,696,358,523,830,149 invocations, more than estimated age of the universe in milliseconds.
 9 8 7 7 6 6 5 6 5 5 4 5 4 4 3 5 4 4 3 4 3 3 2 4 3 3 2 3 2 2 1 4 3 3 2 3 2 2 1 3 2 2 1 2 1 3 2 2 1 2 1 2 1 3 2 2 1 2 1 2 1 2 1 2 1 2 1

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.