python: a recursion diversion

[how-to]

posted by tom / February 10, 2006 /

My solution relies on recursion. Before I explain what that means in computer science terms, I should clue you in to how unimportant it is: almost totally. Okay, it's true — there are a few problems that recursion is uniquely suited to solving... But mostly it's just a way for programmers to make themselves feel smart. Designing recursive algorithms can be very confusing. When they work right they're amazingly elegant and compact — but in my experience recursion is rarely worth including in a basic programming curriculum (but is usually included anyway). When deadlines loom or the code is unlikely to be reused, you can usually find an ugly-but-easy way to avoid using recursion.

So feel free to skip over this. It's probably somewhat confusing, and is completely nonessential. Now, on with the show.

Something is recursive if it is defined, at least partially, in terms of itself. A simple example is the acronym GNU (which refers to a collection of open-source software championed by Richard Stallman). GNU stands for "GNU's Not Unix". See what I mean about recursion and nerdy self-satisfaction?

From a computer's standpoint, the acronym GNU would be even more meaningless than it is to us. Remember when we talked about infinite loops? It's the same situation here. If GNU were a function, it would keep recursing into itself until the computer ran out of memory. That's because it doesn't have an exit condition — a logical situation that will eventually occur and cause the function to return something concrete rather than just another reference to itself. Here's a really simple recursive function — one that has an exit condition.

As you may have guessed, this function produces the factorial of the number that is initially passed to it (e.g. 4! = 4 * 3 * 2 * 1 = 24). It has an exit condition that occurs when its parameter is equal to 1. It's not a very well-defined exit condition (what happens when it's passed an initial parameter less than 1? or a non-integer?), but you get the idea.

Go ahead and try to trace through the function in your head. What happens when it's called with an initial parameter of, say, 3? Just follow the logic. When it hits that reference to itself, the current instance of the function freezes. Nothing is lost; it doesn't forget the value of any of its variables. They all just sit patiently for the newly spawned "layer" of the function to do its thing and return a value. If that new layer (let's call it "n+1") spawns yet another layer (n+2), well, then n+1 will wait patiently as well. Even though there will be a bunch of variables named x sitting inside identically-named functions, they won't interfere with one another.

Some of you may be looking at this factorial example and thinking, "Couldn't you accomplish the same thing with a normal while or for loop?" The answer is yes. There's no reason to use recursion in this case — in fact, it would introduce needless overhead as the system tries to keep track of a bunch of different copies of x. It's just a simple example, not a real situation in which using recursion would be appropriate.

Where recursion comes in handy is when you don't know how many iterations of a procedure you're going to need to execute in order arrive at a solution; or, more frequently, when your algorithm needs to branch in a bunch of different ways.

The arborial terminology isn't accidental — many algorithms are commonly thought of in terms of trees (which, while terminologically lovely, may be confusing — think of corporate organizational charts that have the CEO at the top to get an idea of how these trees are usually depicted). In the case of our phone number/word problem, you could picture an org chart/tree with a level for each digit in the number. The first level would contain the three or four letters that correspond to the first digit on the telephone keypad. Each of those would then branch into the three or four letters corresponding to the second digit of the phone number. And on and on, until you had a level for each digit in the number. Each possible complete path, traced from top to bottom, would represent a word you could spell with that phone number.

That's a lot of branches. Thankfully, the computer will keep track of them for us. Check out this code:

This code assumes that we have the FindLetters function available from the solution I already posted — you know, the one that takes a digit and returns an array of the letters than correspond to it. Also, note the default value for the parameter currentWord — if it's not specified when the function is called, it's assumed to be equal to an empty string.

Notice that FindWordsRecursive has an exit condition — when the phone number getting passed in is empty, the function prints out the word it has built. If it's not empty, it grabs the first digit of the phone number as it currently exists and finds the letters for it. It then adds each valid possible letter onto the word it's built so far, then calls itself, passing along the word-so-far — and the phone number with its first digit chopped off.

In this way the phone number keeps getting shorter and the word-so-far keeps getting longer, until the phone number is empty. At that point the word-so-far gets printed out. The complication is that more than one instance of the function is spawned in every pass (via that for loop) — that's because there's more than one valid letter for each digit. So more and more layers of the function are spawned, just like the branches of that tree, until we finally reach the bottom of all of them, the words-so-far are all printed, and the system exits each layer of the recursive structure. All of this happens step-by-step — don't get confused and think that parallel recursive layers run simultaneously. Everything is done serially and in order.

Aside from this recursive solution being sort of neat, it has the advantage of working with arbitrarily long phone numbers. The solution I initially posted was specifically designed to work with seven digit phone numbers — if you didn't know how many digits there'd be, how could you know how many for loops to write? That's not a problem here.

Hopefully this gives you a taste of the elegance that's possible with recursion. Until you take a data structures class, you probably won't really appreciate it — and until you decide you want to write an operating system, device driver or programming language, you don't really need to take a data structures class. All you really need to know right now is that recursion is kind of neat and kind of hard.