Home > Uncategorized > Simple Recursion

Simple Recursion


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
   else:
      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.

🙂

Advertisements
Categories: Uncategorized Tags: , ,
  1. Dan
    November 27, 2010 at 11:03 pm

    Good points. I agree that recursion can be a helpful tool, and a good programmer should be able to code simple recursive problems like Fibonacci in an interview.
    Too, it can help break a complex program down.
    Iterative approaches, however, can perform better across larger datasets (stack depth, function call overhead, etc). It’s easier to control and monitor stack depth with a separate stack array variable, if necessary. Some classes of programs such as Fibonacci don’t actually need a stack, if you start from the base case and work up.

    Tail-recursion is pretty neat, from a geek perspective, in that it limits stack depth. Some compilers have a neat trick where the final function in a chain of function calls that return the result of the called function without manipulation pop back up to the top stack frame in the tail-call chain. So there are practical benefits to tail-call optimizations beyond self-recursion.

  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: