Path: news.mathworks.com!not-for-mail From: "John D'Errico" <woodchips@rochester.rr.com> Newsgroups: comp.soft-sys.matlab Subject: Re: Fibonacci Date: Sun, 11 Apr 2010 09:24:03 +0000 (UTC) Organization: John D'Errico (1-3LEW5R) Lines: 42 Message-ID: <hps4fj$qok$1@fred.mathworks.com> References: <hprijn$3bl$1@fred.mathworks.com> <hprohm$l1n$1@fred.mathworks.com> Reply-To: "John D'Errico" <woodchips@rochester.rr.com> NNTP-Posting-Host: webapp-05-blr.mathworks.com Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit X-Trace: fred.mathworks.com 1270977843 27412 172.30.248.35 (11 Apr 2010 09:24:03 GMT) X-Complaints-To: news@mathworks.com NNTP-Posting-Date: Sun, 11 Apr 2010 09:24:03 +0000 (UTC) X-Newsreader: MATLAB Central Newsreader 869215 Xref: news.mathworks.com comp.soft-sys.matlab:625474 "Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in message <hprohm$l1n$1@fred.mathworks.com>... > "Jake " <nathan.a2000@googlemail.com> wrote in message <hprijn$3bl$1@fred.mathworks.com>... > > function fib(n) > > int n; > > if(n==0 ) return; > > else return n * fib(n-1); // line 7 > > ....... > ------------------------- > Besides the serious flaws pointed out by James and Matt, there are other difficulties with what you have written here, Jake. First of all, you seem to confuse the Fibonacci series with factorials. Where did you ever get such a strange notion? They are by no means the same entity. > > Secondly, if you eventually do manage to write a correct version using recursion, as you attempted to do with your present version, you will find that because the iteration involved with fibonacci numbers requires looking up two previous fibonacci numbers, then for a large number of terms out, the number of recursive calls will grow exponentially. The tenth term will need the ninth and eighth terms. These in turn will need the eighth and seventh and again the seventh and sixth. This goes on all the way back to the first two terms. For terms very far out in the series the number of these repeated calls for the same previous term becomes very large indeed. That is not an efficient way to do mathematics. The fibonacci series is not a good candidate for recursion and you should use a different method. > > Roger Stafford As Roger points out, this is a terrible way to compute the Fibonacci series. However, there are good ways to do so, using a technique called memoization. In fact there are some very pretty tricks that one can use. I teach about many of them in a File Exchange submission: http://www.mathworks.com/matlabcentral/fileexchange/24022-fibonacci-and-lucas-numbers Basically, I show that simple recursion to compute the n'th Fibonacci number requires O(2^n) computations, whereas with some thought, one can reduce that to something like O(n^2) floating point operations. It actually only requires the computations of O(log(n)) memoized recursive Fibonacci evaluations. But since the n'th Fibonacci number will rapidly have thousands or even millions of digits, I end up at roughly O(n^2). A quick test, computing the 1 million'th Fibonacci number, takes only tic,F = fibonacci(1000000);toc Elapsed time is 16.575102 seconds. Since F has over 200,000 digits, this seems eminently reasonable to me. John