febonacci numbers?

This is a discussion on febonacci numbers? within the C++ Programming forums, part of the General Programming Boards category; Code: // recursive fibonacci function #include <iostream> using namespace std; long fibonacci ( long ); int main() { long result, ...

  1. #1
    Registered User
    Join Date
    Dec 2003
    Posts
    28

    febonacci numbers?

    Code:
    // recursive fibonacci function
    #include <iostream>
    using namespace std;
    
    long fibonacci ( long );
    
    int main()
    {
        long result, number;
    
        cout << "Enter an integer: ";
        cin >> number;
        result = fibonacci( number );
        cout << "Fibonacci(" << number << ") = " << result << endl;
        return 0;
    }
    
    // Recursive definition of function fibonacci
    long fibonacci( long n )
    {
        if ( n == 0 || n == 1 )   // base case
           return n;
        else
           return fibonacci( n - 1 ) + fibonacci( n - 2 );
    }
    
    // number entered was 5
    
    // return fibonacci( n - 1 ) + fibonacci( n - 2 );
    
    // next return 4+3 = 7?
    
    // i'm confused now anyone point out my misunderstandings?
    
    // thank you.

  2. #2
    Registered User Codeplug's Avatar
    Join Date
    Mar 2003
    Posts
    4,671
    The code you posted is correct.

    What exactly do you not understand? Recursion?

    gg

  3. #3
    Registered User
    Join Date
    Mar 2002
    Posts
    1,595
    the fibonacci series is 1,1,2,3,5,8,13,21,34...

    therefore the 5th fibonacci is 5.

    The base class is often written as:

    if(n < 3)
    return 1;

    return fib(4) + fib(3);

    means return the results of fib(4) + the results of fib(3), which is not the same as return 4 + 3.

  4. #4
    Registered User
    Join Date
    Dec 2003
    Posts
    28
    I understand recursion (the basics so far so as factorials) but in my book it says this

    the fibonacci series

    0,1,1,2,3,5,8,13,21


    begins with 0 and 1 and has the property that each subsequent fibonacci number is the sum of the previous two fibonacci numbers..

    So this line here

    Code:
     return fibonacci( n - 1 ) + fibonacci( n - 2 );
    if i entered 5 into my program then it should be like this

    n-1 is 4 then it calls fibonacci again with n-2 which is 3

    so it adds these two numbers together right?

    3+4 = 7

    This is the part i'm stuck on.
    Thanks alot.

  5. #5
    Registered User Codeplug's Avatar
    Join Date
    Mar 2003
    Posts
    4,671
    3 + 4

    is not the same as

    fibonacci(3) + fibonacci(4)

    gg

  6. #6
    Registered User
    Join Date
    Dec 2003
    Posts
    28
    Hmm i understand what your saying guys but.
    I have no idea why it would give me this,(5) when it has no idea how it is getting these numbers?
    All my program knows is to take 1 away from an integer , then take two from it and add them and print to screen.

    So how does it know?
    Sorry if this seems obvious to you guys but it doesn't to me.

  7. #7
    Registered User Codeplug's Avatar
    Join Date
    Mar 2003
    Posts
    4,671
    Code:
    fibonacci(5) = fibonacci(4) + fibonacci(3)
    fibonacci(4) = fibonacci(3) + fibonacci(2)
    fibonacci(3) = fibonacci(2) + fibonacci(1)
    fibonacci(2) = fibonacci(1) + fibonacci(0)
    fibonacci(1) = 1
    fibonacci(0) = 0
    
    And we recurse back up.....
    
    fibonacci(2) = 1 + 0
    fibonacci(3) = (1 + 0) + 1
    fibonacci(4) = ((1 + 0) + 1) + (1 + 0)
    fibonacci(5) = (((1 + 0) + 1) + (1 + 0)) + ((1 + 0) + 1)
    gg

  8. #8
    Registered User
    Join Date
    Mar 2002
    Posts
    1,595
    your program will essentially add up a bunch of ones and zeros to give you an answer as it will work down each call to fib() until it reaches the base case, in which case it will return 0 if n == 0 and 1 if n == 1;


    fib(5) transforms to

    fib(4) + fib(3) transforms to

    (fib(3) + fib(2)) + (fib(2) + fib(1)) transforms to

    ((fib(2) + fib(1)) + (fib(1) + fib(0)) + ((fib(1) + fib(0) + 1) transforms to

    (((fib(1) + fib(0) + 1))) + 1 + 0 + 1 + 1 transforms to

    1 + 0 + 1 + 1 + 0 + 1 + 1 = 5

  9. #9
    Registered User
    Join Date
    Dec 2003
    Posts
    28
    Guys thanks so much for all your help and pathencie i'm able now to understand it all.

    Is this ok


    Code:
    long fibonacci( long n )
    {
        if ( n == 0 || n == 1 )   // base case
           return n;
        else
           return fibonacci( n - 1 ) + fibonacci( n - 2 );
    
    }
    number 5 was entered!


    (4)
    |
    /\
    (3) (2)
    | |
    / \ / \
    (1) (1) (1)

    (3) is first
    |
    /\
    (2) (1)
    | |
    / \ \
    (0) (1) (0) (1)



    so now 1+1+1+0+1+0+1 = 5



    I was so complicating things to much as usual,
    Thank you so much that was great help.
    Cya!
    Last edited by blackgold>>; 04-19-2004 at 12:04 PM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Question about random numbers
    By Kempelen in forum C Programming
    Replies: 2
    Last Post: 07-02-2008, 06:28 AM
  2. Help with Rational Numbers (C++)
    By cloudjc in forum C++ Programming
    Replies: 3
    Last Post: 04-28-2008, 04:03 PM
  3. Logical errors with seach function
    By Taka in forum C Programming
    Replies: 4
    Last Post: 09-18-2006, 05:20 AM
  4. the definition of a mathematical "average" or "mean"
    By DavidP in forum A Brief History of Cprogramming.com
    Replies: 7
    Last Post: 12-03-2002, 10:15 AM
  5. A (complex) question on numbers
    By Unregistered in forum C++ Programming
    Replies: 8
    Last Post: 02-03-2002, 05:38 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21