[SOLVED]

[wtetzner]

Actually I just though of a visual way to show how it works. Since fib calls two instances of itself, it creates a tree of function calls.

Code: Select all

                fib(4)
              /        \
        fib(2)    +      fib(3)
       /     \        /          \
  fib(0) + fib(1)   fib(1)   +   fib(2) 
    |       |         |          /     \  
    1       1         1       fib(0) + fib(1) 
                                 |       |  
                                 1       1

Hopefully that helps make things more clear.

The fourth Fibonacci number is 3.

Yep, and I'm using a 0-based index, so the fourth Fibonacci number is fib(3) = 3
fib(0) = 1
fib(1) = 1
fib(2) = 2
fib(3) = 3
fib(4) = 5

[wearymemory]

Actually I just though of a visual way to show how it works. Since fib calls two instances of itself, it creates a tree of function calls.

Code: Select all

                fib(4)
              /        \
        fib(2)    +      fib(3)
       /     \        /          \
  fib(0) + fib(1)   fib(1)   +   fib(2) 
    |       |         |          /     \  
    1       1         1       fib(0) + fib(1) 
                                 |       |  
                                 1       1

Hopefully that helps make things more clear.

The fourth Fibonacci number is 3.

Yep, and I'm using a 0-based index, so the fourth Fibonacci number is fib(3) = 3
fib(0) = 1
fib(1) = 1
fib(2) = 2
fib(3) = 3
fib(4) = 5

I've always read that f0 = 0, and f1 = 1, are the two seeds to the Fibonacci Sequence.
Also, the OP's code returns 1 if n is less than 3. I guess that lead me to believe that your diagram was wrong. Sorry 'bout that.

[wtetzner]

Actually I just though of a visual way to show how it works. Since fib calls two instances of itself, it creates a tree of function calls.

Code: Select all

                fib(4)
              /        \
        fib(2)    +      fib(3)
       /     \        /          \
  fib(0) + fib(1)   fib(1)   +   fib(2) 
    |       |         |          /     \  
    1       1         1       fib(0) + fib(1) 
                                 |       |  
                                 1       1

Hopefully that helps make things more clear.

The fourth Fibonacci number is 3.

Yep, and I'm using a 0-based index, so the fourth Fibonacci number is fib(3) = 3
fib(0) = 1
fib(1) = 1
fib(2) = 2
fib(3) = 3
fib(4) = 5

I've always read that f0 = 0, and f1 = 1, are the two seeds to the Fibonacci Sequence.
Also, the OP's code returns 1 if n is less than 3. I guess that lead me to believe that your diagram was wrong. Sorry 'bout that.

http://en.wikipedia.org/wiki/Fibonacci_number

By definition, the first two Fibonacci numbers are 0 and 1, and each remaining number is the sum of the previous two. Some sources omit the initial 0, instead beginning the sequence with two 1s.

I've read that it starts with two ones, but apparently it's been defined both ways.
In any case, hopefully the diagram will make it easier to understand recursion.

[Ginto8]

Actually I just though of a visual way to show how it works. Since fib calls two instances of itself, it creates a tree of function calls.

Code: Select all

                fib(4)
              /        \
        fib(2)    +      fib(3)
       /     \        /          \
  fib(0) + fib(1)   fib(1)   +   fib(2) 
    |       |         |          /     \  
    1       1         1       fib(0) + fib(1) 
                                 |       |  
                                 1       1

Hopefully that helps make things more clear.

you forgot to add a check for whether n < 3...

And to the original poster(jtst1), this saying sums up recursion: "In order to understand recursion, you must first understand recursion".

[wtetzner]

you forgot to add a check for whether n < 3...

What? Both fib(0) and fib(1) evaluate to 1 in the diagram.

[avansc]

The Fibonacci sequence is defined as:

Code: Select all

fib(0) = 1
fib(1) = 1
fib(n) = (n - 2) + (n - 1) for n > 1

(Note that the above is not code, just the mathematical definition.)

What this says is that fib(0) returns 1, fib(1) returns 1, and for every integer n that is above 1, fib(n) returns the sum of the previous two values in the sequence.
So let's compute fib(2).

Code: Select all

