[2007-12-15] Recursion
As Joel Spolsky once noted, in programming, recursion and pointers are two of the hardest things to master. And while I'm not going to really comment on pointers in this post, I do have a word or two about recursion.
Recursion seems trivial when the design is obvious. Consider this classic example of a recursive factorial function that was my first real introduction to this paradigm:
factorial(x):
if x < = 0, factorial = 0;
if x = 1, factorial = 1;
if x > 1, factorial = x * factorial(x - 1);
That's relatively simple to turn into real code, isn't it? An if, elseif, else, some returns, and that's the whole thing right there -- it's practically already written for you.
But when the problem isn't so obviously specced out, you have to think about it a bit more closely.
The reason I bring this up now is that I wrote a bit of recursive programming [no longer web-accessible, as of 2012-10-17], and the interesting thing (to me) about it is that I wrote it in the "wrong" order.
It started when I wanted to emulate an "infinitely" deep tree structure for a favorite URLs list. I wanted to keep the tree in a database on a server, and synchronize it with a Firefox extension to a favorites menu the extension would keep. That got me wondering about how to transmit the data over the wire. After a few iterations, starting with something that looked like this:
Folder:[Link Name:URL][Link Name: URL][Folder:[Link Name: URL]]
And ending with this:
Folder
Link Name|URL
Link Name|URL
Folder
Link Name|URL
which limits the link and folder names the least, I then started wondering how I could store it in the database.
Clearly, the simplest way was to have each item keep track of who its parent was, and use a simple auto-incrementing "id" field to identify records. But then came the problem of taking this out of the database and converting it to the pretty format shown above. I had already been considering a recursive function would probably do the job best, and so I got to work building this recursive function.
I had a few false starts, and I edited and deleted unsuccessful solutions mercilessly. I also had to come to terms with the fact that my initial idea -- building the tree as records came from the database -- was amazingly impractical.
What I settled on is shown in the example code I wrote [again, no longer web-accessible], a two step process involving massaging the data a bit after getting it out of the database before converting it into a real tree structure. The example code also features two recursive functions for double the fun: one is for creating the tree structure internally, the other to display said tree structure; the latter was infinitely easier to write than the former, and I did actually write it first, before I realized I was going to need recursion again for the tree building process.
The result? Some pretty decent example code, if you ask me. And several hours of fun, combined with the exhilaration of having found the right solution and having it work as well as you'd intended, without any surprises (read: bugs) messing things up for you.
I'd say that was very much worth the time it took.
Update: I also found this discussion on the Joel On Software message board which seems to bring up similar points (and, indeed, it seemed to me like at least some of the posters involved were reading my mind). Go ahead and give it a read-through, it's interesting.
Why did I rescue this?
I actually just asked myself that, having re-read the article and realized the example code not only wasn't available anymore, but couldn't be made available (it's not just source, but a complete demo, and relies on a database that doesn't exist here, and I don't want to resurrect it). I may actually post just the source code somewhere and update this article, but what the article really shows is that recursion is tricky. It's difficult to get it right when you're just approaching it from scratch, and so it needs to be very carefully thought out.
I haven't actually looked at the code I'm talking about in great detail, so I couldn't tell you if recursion was even necessary in this case, or whether it was applied correctly or not. I can't even tell you if the code is logically thought out, though knowing myself I expect it to be. I do know that what it shows is that apparently fairly simple problems can easily expand into something fairly large and complicated, and that's another lesson to take home from the article.
So, it's worth keeping for historical reasons.