How did this get 8?

Question

Here's the code:

class qual
{
    public static int fibonacci(int n)
    { 
        if (n == 0 || n == 1) 
        { 
            return 1; 
        } 
        else 
        { 
            return fibonacci(n-1) + fibonacci(n-2); 
        } 
    } 

    public static void main(String[] arg) 
    {
        System.out.println(fibonacci(5));
    }
}

The output was 8. The output should be 8 but when I look at this I think it should be 7 ((5-1) +(5-2)).

Why was the output 8? I think the reasoning behind getting 8 will make recursion maybe stop being confusing for me.

Answer 1

Let's treat this like algebra, I'll write f(n) instead of fibonacci(n) to save space:

f(5) = f(4) + f(3)
f(5) = f(3) + f(2) + f(2) + f(1)
f(5) = f(2) + f(1) + f(1) + f(0) + f(1) + f(0) + f(1)
f(5) = f(1) + f(0) + f(1) + f(1) + f(0) + f(1) + f(0) + f(1)
f(5) =  1   +  1   +  1   +  1   +  1   +  1   +  1   +  1

Answer 2

Because it's a recursive call, so each call where the argument is not 0 or 1 calls it again.

fibonacci(7)
-> fibonacci(6) // recursively calls itself with (7-1)
   -> fibonacci(5) // recursively calls itself with (6-1)
      -> fibonacci(4) // recursively calls itself with (5-1)
         -> fibonacci(3) // recursively calls itself with (4-1)
            -> fibonacci(2) // recursively calls itself with (3-1)
               -> fibonacci(1) // recursively calls itself with (2-1)
   -> fibonacci(4) // recursively calls itself with (6-2)
        ...
-> fibonacci(5) // recursively calls itself with (7-2)
   -> fibonacci(4) // recursively calls itself with (5-1)
      -> fibonacci(3) // recursively calls itself with (4-1)
         -> fibonacci(2) // recursively calls itself with (3-1)
            -> fibonacci(1) // recursively calls itself with (2-1)
   -> fibonacci(3) // recursively calls itself with (5-2)
      ...

and so on.

Think about the logic like this, and you should be able to work out what it actually returns to the initial caller.

Answer 3

It's returning fibonacci(n-1), not n-1. When you call this with 5, you get:

return fib(4) + fib(3);

fib(4) returns:

return fib(3) + fib(2);

fib(3) returns:

return fib(2) + fib(1);

fib(2) returns:

return fib(1) + fib(0);

As soon as you reach fib(1) or fib(0), you return 1;

Working backwards, fib(2) returns 2:

return 1 /*fib(1)*/ + 1 /*fib(0)*/;

By the same logic, fib(3) returns 2 + 1, or 3. Fib(4) returns 3 + 2, or 5. Fib(5) therefor returns 5 + 3, which is your 8.

Answer 4

Perhaps this illustration adapted from the Structure and Interpretation of Computer Programs (SICP, or the Wizard book) will help:

Going off on a tangent, SICP is a fantastically deep though at times difficult introduction to programming. Since it uses Lisp (rather, Scheme) as its teaching language, recursion is used throughout. Even iterative processes in Lisp are based on recursive calls:

(define (factorial n)
  (define (fact-iter n product)
    (if (> n 1) 
        (fact-iter (- n 1) (* product n))
        product
  ) )
  (fact-iter n 1)
)

(factorial 5)
; returns 120

is actually iterative. Notes: car returns the head of a list, while cdr returns the tail. Operators use prefix notation; (- a b) is "a - b", (* a b) is "a * b".

Here's what your Fibonacci program looks like in Scheme:

(define (fibonacci n)
  (if (or (= n 1) (= n 2))
      1
      (+ (fibonacci (- n 1)) (fibonacci (- n 2)))
  )

Answer 5

It's not ((5-1) + (5-2)), but rather (finonacci(5-1) + fibonacci(5-2))

And finonacci(5-1) reduces to fibonacci(4), which becomes (finonacci(4-1) + fibonacci(4-2)), etc.

Answer 6

return fibonacci (n-1) + fibonacci (n-2); 

That's actually not just doing (n-1) + (n-2), it's recursively calling the fibonnacci function again.

So it's doing fibonacci (4) + fibonacci (3). That fib(4) is then evaluated to be fib(3) + fib(2), so it ends up returning fib (3) + fib (2) + fib (3). Again, each of those fib(3)'s are actually fib (2) + fib (1), and so on. It keeps breaking down like that, until it hits

if (n == 0 || n == 1)

so it ends up being a bunch of fib (1) + fib (0) + fib (1)..., which is 1 + 1 + 1..., which will end up as 8 if you actually break it all the way down.

Answer 7

I haven't seen this approach yet. Imagine you are storing results and building it up, where f[i] is the result of calling fibonacci(i). 0 and 1 are base cases, and the rest build on it:

f[0] = 1
f[1] = 1
f[2] = f[1] + f[0] = 1 + 1 = 2
f[3] = f[2] + f[1] = 2 + 1 = 3
f[4] = f[3] + f[2] = 3 + 2 = 5
f[5] = f[4] + f[3] = 5 + 3 = 8

Answer 8

The result of the function is not (5 - 1) + (5 - 2), but fibonacci( 5 - 1 ) + fibonacci( 5 - 2 ) or fibonacci( 4 ) + fibonacci( 3 ), which is 5 + 3. The sequence is:

1 1 2 3 5 8

0 1 2 3 4 5

Answer 9

Recursion is actually closely related to the mathematical concept of proof by induction -- and in fact the Fibonacci sequence is recursively defined, so on some level you have to already think in recursive terms to understand how it works.

To better understand the code, you can apply a beta reduction -- that is, replace each function call with the body of the function itself.

If fibonacci(n) translates to fibonacci(n - 1) + fibonacci(n - 2) then:

fibonacci(5) = fibonacci(4) + fibonacci(3)
fibonacci(5) = (fibonacci(3) + fibonacci(2)) + (fibonacci(2) + fibonacci(1))

It's easy to see that this would go on forever, unless we made a special case. Here, we know that fibonacci(1) translates to 1, and fibonacci(0) also translates to 1. So we keep beta-reducing until all we have left are ones, which looks like:

fibonacci(5) = ((1 + 1) + (1 + (1 + 1))) + ((1 + 1) + 1)

Therefore:

fibonacci(5) = 8

Answer 10

The first fibonacci number are 1,1,2,3,5,8,... any other numbers would be unexpected.