Share via

How Not To Teach Recursion

  • Article

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

Comments

  • Anonymous
    May 19, 2004
    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.

  • Anonymous
    May 19, 2004
    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.

  • Anonymous
    May 19, 2004
    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!

  • Anonymous
    May 19, 2004
    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.

  • Anonymous
    May 19, 2004
    I would use a recursive-descending parser to explain the occasional advantage of using recursion over an iterative approach.

  • Anonymous
    May 19, 2004
    The simplest recursion? Directory/file search. Much better than iterative logic.

  • Anonymous
    May 19, 2004
    > 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".

  • Anonymous
    May 19, 2004
    The comment has been removed

  • Anonymous
    May 19, 2004
    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!

  • Anonymous
    May 19, 2004
    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).

  • Anonymous
    May 19, 2004
    > 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?

  • Anonymous
    May 19, 2004
    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.)

  • Anonymous
    May 19, 2004
    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.

  • Anonymous
    May 19, 2004
    The comment has been removed

  • Anonymous
    May 19, 2004
    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)



  • Anonymous
    May 19, 2004
    The comment has been removed

  • Anonymous
    May 19, 2004
    I don't think you can have an algorithm with O(1). Using the Binet Formula leads to an algorithm with O(log N) time complexity (even though apparently you can use a Field so that you only use powers of integers, not real numbers. I woudn't know how to do that, but it's mentioned here: www.cs.wisc.edu/~mhock/SSL/fibcalc.pdf

    Space complexity should always be at least proportianl to the length of the resulting fibonacci number which (I believe) is proportianl to phi^n.

  • Anonymous
    May 19, 2004
    I meant proportional to phi^n / 2^n. Of course if you implement it using say int32s this is not really relevant, you'd just overflow.

  • Anonymous
    May 20, 2004
    > Binet’s Formula: fib(n) = (Phi^n-(-Phi)^(-n))/sqrt(5), where Phi = (sqrt(5)+1)/2

    You can simplify this by noticing that Phi is greater than 1 so Phi^-1 is less than 1 and Phi^-n is much less than 1 for large n. So you'll get the same answer by rounding Phi^n/sqrt(5) to the nearest integer. Note that this formula doesn't work for negative integers.

    The easiest way to derive the formula (that I know of) is using a generating function.

    > I don't think you can have an algorithm with O(1)

    It's O(1) as long as you have a fixed precision for numbers. In general, F_n has O(n) bits in the result so every algorithm must take at least O(n) time.

    > apparently you can use a Field so that you only use powers of integers

    Well, rationals, which can be implemented using integers and some fixup work. The trick requires creating a field extension, a field extension requires a field (naturally), and the integers is not a field. If you had a suitable implementation of integers mod p you could do it with that finite field. Your results may look a little strange at times though!

  • Anonymous
    May 20, 2004
    So if neither "Fibonacci numbers" nor the "Tower of Hanoi" problems are good pedagogic examples ... what would you use to teach recursion to students?

  • Anonymous
    May 20, 2004
    It depends on the purpose of the class of course. But in general, I'd try to find an example where a recursive approach is clearly better, and where the data being manipulated is defined recursively.

    I agree with the commenters above who suggested that file systems are a good place to start. Many students understand them at a practical level already, and you can quite easily define them recursively: A file system is a DAG of folders, a folder may contain zero or more files and zero or more folders. Once you have the concept of a recursively defined DAG down, lots of topics become teachable.

  • Anonymous
    May 20, 2004
    Directed Acyclic Graph, is it? A traditional DOS or Windows 9x or NT <=4.0 file system is just a directed tree for one drive, and a directed forest for the whole system. Expanding the class to DAGs allows for directories that are accessible via several distinct paths. Symlinks (aka junction points)? But those same symlinks can introduce cycles into the graph. Although not recommended, they are possible.

    That leads to a practical problem. Suppose you have a file system supporting symlinks, namely, NTFS 5. How do you traverse it, starting at a given root, visiting each directory only once (even if it is accessible from the root through more than one path), and not getting caught in loops?

  • Anonymous
    May 20, 2004
    Bah, no one liked my example. :(

    But yes, most forms of graph searching are more easily understood when phrased in recursive terms (and frequently easier to write).

  • Anonymous
    May 20, 2004
    Correct recursive function for Fibonacci can be based on Lucas numbers:

    F(n+m) = 1/2 * ( F(n)*L(m)+F(m)*L(n))

    where L is Lucas number (like Fibonacci but start from (1,3) not a (1,1))

    Taking in account L(x) = F(x-1) + F(x+1)

    And a little bit optimized

    F(n+m) = F(n-1)*F(m) + F(n)*F(m+1)

    This way you can create pretty fast recursive algo to calc big Fibonacci numbers.

    Fibonacci calculation was once at All-Ukrainian Informatics Contest (4 hours total to solve 4 CS problems). Test cases was up to F(65000) - about 14Kb in output.

  • Anonymous
    May 20, 2004
    IMHO, teaching recursive functions starting with these very simple examples isn't such a bad practice. Recursive factorial, fibonacci and tower of hanoi are easy to understand and useful to explain the concept. The recursive solution for the tower of hanoi is far from optimal, but elegant, and a very simple solution for a problem that a novice could believe it's very complex. After the concept is understood, starting from those solutions, other concept could be introduced: lazy evaluation, backtracking cut, algorithm complexity, optimizations and so on. Graphs are more complex concepts, and should be introduced later.

    If we talk about the basic concepts maybe we should start with: a=a+1 :) Most of the people have a basic math background before they start to learn programming, so the above basic concept could raise some understanding problem. After that, many will use a++ but maybe not so many will know why ++a is recommended ;).

    These days its seems that the algorithms optimizations isn't the top priority for most of the real applications (unfortunately), instead the top priority is to reduce the developing time and of course the cost. So, RAD tools, scripted language, GC and so on are used, and all of them have optimizations tradeoffs. Also, how many of you encountered in a real application code the famous bubble sort algorithm? :) But, perhaps, the application work well and the client was happy. Until the 'profiler' say's otherwise almost any solution is acceptable if the application is delivered on time, isn't it? ;).

    So, if the optimizations aren't such a problem in the real applications, why should we bother about them when the purpose is the understanding of a concept? But, I'm totally agree that teachers should explain also the alternatives.

    Best regards,
    Bogdan

  • Anonymous
    May 24, 2004
    One particularly good teaching application for recursion is the Merge Sort.

    Among the benefits: Merge Sort is one of the simplest O(N•LogN) sorting algorithms to write.

  • Anonymous
    April 28, 2005
    We have internal email lists for questions about programming languages. Here's one that came across...

  • Anonymous
    July 28, 2005
    Hi Eric,

    I implemented your iterative rules for solving Towers Of Hanoi in vbscript and had lots of fun thanks!

    The problem has always been presented to me in a slightly more stringent way, in that the tower starts on the left spike and must be moved to the right hand spike to win.
    Solving this slightly more stringent scenario can be achieved by adding one more rule concerning the first move:

    The first move should always be from the first
    column to
    a) The second column for even numbers of disks.
    b) The third column for odd numbers of disks.

    Also, by playing around with my code, I found by trial and error that:

    The number of iterations needed to solve for n disks is equal to double the number of iterations required for n-1 disks plus one.

    Thanks for such a great blog and good luck with the marriage!

    Regards,
    Tim



  • Anonymous
    July 28, 2005
    Well, it would be surprising if the number of moves was any different! After all, the algorithm for moving a tree of size n is essentially

    * move a tree of size n-1 onto an empty spike in k moves.
    * move the bottom disk, one move
    * move a tree of size n-1 onto the bottom disk, again, in k moves.

    So the total number of moves has to be 2k+1.

  • Anonymous
    December 22, 2006
    Um... Brett's suggestion of Directory/File search was exactly what I was thinking when I read this post. The student would be less distracted by understanding problem domain and more focused on the concept of recursion. Add to that, a Directory/File search is something that a person is more likely to actually use.

  • Anonymous
    December 22, 2006
    I still remember a homework assignment to solve the tower of Hanoi problem without recursion.  I got a 60% on a well written, well commented, and perfectly working program - I didn't google the answer, but probably came up with something similar to what was listed here (it may not have been optimal number of moves, but that wasn't part of the assignment).   I lost 40% because my professor was convinced the best (or maybe the only?) way to solve this problem was using a stack to simulate recursion (which is probably the dumbest solution that actually works).   Somehow we need to actually teach students how to think - otherwise they grow up to be Professors that teach this way, and poison more minds.  Teaching someone to actually think about and understand what they are doing is hard, if not impossible - but I do appreciate reading posts like this.  I feel better knowing someone is trying.

  • Anonymous
    January 05, 2007
    My favorite example to teach recursion is that of printing a linked list in reverse. Heaven help you it's a slow process to handle iteratively. To print the contents of said list in forward order (assume C++ classes)  printr(list *node){    if(NULL==node)      return;    cout << node->data;    printr(node->next);  } To print in reverse order merely requires moving the cout to after the call to printr(node->next).

  • Anonymous
    January 19, 2007
    The comment has been removed

  • Anonymous
    January 19, 2007
    PingBack from http://mike.hostetlerhome.com/2007/01/19/about-recursion/

  • Anonymous
    January 19, 2007
    The comment has been removed

  • Anonymous
    January 19, 2007
    My last comment isn't entirely clear - what i mean with that equation is to raise a 2x2 matrix to the nth power.

  • Anonymous
    January 19, 2007
    Eric, I observe that it is usually easier to demonstrate that recursive algorithms do what they are designed for.  This is particularly well illustrated in your Tower of Hanoi examples, where you give an iterative algorithm, which to me, at least, is somewhat cryptic: I can understand its description, but it is not straightforward to see why it works. I think code's being clearly correct is an important benefit.  Whether this benefit is more or less important than efficiency depends on the circumstances.  As a (oversimplified) rule of thumb, I make my code as clearly correct as possible, and then if it is not fast enough, I sacrifice some of this clarity for speed. To summarize: I think there are strong arguments for the recursive forms of your functions, and I don't agree with your unqualified characterisations of them as 'the worst' or'terrible'. If the naive fibonacci example isn't fast enough, I'd try a recursive definition based on a helper function returning adjacent pairs before I resorted to your iterative definition.  I think your iterative definition would be faster, but that you have paid a cost in code clarity to make it so.

  • Anonymous
    January 19, 2007
    The comment has been removed

  • Anonymous
    January 19, 2007
    But consider for a minute a tail recursive optimized language such as scheme... and/or an implementation of the fib function that is linearlly recursive. This is O(n), and uses recursion. (define (fib n)  (letrec ((fh (lambda (n nxt rs)                 (cond                   ((= n 0) rs)                   (else                    (fh (- n 1) (+ nxt rs) nxt))))))    (fh n 1 0))) (fib 3)

  • Anonymous
    January 20, 2007
    Andrew, tail recursion an iteration really are the same thing. Your fib implemantation is a good example for this, since it uses the same algorithm fib_2 does.

  • Anonymous
    January 20, 2007
    This wasn't an issue for me. I learned recursion before iteration. My first programming language was scheme -- iteration was introduced after recursion as "tail-recursion".

  • Anonymous
    January 28, 2007
    Here is the sample provided by Andrew Gwozdziewycz reworded in OCaml (another programming system with tail call optimization): <pre> open Printf;; let fib = function n ->  let rec fh fh_num fh_km1 fh_km2 =    if fh_num = 0 then fh_km2    else fh (fh_num - 1) (fh_km1 + fh_km2) fh_km1  in    fh n 1 0;; printf "fib: %d" (fib 9);; </pre>

  • Anonymous
    March 19, 2007
    I first saw recursion in programming demonstrated as a way of computing factorials. Later (in college) I was taught Towers of Hanoi, Fibonacci, and the usual. I don't believe this hurt me, because the instructor was careful to warn us of the inefficiency. This example coincidentally stresses the principle that recursion often gives very easy-to-program and understand solutions to problems, but is rarely the most efficient way to solve something. This also reminded me of the closed formula for the Fibonacci sequence, which you can derive from generating functions: http://mathworld.wolfram.com/BinetsFibonacciNumberFormula.html

  • Anonymous
    March 19, 2007
    The comment has been removed

  • Anonymous
    March 19, 2007
    Eric, your very premise is fundamentally flawed.  Others such as Andrew Gwozdziewycz hinted at it, but even more directly,.. if one uses a real compiler your assumptions are rendered valueless. Using the Franz Allegro Lisp compiler (first compiler I had at had - I'm sure others can do it too), and this definition: (defun fib (x)  (cond   ((or (= x 1)        (= x 2)) 1)   (t    (+ (fib (- x 1)) (fib (- x 2)))))) compiled and tracing Fib I see exactly one call.  If I force it to interpret, say for pedagogical reasons, I can see the recursive call structure when tracing. Pedagogically if you want to teach students to be good programmers, you first teach them the tools of the trade.  I would much rather see anyone working for me write that then your fib_2.  Why?  it's easier to maintain, it's easier to see what it does, I guarantee it took less time to write and debug.  It's good clean functional code with no side effects. But more importantly it works and it works right.  And with my modern compiler it works efficiently (because most modern compliers can get rid of tail recursion quite easily).  Why do I want to teach my students to second guess and try to out-think the compiler?  They should write what's simplest, then they should profile the thing and it turns out you forced them to use a dumb complier for some reason, THEN and ONLY THEN should you and they worry about the next steps to optimize.  Trying to optimize before understanding the problem needing optimizing is a huge part of the problem in the way most students are currently taught and try to program.  Please don't perpetuate this. I agree that assignments are more interesting if they have a purpose.  And computing Fibonacci numbers for no apparently good reason is a little pointless.  More grounded tasks always help.  But for just looking under the hood, sometimes it helps when they can see the call graph, and not have to worry about all the underlying processing, because it's simple.  As such I would be more inclined to use an example like that in class to show the idea without getting mired in the details, and then have them practice with something more meaningful, maybe like sort as others have mentioned.

  • Anonymous
    March 19, 2007
    The comment has been removed

  • Anonymous
    March 19, 2007
    "To learn recursion, you must learn recursion.." I think this is the best expression, I ever read about recursion so far...

  • Anonymous
    March 19, 2007
    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.

  • Anonymous
    March 19, 2007
    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.

  • Anonymous
    March 19, 2007
    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.

  • Anonymous
    March 19, 2007
    <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.

  • Anonymous
    March 19, 2007
    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.

  • Anonymous
    March 19, 2007
    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.

  • Anonymous
    March 19, 2007
    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.

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

  • Anonymous
    March 19, 2007
    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

  • Anonymous
    March 19, 2007
    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.

  • Anonymous
    March 20, 2007
    Sounds like someone has been reading code complete...

  • Anonymous
    March 20, 2007
    Would this work? http://en.wikipedia.org/wiki/Ackermann_function

  • Anonymous
    May 25, 2007
    The comment has been removed

  • Anonymous
    March 09, 2008
    If you would interview me, I would probably tell you to check your math, because the first Fibonacci number is 0, not 1. They don't go "1, 1, 2, 3, 5, 8, ..." They go "0, 1, 1, 2, 3, 5, 8, ..." So I guess I would have found a bug in the very definition of your exercise. Does that mean I get the position now? ;)

  • Anonymous
    May 21, 2008
    u have given very good points. who is necessary for a good programmer. i want to know what is cases in which we cant found solution of recursion into itreative way. that means we cannt change recursive program in itrative way. please mail me....

  • Anonymous
    May 06, 2009
    You are using a very inefficient recursive algorithm for Fibonacci. I was asked to solve the problem at school and came up with this one. Where Fibonacci number at position 10 is Fib(10, 0, 1) (C#) public static long FibonacciOf(int Times, long TwoNumbersBack, long OneNumberBack) {    if (Times == 0)        return TwoNumbersBack;    else if (Times == 1)        return OneNumberBack;    else if (Times == 2)        return OneNumberBack + TwoNumbersBack;    else        return FibonacciOf(Times - 1, OneNumberBack, OneNumberBack + TwoNumbersBack); }

  • Anonymous
    April 15, 2010
    I actually programmed up a fast recursive fibonacci number generator that uses identities with 2n, 2n+1, 3n, 5n, and so on to produce a faster than O(n) solution.  Granted, that still doesn't beat the analytic solution, but it's pretty cool.  (I don't know the actual big O, but statistics tell me it's near O(n^.73).)   Here's a snippet of the code in Java. else if (n%2==0) { int fm1 = fibonacci(n/2-1); int fp1 = fibonacci(n/2+1); return fp1fp1-fm1fm1; }

  • Anonymous
    August 09, 2012
    "[...]suppose you have a pair of rabbits that every year gives birth to a pair of rabbits[...]" I guess you meant "you have a pair of rabbits that every year gives birth to ONE rabbit" No, I meant what I said. Do the math, you'll see that it works out. -- Eric