Results Of The Fibonacci Challenge Are Inhttp://blogs.msdn.com/b/ericlippert/archive/2004/05/20/results-of-the-fibonacci-challenge-are-in.aspxAnother bunch of good replies to my challenge of yesterday. And again, a bunch of answers that I didn't expect, and some of the points that I was thinking of weren't mentioned.
People seem to like this more conversational format; I'll probably useen-USTelligent Evolution Platform Developer Build (Build: 5.6.50428.7875)Recursion and Dynamic Programminghttp://blogs.msdn.com/b/ericlippert/archive/2004/05/20/results-of-the-fibonacci-challenge-are-in.aspx#5391716Wed, 10 Oct 2007 17:18:08 GMT91d46819-8472-40ad-a661-2c78acb4018c:5391716Fabulous Adventures In Coding<p>Back in May we were discussing the merits and drawbacks of recursive programming techniques -- that is,</p>
<img src="http://blogs.msdn.com/aggbug.aspx?PostID=5391716" width="1" height="1">Recursion, Part Zerohttp://blogs.msdn.com/b/ericlippert/archive/2004/05/20/results-of-the-fibonacci-challenge-are-in.aspx#4796123Fri, 07 Sep 2007 01:59:23 GMT91d46819-8472-40ad-a661-2c78acb4018c:4796123Fabulous Adventures In Coding<p>I’ve mentioned recursive programming techniques several times over the years in this blog ( Topological</p>
<img src="http://blogs.msdn.com/aggbug.aspx?PostID=4796123" width="1" height="1">re: Results Of The Fibonacci Challenge Are Inhttp://blogs.msdn.com/b/ericlippert/archive/2004/05/20/results-of-the-fibonacci-challenge-are-in.aspx#140663Mon, 24 May 2004 21:32:00 GMT91d46819-8472-40ad-a661-2c78acb4018c:140663James HugardThis topic was too old for me to reply to it in the original thread... The discussion below neglects the fact that the JScript engine has a limited call stack... recursion dies when the stack is only 467 levels deep - a fact which once prompted me to rewrite the easy to implement recursive solution with an iterative one :P
<br>
<br># re: The Stygian Depths Of Hacked-Together Scripts 5/13/2004 6:50 PM Eric Lippert
<br>Good point. For a list which mostly consists of unique words, this solution makes two entire in-memory copies of most of the data in the list. If the data are large and not copied by reference, that could be quite expensive.
<br>
<br>Quicksort on the other hand only consumes memory in the form of stack frames, and each stack frame is of a constant size, and in the typical case there will be O(log n) stack frames max in use at any time. (The standard quicksort algorithm suffers from a n-squared worst case in rare cases, but getting into those details would take us far afield.)
<br>
<br>There are other aspects that I've neglected in this analysis. (Hint: think about what I said above; what if the data are large?)
<br><div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=140663" width="1" height="1">re: Results Of The Fibonacci Challenge Are Inhttp://blogs.msdn.com/b/ericlippert/archive/2004/05/20/results-of-the-fibonacci-challenge-are-in.aspx#140588Mon, 24 May 2004 20:08:00 GMT91d46819-8472-40ad-a661-2c78acb4018c:140588Eric LippertFirst off, please point out the sentence in which I stated that the problem was "calculate the nth fibonacci number". I can't find such a sentence. I said that I wanted an algorithm that _produced_ the nth Fibonacci number.
<br>
<br>Second, your objection is based on a semantic quibble. Tell you what, I'll modify the algorithm:
<br>
<br>var fibarr = new Array(null, 0, 0, 1, 2, 4, /*[...]*/, 8944394323791463);
<br>function fib_3(n)
<br>{
<br> // [appropriate checking here.]
<br> return fibarr[n] + 1;
<br>}
<br>
<br>OK, now it calculates the nth fib number, and its still O(1). Happy now? :-)
<br>
<br>Here's a question for you: True or false: the planet Saturn is a device which computes the orbit of the planet Saturn.
<br>
<br>You've got to admit that Saturn does an admirable, 100% accurate job of computing the orbit of Saturn. Want to know where Saturn is in its orbit? Go to Saturn, and there it is! Want to know where it will be in a year? Follow Saturn around for a year, and Saturn will give you the answer.
<br>
<br>And yet that seems unsatisfying somehow. You need to carefully define the word "calculate" if you want to have this conversation.<div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=140588" width="1" height="1">re: Results Of The Fibonacci Challenge Are Inhttp://blogs.msdn.com/b/ericlippert/archive/2004/05/20/results-of-the-fibonacci-challenge-are-in.aspx#140568Mon, 24 May 2004 19:53:00 GMT91d46819-8472-40ad-a661-2c78acb4018c:140568109> That's certainly O(1)
<br>
<br>Sorry, this doesn't apply. The question was about the asymptotic order of _calculating_ fibonacci number. Taking the number from an array does not calculate it.<div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=140568" width="1" height="1">