Recursion in Ruby

I recently took part in the RPCFN. Being that this month's challenge was a Shortest Path type challenge and I've done enough discrete maths papers to know that the best graph traversal Algorithm for this is Dijkstra's least cost path one I went away and implemented it in a couple of hours. Many others did exactly the same thing, often much more elegantly that me. What struck me was that the markers were quite obviously looking for people to imagine up their own method of finding the shortest path, and had a massive bias towards recursive algorithms.

Now the winning submission is a very nice piece of code, it's concise, easy to read, simple, well tested, and it clearly lays out it's goals, to find a recursive solution to the problem with disregard of performance. It performed ok, I did wonder however how the recursion would impact the performance on larger problem sets.

So I took Todd's code and refactored mine to work with his data structures. I also changed up my code to match his module's interface and packaged both implementations into their own classes so that there wouldn't be clashes while trying to test them. (modules are for adding abilities to classes, not for providing whole feature sets, if you see yourself including a module into main, you're doing it wrong...)

And here it is.

I ran benchmarks on a low end computer (Pentium 2.8) against 3 graphs, one with 2 nodes and 2 edges, the RPCFN example with 7 nodes and 10 edges, and a larger, more complicated one of 7 nodes and 21 edges, all of this is in the code linked above. Here's the results over 10000 iterations:

Simple Graph:
Iterative Approach took 1.54700second(s).
Recursive Approach took 0.95300second(s).
RPCFN Graph:
Iterative Approach took 6.37500second(s).
Recursive Approach took 20.62500second(s).
Large Graph:
Iterative Approach took 10.70300second(s).
Recursive Approach took 472.96200second(s).

The numbers speak for themselves, this approach doesn't scale at all well. In fact at first I thought I'd broken some of Todd's code and created an infinite loop of some sort. It's more than likely that the recursive function could be tweaked to get better performance, but short version is that if I were ever to need to implement graph traversal in Ruby for any production system, recursion would be the last approach I'd look at.

Final word
Todd's decision to use a recursive solution in this case was totally justified, readability and simplicity were massive factors in this event. That said I believe that outside of the smaller, more contrived problem scopes, recursion brings a lot of headaches and scaling issues than the iterative approaches.