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

[warrenbbs]

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

 

[Jileshl]

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

 

[Jussi Piitulainen]

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.

 

[Andreas Leitgeb]

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.

 

[lscharen]

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...89395386b3/08275679952378eb?#08275679952378eb

 

[warrenbbs]

See this thread:

http://groups.google.com/group/comp.lang.java.programmer/browse_threa...

Wow! Thanks to everyone - that helps a lot!