Now, fib(n) = fib(n - 2) + fib(n - 1)
Then fib(2) = fib(2 - 2) + fib(2 - 1)
So   fib(2) = fib(0) + fib(1)
     fib(2) = 1 + 1, since fib(0) = 1 and fib(1) = 1

So when you write the function in code, you need to check if n = 0 or if n = 1. These are called the base cases or termination conditions. That's because they are not defined in terms of fib, so when you get a value n that is 0 or 1, it stops the recursion.
Everything else is defined in terms of fib.

Say you call fib with n = 4.
So fib(4) = fib(4 - 2) + fib(4 - 1)
Then fib(4) = fib(2) + fib(3)
Now fib(2) and fib(3) need to be computed in order to find fib(4).
So we compute fib(2):
fib(2) = fib(2 - 2) + fib(2 - 1)
fib(2) = fib(0) + fib(1)
So now we need to compute fib(0) and fib(1) to find fib(2)
But both fib(0) and fib(1) return 1. These are the base cases, since they don't call fib again.
So now we can finish computing fib(2).
fib(2) = fib(0) + fib(1)
fib(2) = 1 + 1
fib(2) = 2
Now we need fib(3) to finish computing fib(4), which we started computing above.
So fib(3) = fib(3 - 2) + fib(3 - 1)
fib(3) = fib(1) + fib(2)
Now we need to compute fib(1) and fib(2) to find fib(3).
fib(1) is a base case, and returns 1.
Computing fib(2) is the same as fib(2) above, which we discovered returns 2.
So fib(3) = fib(1) + fib(2)
fib(3) = 1 + 2
fib(3) = 3
Now we know both fib(2) and fib(3), so we can finish computing fib(4)
fib(4) = fib(2) + fib(3)
fib(4) = 2 + 3
fib(4) = 5

Hopefully I wasn't too unclear. The example was kind of long, but if you follow each step, you should be able to understand the process.

is it just me... or does this look almost exact to what i wrote....

[dandymcgee]

The Fibonacci sequence is defined as:

is it just me... or does this look almost exact to what i wrote....

Well, you are both trying to explain the same thing.

[jtst1]

Hey everyone, I didn't expect this many people to reply lol. I understand it now basically.

"In order to understand recursion, you must first understand recursion"

rofl yeah. Can i ask why it has to have n < 3?

[aamesxdavid]

Can i ask why it has to have n < 3?

Because the first two numbers have to be listed as "1".

That's how the whole sequence starts, and without putting fib(1) and fib(2) as "1", the program has nothing to go on for adding the rest of the numbers up. Is it this one?

Code: Select all

int fib(int n);

int main()
{
    int n, answer;
    cout << "Enter number to find: ";
    cin >> n;

    cout << "\n\n";

    answer = fib(n);

    cout << answer << " is the " << n << "th Fibonacci number.\n";

    return 0;
}

int fib(int n)
{
    cout << "Processing fib(" << n << ")... ";

    if (n < 3)
    {
        cout << "Return 1!\n";
        return (1);
    }
    else
    {
        cout << "Call fib(" << n-2 << ") and fib (" << n-1 << "). \n";
        return(fib(n-2) + fib(n-1));
    }
}

[jtst1]

Can i ask why it has to have n < 3?

Because the first two numbers have to be listed as "1".

That's how the whole sequence starts, and without putting fib(1) and fib(2) as "1", the program has nothing to go on for adding the rest of the numbers up. Is it this one?

Code: Select all

int fib(int n);

int main()
{
    int n, answer;
    cout << "Enter number to find: ";
    cin >> n;

    cout << "\n\n";

    answer = fib(n);

    cout << answer << " is the " << n << "th Fibonacci number.\n";

    return 0;
}

int fib(int n)
{
    cout << "Processing fib(" << n << ")... ";

    if (n < 3)
    {
        cout << "Return 1!\n";
        return (1);
    }
    else
    {
        cout << "Call fib(" << n-2 << ") and fib (" << n-1 << "). \n";
        return(fib(n-2) + fib(n-1));
    }
}

Yeah that was the code.

[RoJaMi]

SO JoTaSt, have you figured out your problem?

[jtst1]

It's jtst1, and yes if you read on up.