Do you *really* understand recursion?

Today while writing a program that involved recursion, I got to thinking: Do I really understand recursion? Like, really, really understand recursion?

I know recursion; I understand the key concepts involved; I can write algorithms for Binary Search, Trees, Towers of Hanoi, etc., without thinking – but does all that mean I understand recursion?

This led me to examine my favorite Towers of Hanoi puzzle. It’s easy to say that “Move n disks from peg 1 to peg 3” means the combination of:

  • Move n-1 disks from peg 1 to peg 2
  • Move the nth disk from peg 1 to peg 3
  • Move the previous n-1 disk stack from peg 2 to peg 3

And it’s also easy to see how this would work for n = 2 or 3. At n = 4, a slight discomfort sets in, through you might still be able to trace it on paper. At n = 5, you can’t help feel a slight panic.

So I edited my program with all sorts of printf() statements to show which function invocation I was in and what was going on, but it didn’t help.

Several wasted minutes later, I felt compelled to make a Google search on “does anyone really understand recursion”. Thankfully, among other gibberish, it returned this post, which had this wonderful advice from the classic Lisp book:

Students learning about recursion are sometimes encouraged to trace all the invocations of a recursive function on a piece of paper. … This exercise could be misleading: a programmer defining a recursive function usually does not think explicitly about the sequence of invocations that results from calling it. … How do you visualize all those invocations? You don’t have to.

Phew. What a relief . . .

Leave a Reply

Your email address will not be published. Required fields are marked *