Recursively Yours

Yours to read, my new Mint column, Recursively Yours to read, my new Mint column, Recursively Yours to read, my new Mint column ... here.

(I called it "To Recurse, Perchance to Dream", Mint preferred "Recursively Yours").

In case the link does not work, the text is below. Comments, as always, welcome.

***
Our kittens have never stepped out of our flat. So I'm wondering about teaching them a foolproof method, call it the CatOut method, to find their way downstairs for a stroll. Now I'm sure they understand human-speak -- all right, I'm overly fond of felines -- so here's what I might whisper in their furry ears: "CatOut starts by checking if you're already on the ground floor. If so, you're done: race out to the road. If not, walk down one flight of stairs and do the CatOut from there."

Simple, right? So what happens when Aziz and Cleo do the CatOut at our fourth floor flat? They'll check: are we on the ground floor? No. Therefore, walk down one flight, to the third floor. Apply CatOut there. Meaning, they'll check: are we on the ground floor? No. Therefore, walk down one flight, to the second floor. Etc. In minutes, they'll shoot joyously out of the building, onto the road.

Look at it like this: We've defined their trip from a given floor in terms of the same trip from the floor below. We've defined it in a way that every computer science student will recognize: recursively.

Recursion is a profound and powerful idea. If you do it right, it works like a dream. But for me, its real appeal is that it's like saying: "You want to do this? Just go do it."

Or: "You want to learn how to swim? Jump in and start swimming." Best way to learn.

Because sometimes when you have a problem, detailed instructions get intense and complicated. Far better to just attempt a solution to a smaller but related problem, learning as you go. The power of recursion is precisely that it defines a task in terms of a simpler version of itself. By a clever bit of self-reference that, finally, reduces a daunting problem to a series of easy ones.

You specify an endpoint in which the task becomes trivial: if on the ground floor, run for the road. You specify a recursive case that reduces the task -- descend a flight of stairs -- because apart from the reduction the procedure is then identical: make the trip, but from one floor below.

Do this repeatedly, and CatOut becomes just a series of descents, one flight at a time. This way, you know Aziz and Cleo can reach the road from the ground floor, from the 10,679th floor, or even from the top of a building with an infinity of floors. (Though after descending a few million flights, you may hear a few yowls of protest. You have been warned.)

So yes, computer science students learn recursion, though not through the good offices of Aziz and Cleo. Instead, it works well, for example, for one of the earliest programming problems they tackle: calculating the factorial of a positive number.

The factorial, written with an exclamation mark, is what you get when you multiply all the numbers between 1 and the original number.

Thus 5! (read "five factorial") = 1 x 2 x 3 x 4 x 5 = 120.

And 100! = 1 x 2 x 3 x 4 x … x 97 x 98 x 99 x 100 = a number so large, I feel tired even trying to contemplate it, leave alone calculate it.

But while factorials quickly get large, you can tell a computer -- a stupid machine that can multiply two numbers, but no more -- how to calculate them via a short recursive procedure.

Note only that 5! = 5 x 4!, or 100! = 100 x 99! = 100 x 99 x 98!, etc -- you can break those down further. In English, the procedure looks like this: to calculate the factorial of a number, check -- is it 1? If so, the answer is 1 (the trivial case) and you're done. If greater than 1, the answer is the product of the number itself and the factorial of the number immediately below (the recursive step).

Do this repeatedly, and instead of an intimidating factorial calculation, the computer is left to do what it can: multiply pairs of numbers, a series of pairs. The power of recursion.

In my computer science days, my colleagues and I obsessed about writing what we called "elegant" software. We didn't always succeed, and it wasn't always clear what qualified as elegant in a particular situation. Yet we all recognized that it usually is clear, innovative and has a satisfying dash of panache.

And some of the most satisfyingly elegant stuff came from using this thing called recursion. Because if you get it right, recursion can substitute for chunks of clumsy programming.

"To recurse is divine", said the legendary computer scientist L Peter Deutsch. Me, I like learning by breaking things down, by doing, by simply getting going. That's what recursion's about, for me. Don't know much about divinity, but I'll take elegance every time.