Ramblings of Narc

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, 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, 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.

My week-ends have been pretty crappy lately. Saturdays, I sleep. Sundays, I visit my Dad in hospital (I sincerely hope he’s getting out soon). All in all, this leaves me pretty much no time during the weekend when I feel like actually doing anything useful, so I’ve been brain-dumping my various project ideas on this blog.

The trouble is, other than backing up Eris, I haven’t really done much work on my other projects, which kinda sucks.

So I’m getting pissed off. Which, for me, is when things usually get done.

Therefore, the very next thing I’m going to do (outside of work, that is), will be to finally formalize the structure of my CM proggies. Which means various shiny new bits are about to get checked in to the NeoFW repository, most likely. Just as soon as I figure out what this formalized structure looks like…