febonacci numbers?

[blackgold>>]

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

[Codeplug]

The code you posted is correct.

What exactly do you not understand? Recursion?

gg

[elad]

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.

[blackgold>>]

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

 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.

[Codeplug]

3 + 4

is not the same as

fibonacci(3) + fibonacci(4)

gg

[blackgold>>]

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.

[Codeplug]

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

[elad]

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

[blackgold>>]

Guys thanks so much for all your help and pathencie i'm able now to understand it all.

Is this ok

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!