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

Discussion in 'Java' started by warrenbbs@googlemail.com, Mar 12, 2008.

1. ### Guest

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

, Mar 12, 2008

2. ### Guest

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, 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

, Mar 12, 2008

3. ### Jussi PiitulainenGuest

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.

Jussi Piitulainen, Mar 12, 2008
4. ### Andreas LeitgebGuest

<> 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.

Andreas Leitgeb, Mar 12, 2008
5. ### Guest

, Mar 12, 2008
6. ### Guest

, Mar 13, 2008