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

  • Couldn't agree more !

    The first recursion problem I was set at university (after the obligatory introduction via factorial) was, "Write a program that draws a tree."  

    Obvious example when you think about it, I guess ;-).

    The second one was, "Write a program which draws a randomly winding avenue of trees receding into the distance."

    They also gave us a bonus question; "Write a program that draws something cool."

    To put this in context, this was an introductory paper in Pascal - they did a bit of spoon feeding, and pretty much everyone "got it" - and at the same time, several rather exceptional students wrote some damned fine code.

    I think the same lecturer set the following question in a programming competition I was in (my team came third last as I recall) ... you are dropped in the middle of a forest.  It's a commercial forest of infinite size, and the trees are planted on the intersections of a grid of 1 metre squares.  So without loss of generality, your position is (x,y) where 0<x<=y<1.  It's a mature forest, and at your eye level all you can see are trunks of uniform radius r.  i.e. the branches are all well above your head.  Assuming that you yourself have radius 0, and you are given (x,y,r) as inputs ... how many tree trunks are fully visible at eye level ?  Partially visible ?

  • "To learn recursion, you must learn recursion.."

    I think this is the best expression, I ever read about recursion so far...

  • Kevin:  I think you should stop hard-coding your (fib 6) call (or whatever value you used for testing).  Otherwise your compiler will perform the computation for you during the compile stage and your fib function will just become 'return the pre-computed result' function.

  • Teaching recursion with the Fibonacci sequence as an example is not a good idea. Mostly because it can be taught without recursion.

    Here is my VBA function:

    Function Fibonacci(N As Single)

       Fibonacci = Round(((Sqr(5) + 1) / 2) ^ (N + 1) / Sqr(5))

    End Function

    This is a great article just the same. Thanks for posting it.

  • I'm with Kevin on this one -- teaching introductory students to worry about writing obfuscated code like the fib_2 example just in case they have to program with a dumb compiler that can't even optimize out tail-recursion seems a bad idea.  

    PS: I do think that the Fibonacci problem is probably boring to most students and I'm all for finding more interesting problems, so I do agree with that; I'm just not a fan of code that's written in a more difficult manner than it needs to be just because the writer didn't trust the compiler.  It makes it harder for humans to read and hides your intent, which might actually make it harder for a good compiler to optimize.  And yes, I know, this is a simple example and fib_2 isn't *that* difficult to read, my objection is more about the underlying premise of this article -- that's it's better to write more confusing code even if your tools allow more readable code to run just as efficiently.

    PPS to Andy: Huh?  I doubt that Kevin was hard-coding a call to a particular value like (fib 6).  Optimizing out tail-recursion has been common among compilers for decades, so I'm fairly confident that what he says about Franz's Lisp compiler is correct.  It's just not that rare a thing to see in compilers.

  • <i>with a dumb compiler that can't even optimize out tail-recursion</i>

    This isn't a counter-argument, but the Java compiler sadly doesn't optimize out tail recursion.  It's a well known bug, but there doesn't seem to be much movement in the Java camp to fix this.

    The .NET byte code does support this, from what I've read.

    Not that Java and .NET are my favorite language[s| frameworks], but I think this is yet another place where .NET is doing better than Java.  

    Fibonacci as a teaching point is nice in an algorithms class because you can then get into finding closed form solutions for recursive functions.

  • I suppose like others here, I tend to disagree with the premise of this article.  I think that an obviously correct implementation that closely resemble the problem is one of the greatest reasons for using and teaching recursion.

    :)I realize that this post is now about 3 months old, but I noticed that nobody mentioned memoization!  Was this because it is too obvious?

    Personally, my first instinct is to write the naieve fibonnaci and then memoize it.  I've personally seen this able to compute numbers well beyond the bounds of a 32-bit integer fast enough that I didn't feel the need to optimize it further.  For whatever that's worth.

  • How do you get "three months" out of "May 19th, 2004"?  This post is 34 months old.

    I am not sure why it is kicking up such a fuss now.  People keep on posting it to reddit.  It is not a particularly interesting post.

  • Another simple problem (courtsey SICP) is to compute exponentiation i.e. a ^ b where both 'a' and 'b' are integers. This is quite cool, because you get to not only _understand_ recursion, but also some amount of complexity O(n) vs O(log n) etc.

  • A sample homework we had in our computer science class was to print out a linked list backwards.

  • The Best Way to solve the Problem is by using the Stack Structure and Composite Design Pattern , Which wil help you to reduce the LOC than the recursion.

    About Compsite Pattern : http://www.exciton.cs.rice.edu/JavaResources/DesignPatterns/composite.htm

    Design Pattern will provide the *Good and Exact* Solution to many of the Problems where the recursion is happening around. Even a repeat call will make the memory to be eaten wider ! So , Composite pattern need to be taught before the Recursion Class :-)

    ---

    ananthmv

  • One thing to consider is that proletariat languages generally rely on iteration. The iterative solutions are better, primarily because you've thought them through more. If you implement tail recursion and memoization, the run times of the recursive solutions are the same as of the iterative. The memory usage is still slightly greater (functional code tends to be slightly more memory-intense), but not by the large factors shown.

    That's one typical trade-off with programming functionally: functional code parallelizes much better (since you don't store change any data in variables, order of operations doesn't matter). If you run it on a multicore cell processor, it is much faster. On the other hand, since you create new data instead of overwriting old data, the memory usage tends to be greater.

  • Sounds like someone has been reading code complete...

  • Would this work?

    http://en.wikipedia.org/wiki/Ackermann_function

  • Interesting blog entry and ensuing discussion.  Netting it out: There are a lot of ways to solve a problem.  Recursion is often inefficient in space and time.  However, when you introduce a topic, the particular example you give is not nearly as important as the independent student exercise.

    In high school, I had a brilliant AP Computer Science teacher.  He presented fibonacci as a recursive solution, and then he had us step through the algorithm on paper.  I guess you can say, "Real programmers don't use pencils!" but the fact of the matter is that this was a useful exercise for understanding the difference in control flow from a while or for loop.  This is a form of microanalysis.  (Another form of microanalysis is to have students visualize the stack frames stacking on top of each other which each function call, in order to appreciate that this function is LIFO-to-the-extreme under the hood.)  After we traced through the program, our teacher said, "Now your [independent student] assignment is to write this using the iterative approach you are familiar with."  Note that this is a completely different perspective and demonstrates your argument that fibonacci is only good in principle is a strawman.  The real failure is always going to be in the assignments you give students, because, as John C. Reynolds has pointed out in The Craft of Programming (1981), the most difficult task in Computer Science is teaching an experienced programmer how to program.  I agree with Reynolds: Giving assignments at the right level of difficulty is the only way to attract students who are often put off by "polemics and formalism".  Therefore, I posit that my AP Computer Science teacher did a good job introducing fibonacci.

    At the end of the lesson plan on recursion, my teacher summarized the following key points:

    * Recursion is often more elegant than an iterative solution. (To emphasize this, he presented Towers of Hanoi.  I cannot remember what he said about Towers of Hanoi as it relates to an iterative alternative.)

    * Recursion requires the parameters to be put on the stack for each function call.

    * Recursion does not stop until the base case is reached, and memory will continue to be allocated, stack frame on top of stack frame, until the base case is reached.  For inputs that require many recurses, the program may run out of memory...

    * Memory is finite and if you use too much of it, then your program will not be robust.  It is important that your program does not crash unexpectedly.

    * Iterative solutions tend to be faster and require less space, because their is less memory allocation (the implication being that memory allocation is time consuming and necessitates more memory being used).

    All-in-all, it was a pretty good introduction to recursion.  However, I think it should have been followed up by useful examples of recursion.  It definitely could have been better, and I think the first step to making it better would be to have the students understand the difference between microanalysis and macroanalysis.  When writing recursive algorithms, you should de-compose the problem using macroanalysis.  J. Stanley Warford in Computer Systems 1st Edition has some good examples of the microanalytic versus macroanalytic approach, however he lacks enough focus on cases where you want to use recursion.  He does mention recursive descent parsing and mutual recursion, however he does not present code for a recursive descent parser.

    It is also worth noting that we use recursive thinking in mathematics, often when not realizing it.  Calculating the determinant is one common example.  I recently recommended to someone that they implement Lewis Carroll's method for calculating the determinent of a square matrix.

    That being said, recursion is clearly a "Threshold Concept," so to speak, because once students learn it, the knowledge they gain is transformative, irreversible, and integrative.  For these reasons, it is something students should master.

Page 4 of 5 (65 items) 12345