views:

490

answers:

10

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.

+19  A: 

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.

Software Monkey
it still isn't making sense sorry. i see that you bolded the two 4's but i don't see where they came from. both of those 4's are 5-1, but the code makes it look like it wants 5-1 and 5-2 like i said above.
David
+1 just for 'drawing' what I'd try to explain.
Bobby
@David: Read my answer - I walk through it in each step... Does that help?
Reed Copsey
@David: Reed Copsey's and matt b's answers provide a slightly different angle which should help.
Software Monkey
+3  A: 
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.

Tanzelax
+4  A: 

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.

Carl Manaster
+6  A: 

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.

Reed Copsey
this plus matt's comment was usefull thanks for the help
David
+2  A: 

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

tvanfosson
+19  A: 

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
matt b
thanks this helped alot. when i wrote it out i was getting 5 for a bit but when i read this i realized that i was forgetting to turn fib (0) into 1. thank you
David
+2  A: 

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
Daniel Pryden
+2  A: 

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
Claudiu
the second fibbanachi number is 1
David
whats your point? f[1] is the 2nd number.
Claudiu
+4  A: 

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

alt text

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)))
  )
outis
what do lisp and Scheme mean?
David
Lisp (http://en.wikipedia.org/wiki/Lisp_%28programming_language%29) is a family of languages. The name is short for "LISt Processor". Scheme is one variety of Lisp. Others include Common Lisp, Emacs Lisp and Clojure. Languages in the Lisp family have a very simple syntax (just about everything is a list contained in parentheses and separated by whitespace) but very powerful features.
outis
xkcd sums it up well: http://xkcd.com/297/. See also the "What Made Lisp Different" section of http://www.paulgraham.com/icad.html
outis
A: 

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

Peter Lawrey
the reason it is an 8 has nothing to do with it being a fibonacci number. "fibanacci numbers" are an imposed charactaristic of a set of numbers. That it retuirns an 8 is the result of semanticaly what the program means. It does not return an 8 because it is suposed to because i want it to return fibonacci numbers
David
@David "the reason it is an 8 has nothing to do with it being a fibonacci number". I thought you wrote a function called fibonacci which calculates fibonacci numbers because you expect it to return a fibonacci number, but you tell me this has nothing to do with fibonacci numbers...?! Could you rephrase your last statement, I feel like a "not" is missing because it makes no sense to me.
Peter Lawrey
no the original comment is right. Your answer seems to implicitly make wrong metaphysical assumptions. my original question is obviously one of semantics.
David
So your question is; I know the answer is correct but why is it not an incorrect answer, i.e. why does it work? In that case, I suggest you learn to use a debugger. (usually next to the Run button on your IDE) This will allow you to step through each stage of your program, see values and results and help you see not just how this program work, but any program works. The debugger is the best tool for answering the question: Why doesn't the program do what I think it should.
Peter Lawrey