| > Every recursion class talks about the Fib algorithm and why it's nice with recursion. It is nice with recursion in the sense that it's a straightforward, easy algorithm (what college CS student doesn't know basic arithmetic?) that illustrates recursion. It's also trivial to write the recursive version based on the mathematical definition. It is not nice in that it's very slow and blows up due to the exponential growth of the recursive calls. No one outside of CS 101 or an algorithms class is going to ever write the recursive version again. But that not-nice aspect makes it nice again, because it's a good jumping off point in how to improve an algorithm's runtime by understanding its structure (the iterative version) or throwing more memory at it (the memoized version). > But the iterative version doesn't have these stack limitations, presumably uses less memory and is just as fast. There is no "presumably", unless you store every Fibonacci number and not just the last two, the iterative Fibonacci does use less memory than the naive recursive Fibonacci. And there's no "just as fast". The iterative Fibonacci is faster, unless you've done something horribly wrong. It runs in linear time wrt N rather than exponential. If your linear algorithm is only just as fast as an exponential one, you haven't made a linear algorithm. > Doesn't that make it a better implementation? Yes, obviously. Which is why after CS 101 or an algorithms class you pretty much never write anything like that except maybe as a prototype. "This recursive program follows the definition closely, but it blows up memory/time." Start there and improve is a very reasonable thing. Start there and stop is just silly. |