Fibonacci recursion

[sethman410]

Hey. Please explain how this recursion works.

  int fib(int n)
{
	if (n <= 0)							// Base case
		return 0;
	else if (n == 1)					// Base case
		return 1;
	else
		return fib(n-1) + fib(n - 2);		// Recursive case
}

For the first ten numbers, the output would be like this: 0 1 1 2 3 5 8 13 21 34

Ok, very confused about this because let's say for example the 3 is the n for now and shouldn't the next number be 3? It should be infinite looping itself. Because 3 - 1 is 2 and 3 - 2 is 1 therefore 2 + 1 is 3. See my perspective? How about for 13, 13 - 1 is 12 and 13 - 2 is 11 and therefore the next n should be 23 but instead it's 21.

I don't understand where 2, 3, 5, 13, 21, or 34 comes from. For number 8 though, it's the only one that makes sense to me because (8-1) + (8-2) is 13 and indeed it is displaying 13 as the next number.

So how does this recursion really work? How is it doing its math?

[Chervil]

It can be hard to explain. But of course the fundamental principle of recursion is that the function may call itself. In this case the number of calls can become very large.

Here's an example for fib(5) which happens to give the result 5, though the actual number is quite tricky to understand, because of the number of calls involved. At first, fib(5) is calculated as the sum of fib(4) + fib(3). Well, it can't actually do the addition immediately, as each of the two expressions must itself be evaluated first. Hence fib(4) is evaluated as the sum of fib(3) + fib(2) and so on.

                                     Fib(5)
                                     
                     Fib(4)            +              Fib(3)
                     
            Fib(3)     +     Fib(2)    +     Fib(2)     + Fib(1)
            
    Fib(2)    + Fib(1) + Fib(1)+Fib(0) + Fib(1)+Fib(0)  +   1
    
Fib(1)+Fib(0) +   1    +   1   +  0    +   1   +  0     +   1

  1   +  0    +   1    +   1   +  0    +   1   +  0     +   1

As you can see, the final result is the sum of a lot of 1 and 0 values, which adds up to 5.

I was going to illustrate fib(6) which follows the same principles, giving 8 as the result, but it was growing too wide to fit on the screen comfortably.

[Chervil]

Well, ok, since you said fib(6) which gives the result 8 was the only one which made sense, here's the way that is calculated:

                                                               Fib(6)
                                    Fib(5)                       +                      Fib(4)
                    Fib(4)             +             Fib(3)      +             Fib(3)     +     Fib(2)
           Fib(3)      +     Fib(2)    +     Fib(2)    +  Fib(1) +     Fib(2)    + Fib(1) + Fib(1)+Fib(0)
    Fib(2)    + Fib(1) + Fib(1)+Fib(0) + Fib(1)+Fib(0) +   1     + Fib(1)+Fib(0) +   1    +   1   +  0
Fib(1)+Fib(0) +   1    +   1   +  0    +   1   +  0    +   1     +   1   +  0    +   1    +   1   +  0
  1   +  0    +   1    +   1   +  0    +   1   +  0    +   1     +   1   +  0    +   1    +   1   +  0