Elysian Shadows

wearymemory wrote:

wtetzner wrote: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.

wtetzner wrote:

wearymemory wrote:

wtetzner wrote: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 wrote:

wtetzner wrote:

wearymemory wrote:

wtetzner wrote: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.

Wikipedia wrote: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.

wtetzner wrote: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.

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

wtetzner wrote: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.

avansc wrote:

wtetzner wrote:The Fibonacci sequence is defined as:

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

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

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

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));
    }
}

aamesxdavid wrote:

jtst1 wrote: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));
    }
}