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
    #1
    1. Advertising

  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
    #2
    1. Advertising

  3. 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
    #3
  4. <> 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
    #4
  5. Guest

    , Mar 12, 2008
    #5
  6. Guest

    , Mar 13, 2008
    #6
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Brett Trost

    Fibonacci problem

    Brett Trost, Jan 22, 2004, in forum: Perl
    Replies:
    2
    Views:
    1,025
  2. fighterman19
    Replies:
    11
    Views:
    859
    Karl Heinz Buchegger
    Sep 8, 2003
  3. Fibonacci numbers

    , Oct 10, 2003, in forum: C++
    Replies:
    28
    Views:
    1,393
    yousafzai
    Jun 5, 2011
  4. Alex Vinokur
    Replies:
    0
    Views:
    471
    Alex Vinokur
    Oct 29, 2003
  5. salai
    Replies:
    8
    Views:
    170
    Jay Anderson
    Jul 14, 2009
Loading...

Share This Page