Skip to main content

Recursion: an example with no code

File under

You are using recursion right now. Right this very second. You use it hundreds of times a day without even realizing it, and so does everybody else. And you’ve been using it ever since you read your first Hardy Boys caper, or said something to Mommy and Daddy that wasn’t baby talk.

Here’s why: language is a recursive system.

This is an observation I made about a decade ago, while I was riding the T home from college (somewhere between the Southerland Road and Washington Street stops on the B Line, for those of you who are local). Like anyone else, I’ll read or listen to music on the T, or just people watch. But sometimes it’s nice to just sit and think, without worrying about doing anything more taxing than watching the world flash past your window. Well, on the B Line, the world doesn’t so much flash by as it does crawl haltingly.

In any case, to show how language is recursive, consider the following sentence:

Word on the street is that you manage a stalwart young pugilist who cannot be knocked down.

Assuming that you haven’t seen the episode of The Simpsons from which that line is taken about 50 times (ahem), how do you parse this sentence? Most likely, you read each word; consider what it means; and when you get to the period, you stop. With any luck, by the time you reach the period, you’ll understand the stenence.

But suppose you’ve never seen the word “stalwart” before, and you can’t figure out what it means from the context. Easy: just look it up in a dictionary. Here’s the first result of a Google search for “define:stalwart”:

hardy: having rugged physical strength; inured to fatigue or hardships

OK. I think I’ve got it, but what does &”inured” mean?

made tough by habitual exposure

Ah. Brilliant. Moving on … what’s a “pugilist”?

boxer: someone who fights with his fists for sport

Got it. And here’s the period, so we’re done, and I understand the sentence: Homer can take him some punches.

By now, you’ve probably figured out where I’m going with this: that every word in a language is defined in terms of other words. If you don’t know the meaning of a word, look it up; and if you don’t understand one of the words in the definition, look that up, too, and so on, until you get to a point where you understand every word.

So it turns out that the process of reading a sentence is remarkably similar to a recursive function:

  1. Base case: you hit the end of the sentence, the period – why, here’s one now.
  2. Recursive case: do I understand this word? If yes, great, move on to the next word. If not, get it’s definition, and parse that sentence.

And there you have it.

Now, will this little example help you write recursive functions? Probably not. The only way to learn to program recursively is through practice. One day, you’ll be trying to solve some problem, and the solution will naturally come to you: recursion! Until that day, keep practicing.

But I do hope that this example has given you an opportunity to reflect on how fascinating the system of language is. The image that comes to my mind (while not really accurate) is a house of cards. Everything depends on everything else to keep it standing; it appears to be built on nothing, to be all smoke and mirrors.

And yet, how solidly it stands. How beautifully it works. How wonderful.