Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Java > Newbie Q: Fibonacci... how does this work?

Reply
Thread Tools

Newbie Q: Fibonacci... how does this work?

 
 
warrenbbs@googlemail.com
Guest
Posts: n/a
 
      03-12-2008
Hi

I've seen in many places the following code (or similar) to display
the nth number in the fibonacci sequence via recursion:

public class fibonacci
{
static int fib(int n)
{
if (n==0||n==1) return 1;
else {
return fib(n-1)+fib(n-2);
}
}
public static void main(String[] args)
{
System.out.print(fib(Integer.parseInt(args[0])));
}
}

It's obviously a basic piece of code, but what I'm struggling to
understand is exactly HOW it returns the correct number. I guess this
is the key line:

return fib(n-1)+fib(n-2);

I understand the underlying principle for determining the correct
number in the sequence and obviously I can see that if the input is 0
or 1 then 1 is returned, but if I enter, say, 6, how does this class
actually return 13? Can anyone show me a step-by-step of what is
happening in the recursive function?

Sorry, I realise this is a lame question, but I'd really like to get
my head round it and I'd be grateful for any insight!

thanks
warren

 
Reply With Quote
 
 
 
 
Jileshl@gmail.com
Guest
Posts: n/a
 
      03-12-2008
Hey,

Lets do it this in Mathematical way.

for
n==0 fib(0) = 1
n==1 fib(1) = 1
n==2 fib(2) = fib(1)+fib(0) = 2
n==3 fib(3) = fib(2)+fib(1)=3
n==4 fib(4) = fib(3)+fib(2)=5
n==5 fib(5) = fib(4)+fib(3)=8
n==6 fib(6) = fib(5)+fib(4)=13

---------------------------------------------

If you can understand the above mathematics...then I am sure now you
can get how this class actually works...

n==6
will be fib(6)
which will in turn calculate all fibonacci values right till f(0)....
do a step by step.... logging that would help you to understand this
more.

Regards,

Jilesh

On Mar 12, 1:31 am, (E-Mail Removed) wrote:
> Hi
>
> I've seen in many places the following code (or similar) to display
> the nth number in the fibonacci sequence via recursion:
>
> public class fibonacci
> {
> static int fib(int n)
> {
> if (n==0||n==1) return 1;
> else {
> return fib(n-1)+fib(n-2);
> }
> }
> public static void main(String[] args)
> {
> System.out.print(fib(Integer.parseInt(args[0])));
> }
>
> }
>
> It's obviously a basic piece of code, but what I'm struggling to
> understand is exactly HOW it returns the correct number. I guess this
> is the key line:
>
> return fib(n-1)+fib(n-2);
>
> I understand the underlying principle for determining the correct
> number in the sequence and obviously I can see that if the input is 0
> or 1 then 1 is returned, but if I enter, say, 6, how does this class
> actually return 13? Can anyone show me a step-by-step of what is
> happening in the recursive function?
>
> Sorry, I realise this is a lame question, but I'd really like to get
> my head round it and I'd be grateful for any insight!
>
> thanks
> warren


 
Reply With Quote
 
 
 
 
Jussi Piitulainen
Guest
Posts: n/a
 
      03-12-2008
http://www.velocityreviews.com/forums/(E-Mail Removed) writes:

> I've seen in many places the following code (or similar) to display
> the nth number in the fibonacci sequence via recursion:

....
> static int fib(int n)
> {
> if (n==0||n==1) return 1;
> else {
> return fib(n-1)+fib(n-2);
> }
> }

....
>
> It's obviously a basic piece of code, but what I'm struggling to
> understand is exactly HOW it returns the correct number. I guess
> this is the key line:
>
> return fib(n-1)+fib(n-2);
>
> I understand the underlying principle for determining the correct
> number in the sequence and obviously I can see that if the input is
> 0 or 1 then 1 is returned, but if I enter, say, 6, how does this
> class actually return 13? Can anyone show me a step-by-step of what
> is happening in the recursive function?


You can simply replace each fib(n) with whatever it returns. You can
do this because there are no assignments or other such effects to
consider. So do this:

fib(4) = fib(3) + fib(2)
= (fib(2) + fib(1)) + (fib(1) + fib(0))
= ((fib(1) + fib(0)) + 1) + (1 + 1)
= ((1 + 1) + 1) + 2
= (2 + 1) + 2
= 3 + 2
= 5

When you do this for fib(6), you will notice that you have to do the
same calls many times over, like fib(1) thrice and fib(0) twice above.
This fib(n) method is inefficient.
 
Reply With Quote
 
Andreas Leitgeb
Guest
Posts: n/a
 
      03-12-2008
(E-Mail Removed) <(E-Mail Removed)> wrote:
> return fib(n-1)+fib(n-2);


> if I enter, say, 6, how does this class
> actually return 13?


Let's begin with 4 for the principle:

fib(4) will first calculate fib(3):
fib(3) will first calculate fib(2):
fib(2) will first calculate fib(1) which is 1
fib(2) will then calculate fib(0) which is also 1
fib(2) will then add 1 + 1 which gives 2
fib(3) will then calculate fib(1) which is 1
fib(3) will then add 2 + 1 which gives 3
fib(4) will then calculate fib(2):
fib(2) will first calculate fib(1) which is 1
fib(2) will then calculate fib(0) which is also 1
fib(2) will then add 1 + 1 which gives 2
fib(4) will then add 3 + 2 which gives 5

If you've understood that, doing it for 5 and then 6 is an
apt exercise for you.

 
Reply With Quote
 
lscharen@d.umn.edu
Guest
Posts: n/a
 
      03-12-2008
> Sorry, I realise this is a lame question, but I'd really like to get
> my head round it and I'd be grateful for any insight!
>
> thanks
> warren


See this thread:

http://groups.google.com/group/comp....275679952378eb

 
Reply With Quote
 
warrenbbs@googlemail.com
Guest
Posts: n/a
 
      03-13-2008
On 12 Mar, 20:50, (E-Mail Removed) wrote:
> > Sorry, I realise this is a lame question, but I'd really like to get
> > my head round it and I'd be grateful for any insight!

>
> > thanks
> > warren

>
> See this thread:
>
> http://groups.google.com/group/comp....r/browse_threa...


Wow! Thanks to everyone - that helps a lot!
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Re: How include a large array? Edward A. Falk C Programming 1 04-04-2013 08:07 PM
VONAGE Newbie w/newbie question New_kid@nowhere.new VOIP 0 08-11-2007 01:40 PM
another newbie question from another newbie.... Lee UK VOIP 4 05-17-2005 04:10 PM
newbie: cisco vlan newbie question No Spam Cisco 3 06-07-2004 10:02 AM
Newbie! I'm a newbie! What's wrong with this program? Id0x Python 4 07-20-2003 11:40 PM



Advertisments