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

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

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

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

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.

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.

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

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

>
>

Wow! Thanks to everyone - that helps a lot!