Tower of Hanoi

Subliminal hint, in German

An old school software engineer showed me a computational thinking exercise the other day that finally helped me understand recursion. Or at least brought me a step closer to figuring it out.

The Tower of Hanoi is a classic math puzzle.

Go work on it. I’m going to assume you’re smart enough to figure it out eventually. Come back when you’ve done that. And don’t come back until then.

**Hanoi tiger mom locks blog door**

Have you figured it out?  Oh really. So how many moves would it take to move a ten disk tower?  If you don’t know that, then you didn’t really figure it out! Get out of here!

**Locks door again (secretly bakes brownies)**

Figured it out?

Of course you did.  Have a brownie.

Now we can talk about your adventure. Remember that joyful moment of insight, when you realized that you could move a tower that reached the sky, if you wanted to, because you’d figured out the simple formula! (Start by moving the top 3 disks, then move the fourth disk on to the empty rod, then move the  3 disk tower back on top of the 4th disk, then move the 5th disk onto the empty rod, then move the 4 disk tower back on to that, then move the 6th disk onto the empty rod. Repeat forever.)  But then there was the  horrific realization of how much work that would involve, since every time you add a disk, the number of moves increases exponentially (the formula for figuring out the moves is actually (2 ^{number of disks} -1))

Welcome to a secret truth of civilization. Engineering has a simple solution to almost any problem, except where to find the slaves to actually do the totally tedious work!

A recursive formula is basically a formula that repeats the same work over and over, but always adding a little something else—or taking something away–so that the work is actually producing some kind of change.

Crack that and you’ve cracked a major concept in programming.

Now you just have to find slaves! Here bring them some brownies.