Examples of Recursion: The Good, the Bad, and the Silly

What we need: a really good example

The programming artefact of recursion, also known as “writing a subroutine that calls itself”, is well known to generations of students of computer science. Recursion is a reasonably simple yet a remarkably powerful concept. That is, it’s a reasonably simple concept once you understand it, but unfortunately, it can take some effort to get that understanding.

Teachers of computer science are faced with the challenge of finding good examples of recursive programs to offer to their students. The ideal example will demonstrate the principle of recursion clearly while hinting at its power, and thus show why it’s a compelling concept. Over the years I have come across examples of recursive programs, enough now that I think I can classify them into three broad categories: the good, the bad, and the silly. Here are the categories, each with an example:

The Good: Towers of Hanoi

Towers of Hanoi is a puzzle that consists of three posts, and a set of disks of different sizes with holes in the middle so that the disks can be stacked on the posts. You start with all disks stacked on one post, ranging from smallest to largest, top to bottom. Your job is to transfer the stack from the first post to the third, using the second post for temporary storage. You can only move one disk at a time, and you can never place a larger disk on top of a smaller disk.

The puzzle can be solved easily by breaking down the job into smaller jobs. To move the entire stack of disks from the first to the third post, do these steps:

• Move the (slightly smaller) stack of all but the largest disk from the first to the second post,
• Then move the largest disk from the first post to the third,
• Then move the (slightly smaller) stack from the second to the third post.

The middle task is a simple step – just move one disk – but the first and last steps each require solving again the Towers of Hanoi puzzle but for a smaller stack. In other words, solving the full puzzle requires solving two simpler instances of the puzzle.

The Internet is Born, Thanks to Cats

From ARPANET to Internet

It is well known that the internet, that indispensable part of modern civilian life, started out as a US Department of Defence project to build a robust computer network, the ARPANET. I sometimes wonder what the military leaders of that era would think if they can see what their project has grown into. How would a general of the 1960s react to seeing people using this technology, designed for better warfare, to watch videos of cats doing wacky things?

In my mind I imagine that there was a fateful meeting that set the direction. In the 1960s, computer networks are emerging from research labs into productive applications, but they are not fault-tolerant. The military is interested, but the it needs networks that can survive attacks, and university labs think they have the answer. A meeting is convened at the Pentagon where university professors can present their ideas for a new kind of network.

The Professors have a Proposal

As a general and other military staff listen, the professors explain how networks of the day look like trees with branches, nodes, and leaves. This design is easy to build and run thanks to minimal links and simple route planning, but it has a problem: if any branch is cut then the network breaks into two parts.

A tree is the simplest kind of network …

… but any single failure breaks it.

The professors want to build a network that looks more like a highway system, where there are several routes between any two places. If a road is blocked, those multiple routes mean network remains largely intact.

Loops in this network make it more complicated to build and operate…

… but it tolerates failure points.

Of course every benefit comes with a price, and with this road-map-style computer network the price is in the computers at the nodes of the network. When forwarding a packet of data toward its destination, a node has to choose between several outbound links. The choice depends not only on the direction to the destination, but on the capacity of each link and data-traffic congestion.

The computer in each nodes of the network requires more complex algorithms and more processing power than was current in the industry-standard tree-networks.

As the presentation progresses, the military staff are becoming more and more enthusiastic with what they are hearing, and by the end, they are sold on this project.

It is at this point a staff member stands up to say “Your proposal is very impressive, and I think I speak for all of us in saying we would like to move forward. What would be our the next step?”. The professors are ready with a plan to build a prototype network that links together several universities and military bases. The general asks, “Can you estimate how much your prototype network will cost?”. One professor stands up, and begins by listing a number of caveats – “great complexity”, “untested algorithms”, etc. – before finally stating a price. A very high price.