Got Questions? Get Answers.
Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
Fibonacci

Subject: Fibonacci

From: Jake

Date: 11 Apr, 2010 04:19:03

Message: 1 of 8

function fib(n)

int n;

if(n==0 ) return;
    
else return n * fib(n-1); // line 7
    

I ran it

>> fib(8)
??? Error: File: fib.m Line: 7 Column: 13
Missing MATLAB operator.


Please help me

Subject: Fibonacci

From: James Tursa

Date: 11 Apr, 2010 05:09:03

Message: 2 of 8

"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
>
>
> I ran it
>
> >> fib(8)
> ??? Error: File: fib.m Line: 7 Column: 13
> Missing MATLAB operator.

Looks like you took a C routine, called it an m-file, and ran it. There is no int data type in MATLAB. To return a variable you put it as part of the function line and then set it to a value in the routine ... it is not part of the return statement. Comments use % , not //. You should read the Getting Started and Functions section of the doc.

James Tursa

Subject: Fibonacci

From: Matt Fig

Date: 11 Apr, 2010 05:10:06

Message: 3 of 8

What you typed above is NOT MATLAB syntax. See the help for IF and RETURN. At the command line, type:

>> help if
>> help return

Also, perhaps reading the 'Getting Started' section would help.

Subject: Fibonacci

From: Roger Stafford

Date: 11 Apr, 2010 06:00:22

Message: 4 of 8

"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

Subject: Fibonacci

From: Roger Stafford

Date: 11 Apr, 2010 08:59:04

Message: 5 of 8

"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

  I confess I was a little too disparaging of the recursion method. In point of fact there is a way of making recursive calls for generating the fibonacci series which avoids the difficulties I previously mentioned. You simply have to require that each call return a pair of consecutive fibonacci numbers..

Roger Stafford

Subject: Fibonacci

From: John D'Errico

Date: 11 Apr, 2010 09:24:03

Message: 6 of 8

"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

Subject: Fibonacci

From: james bejon

Date: 11 Apr, 2010 20:03:04

Message: 7 of 8

>> As Roger points out, this is a terrible way to compute the Fibonacci series.

Here's an even worse way, in case you're interested (just something I was playing around with)!

n = 100;
subs = cumsum([transpose(1:n), ones(n, n-1)], 2);
val = abs(pascal(n, 1));
fib = accumarray(subs(:), val(:));
fib = fib(1:n);

Subject: Fibonacci

From: Loren Shure

Date: 12 Apr, 2010 14:45:06

Message: 8 of 8

In article <hpt9tn$87l$1@fred.mathworks.com>, jamesbejon@yahoo.co.uk
says...
> >> As Roger points out, this is a terrible way to compute the Fibonacci series.
>
> Here's an even worse way, in case you're interested (just something I was playing around with)!
>
> n = 100;
> subs = cumsum([transpose(1:n), ones(n, n-1)], 2);
> val = abs(pascal(n, 1));
> fib = accumarray(subs(:), val(:));
> fib = fib(1:n);
>

more methods here:
http://blogs.mathworks.com/loren/2006/05/17/fibonacci-and-filter/


--
Loren
http://blogs.mathworks.com/loren
http://matlabwiki.mathworks.com/MATLAB_FAQ

Tags for this Thread

No tags are associated with this thread.

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us