Posts Tagged ‘algorithm’

Simple Recursion

October 2, 2010 1 comment

I started writing this post last week, then an update to the wordpress app crashed and I lost the draft. With any luck, this post will be better than last week’s post would’ve been 🙂

A few weeks back, there was an article or two posted to digg/reddit/slashdot about recursion. The basic bottom line was something to the effect that 90% of programmers fail at simple recursion, which is both surprising and expected.

Surprising, because simple recursion really is… simple recursion. Most coders have seen the infamous Fibonacci series, and the (pseudo) code is quite simple:

def fib(n):
   if n == 1 or n == 0:
      return 1
      return fib(n-1) + fib(n-2)

You have a simple basis case (two cases, n is one or zero) to terminate the recursion, and if the inputs are not trivial to compute then you break the problem down into smaller problems and “recurse.” in the fibonacci example above, it’s pretty simple code to compute a simple numeric series… So it surprises me that coders can/do routinely fumble on this exact problem. I have personally seen multiple people fail this question in a interview with significant prompting. So it shouldn’t surprise me, but it does.

Now some people will argue with me and say the Fibonacci series is not a good question because it’s too (basic, academic, fill in the blank). And generally speaking, they’re correct – the Fibonacci series is a pretty basic, boring problem which is solvable with simple, basic code. So I am definitely interested in more complex, more advanced code which tackles more complex problems (merge sort anyone?). However someone who doesn’t get the Fibonacci series (which is a classic recursion example) is very unlikely to ace more challenging questions.

At this point, I have several other thoughts about recursion – non-trivial recursion is, not surprisingly, non-trivial; and I’d like to give some of the sorting algorithms a decent write-up. But for now I think I’ll keep it short and to the point:

Recursion can be elegant, fun, and simple. We should all spend a little more time recursing.


Categories: Uncategorized Tags: , ,