Fibonacci Sequence How is it Working

Question

I am confused as to how Java is running this specific code. I am comfortable with the Fibonacci sequence but not exactly with how to grapple my mind to the way this specific method is running. So obviously I'm returning 0 if n is 0 and returning 1 if n is 1. Now let us say I pass 3 for n. We return fib(2) + fib(1). How does it know what fib(2) is if it never calculated that in the first place? Does it go through the whole function again to find out what fib(2) is? When does it stop? My mind is going to blow up.

 public static int fib(int n){
    if (n == 0){
        return 0;
    }
    else if (n == 1){
        return 1;
    }
    return (fib(n-1) + fib(n-2));

}

Answer 1

You are expreiencing one of the coolest concepts in programming/math called Recursion. It can be beautiful but itcan also be a curse. At the beginning of learning recursive functions I was also driven mad by these compilcated self calling monsters but after a while I recognised how many problems can be solved much easier with recursion. So back to your problem.

So according to Wikipedia the Fibonacci sequence is

"The sequence Fn of Fibonacci numbers is defined by the recurrence relation:

F n = F n−1 + F n−2

n being the current number.

So at the beginning we callfor example

fib(3);

in the method it calls

fib(2);

then in fib(2) it calls

fib(1)

this returns 1 (because of the if) so this gets to fib(2) and fib 2 calls fib(0) results in 0 so fib(2) returns 1

Because fib(3) was interrupted by the other methods its still at the point of returning. which looks like that currently.

return 1 + fib(3 - 2)

fib(1) returns 1 so

fib returns 2 at the end

This was a bit hard to explain but I think you'll understand pretty soon.

TIP: When you cant understand how something executes use a debugger.It helps so much with visualizing data and algorithms. It helps you understand much quicker. fib(1)