How Not To Teach Recursion

How Not To Teach Recursion

  • Comments 65

A Joel On Software reader asked the other day for examples of recursive functions other than old chestnuts like Fibonacci or factorial.  Excellent question. I suggested topological sort, of course, but there are plenty of other examples that are way better than the Fibonacci numbers.  Why do I think Fibonacci is bad?  Read on.

In case it's slipped your mind, the Fibonacci numbers are defined as follows:

fib(1) = 1
fib(2) = 1
fib(n) = fib(n-1) + fib(n-2)

thus, they go 1, 1, 2, 3, 5, 8, 13, 21, …

The Fibonacci numbers have many interesting properties.  For example, suppose you have a pair of rabbits that every year gives birth to a pair of rabbits, rabbits take one year to reach maturity, and rabbits never die.  In that (admittedly unrealistic) situation, the number of pairs alive at any given time is a Fibonacci number.  Clearly the number alive this year is the number alive the year before (who all live) plus the number alive two years before (who are now mature enough to breed.)  Fibonacci numbers also have a relationship to the Golden Mean, logarithmic spirals, and many other interesting nooks of mathematics.  But that's not what I want to talk about today.

Because they have a straightforward recursive definition, it's natural to introduce recursive programming to students by simply translating the definition into code:

function fib_1(n)
{
    if (n == 1 || n == 2)
        return 1;
   
else
      return fib_1(n-1) + fib_1(n-2);
}

I am in principle very much for this pedagogic approach.  Recursive programming can be difficult to get your head around.  Starting with recursive definitions, getting your head around those, and then using those definitions in code is a pretty good way to approach the material.  If you think of lists as being "zero or more items in a row", it is conceptually hard to think of anything other than an iterative approach to processing the list.  If you think of a list as "a list may be empty, or may be an item followed by a list", then the definition of the data leads itself to a recursive programming approach very naturally.

Practically however, this is probably the worst possible simple way to solve the Fibonacci problem.  When you introduce recursion by using it to solve a problem which iteration solves much, much better, students come away thinking that recursion is dumb -- that it is both harder to understand and produces worse solutions.  Better to pick an example where the iterative solution is not better!

In fact, this is a good whiteboarding question for interviews:  implement me a recursive Fibonacci algorithm, tell me why it is terrible, and write me a better algorithm. A good candidate should be able to come up with the above and something like this:

function fib_2(n)
{
    if (n == 1 || n == 2)
        return 1;
    var fibprev = 1;
    var fib = 1;
    for (var cur = 2 ; cur < n ; ++cur)
    {
        var temp = fib;
        fib += fibprev;
        fibprev = temp;
    }
    return fib;
}

Typical questions that I might ask at this point in an interview are

  • What are the asymptotic running time and memory usage of the two algorithms you've written?
  • Can you write me an algorithm with even better asymptotic running time and memory usage? Alternatively, can you convince me that this is as good as it gets?
  • Suppose I asked you to make this algorithm absolutely as fast as possible.  What would you do?
  • Now suppose that I do not care much about raw speed but I do want the method to be robust in the face of bad input.  Now what do you do?

and so on.  (Anyone who cares to propose answers to these can leave comments; consider this a spoiler warning if you want to work them out for yourself.  Working out the asymptotic running time of recursive fib is quite easy and produces a somewhat surprising result.)

Another old chestnut that's often used as an introduction to recursion is the famous Tower Of Hanoi problem.  Briefly stated, you have a number of disks with a hole in the middle, and three spikes upon which you can place disks.  The disks are all of different sizes and are arranged from biggest to smallest in a pyramid on one spike.  You must move one disk at a time from spike to spike, you must never place a larger disk on top of a smaller disk, and you must end up with the entire pyramid on a different spike than you started with. 

The recursive solution is straightforward.  Moving a "sub-pyramid" of size one is obviously trivial.  To move a sub-pyramid of size n, first move a sub-pyramid of size n-1 to an  extra spike.  Then move the bottommost disk of the size n pyramid to the other extra spike.  Then move the sub-pyramid of size n-1 onto the disk on the second extra spike.  A nice recursive solution!

Many recursive implementations for this old chestnut exist.  But I'm not a big fan of this problem as a pedagogic approach to recursion for two reasons.  First, it's totally contrived (as is “fib“).  Second, there is a very simple iterative solution for this problem, which is almost never mentioned when it is used as an example of the power of recursive programming!  Again, we should pick examples where recursion is clearly preferable.

In case you're curious, the iterative solution can be produced by writing a program that implements these rules in a loop:

  • Number the disks 1 to n starting from the top. 
  • Never move an odd disk onto an odd disk.
  • Never move an even disk onto an even disk.
  • Never move a larger disk onto a smaller disk.
  • Never move the same disk twice in a row.
  • Never move a disk onto an empty spike unless you have to. 
  • Move disks until there are no legal moves.

If you don't believe me, try it yourself with ace through ten of a deck of cards sometime.  Or, perhaps start with ace through four -- ace through ten will take you a while.  Both the recursive and iterative solutions are optimal in the number of moves.  The recursive solution is O(n) in terms of memory usage, the iterative solution is O(1).

  • Good points about Fibanocci and Towers of Hanoi. A better (IMO) problem to work with recursively is the "missionaries and cannibals" problem. As a side note, this problem would require the students to already be fairly proficient at programming (we did it 3/4 of the way through our first semester course IIRC).

    For the interested, I will describe this problem. You have N missionaries and M cannibals on one side of a river (N > M). There is one rowboat which can hold two people in it. If there are ever more cannibals on one side of the river than there are missionaries on that side, the cannibals eat all of them (failed solution).

    Now show me the optimal set of steps to move all missionaries and all cannibals to the other side of the river.

    Note: I'm fairly sure this could be done iteratively too, but its a LOT easier to figure out what to do if you approach it recursively.
  • Good one Eric,
    I've often thought about how hideous the fibonacci recursion example is. Actually I believe that I've got a book (maybe WEP, but I'm not sure) that discusses this as well.

    Personally I've always liked "search in a binary tree" for my example. Or, if people don't understand binary trees, search in a sorted array for my examples of recursion.

  • Indeed -- binary search of a sorted array, either recursive or iterative, is another good interview problem because it requires intense attention to detail. The number of ways to get an off-by-one error is huge!
  • Hmm -- in your iterative sample, wouldn't a check to see if n < 1 be important? Otherwise when you get to your loop, cur < n won't be true until you hit an integer overflow ... at which point you have a very wrong answer.
  • I would use a recursive-descending parser to explain the occasional advantage of using recursion over an iterative approach.
  • The simplest recursion? Directory/file search. Much better than iterative logic.
  • > in your iterative sample, wouldn't a check to see if n < 1 be important?

    That's why I ask a question about robustness.

    > when you get to your loop, cur < n won't be true until you hit an integer overflow

    The sample is in JScript, not C. There's no such thing as integer overflow in JScript. When a number gets too big, we have a special value for "infinity".
  • 1) The recursive fib sequence will require 2 frames (function return pointers + some) on the stack for each recursive call, not to mention the overhead of setting up the next function calls. Ouch! Would this be O(2^n)?

    2) The gist of fib_2() is likely as good as it can get based on my knowledge of generating Fib sequences (w/o cheating with a google search)

    3) Not sure how JScript deals with a var declaration in the loop (If it reallocates space for temp instead of changing the contents of what temp points to). If it reallocates, I would declare temp previous to the loop.

    4) As Shawn pointed out, bounds checking to prevent overflows and negative numbers in fib_2() would be sufficient to make it robust.

    As for a recursion example, I always think of getting a complete (recursive) directory listing as a good one - easy for the student to comprehend the problem even if you are not explaining it to a math genius.

    I have to agree with you on The Tower example. In the real world, I never decided to pick a recursive solution because the problem at hand reminded me of the Tower example.
  • Require all of your students to learn Scheme or Lisp as their first programming language and then forbid the use of the interative functions in both languages so that you have to use recursion for everything...

    That has to be the WORST way to teach recursion. It took me years to get over my hatred of recursion because of that!
  • Actually, there is an iterative algorithm for Hanoi that requires much less rules to remember:

    while (problem not solved)
    {
    move the smallest disk one position clockwise;
    perform the only available move not involving the smallest disk;
    }

    It yields the same sequence of moves as the recursive algorithm.


    The recursive Fibonacci function has one more interesting property; if you call fib_1(n) once, fib_1(n-1) gets called once, fib_1(n-2) twice, fib_1(n-3) three times, and fib_1(n-k) gets called fib_1(k+1) times.


    As for teaching recursion: quick sort and tasks involving tree traversal (naive tree-based set or map, dir /s).
  • > Ouch! Would this be O(2^n)?

    Good guess. Can you prove it?

    > likely as good as it can get

    I'll give you a hint -- there is an O(1) fib algorithm.

    > Not sure how JScript deals with a var declaration in the loop

    All var declarations are logically hoisted to the nearest lexical scope, and braces do not define scopes. There's a good blog topic...

    > bounds checking to prevent overflows and negative numbers in fib_2() would be sufficient to make it robust.

    Oh really?

    What if you pass in too many arguments? Too few? Strings? Dates? Arbitrary COM objects? null? undefined?
  • Isn't the running time for a recursive fibonacci algorithm proportional to the fibonacci number that it's trying to compute?

    To write the fastest possible generator, it's possible to put all the answers in a table (written by an iterative algorithm). The table doesn't get too large because the fibonacci sequence grows quite fast so you're soon beyond 32 bit numbers. (Can't remember how soon now.)
  • Often, it's preferable to use recursion for
    - formal specification of the a problem, and
    - derivation of a solution.
    The special case here would be the so called tail recursion, which can always be rewritten into an efficient iteration.

    By itself (without derivation) the fib_2 has limited value, both for teaching or job interview purposes. After one writes down this algorithm, it's not likely students or candidates will find themselves able (unless they're really brilliant) to find the even better solution with a time complexity O(log N).

    This solution is suggested by Kaldewaij in "Programming: The Derivation of Algortithms" (Prentice Hall International Series in Computer Science), p. 88.
  • > I'll give you a hint -- there is an O(1) fib algorithm.

    There exists an analytical formula for fib(n) that involves the Golden Ratio. Can’t remember it off the top of my head, though.

    Binet’s Formula: fib(n) = (Phi^n-(-Phi)^(-n))/sqrt(5), where Phi = (sqrt(5)+1)/2.

    This is O(1) if you consider raising a float to the power an O(1) operation.
  • Another thing to squeeze things down a bit more (This method only validates where necessary, but is still robust):

    change

    if (n == 1 || n == 2)
    return 1;
    to

    if( n < 3 )
    {
    if( n > 0 )
    return 1;
    else
    // throw your favorite exception here
    }

    Of course, the above solution is optimal (binet's formula)



Page 1 of 5 (65 items) 12345