CODEWITHSUNDEEP
javascriptrecursion
user10108817
user10108817

Reputation: 285

javascript: understanding the flow of a fibonacci recursive statement

I eventually want to get the hang of dynamic programming but before that, I am having a hard time understanding the flow of this. I understand recursion but I'm having trouble understanding the flow of this:

function fib(n) {
  if (n == 0) return 0;
  if (n == 1) return 1;
  return fib(n - 1) + fib(n - 2);
}
console.log(fib(3));

if I have a small integer of 3, it does not pass those 2 conditionals so it hits return fib(n-1)+fib(n-2); So to my understanding, that will go through the first part of that first: fib(n-1) (3-1 = 2)... 2 does not satisfy either of those conditionals so it runs fib(n-1) (2-1 = 1). 1 DOES satisfy one of the conditionals so it returns 1 and breaks that part of it.

Now to to the next part: fib(n-2) . (3-2 = 1). 1 does satisfy one of the conditionals so it returns 1 . So in the end, isn't that returning 1 + 1 ?

I'm not sure where I'm going wrong in my understanding.

Upvotes: 0

Views: 58

Answers (2)

Sylwester
Sylwester

Reputation: 48745

One of my favorite ways to do this is to start with the base cases and go backwards:

fib(0); // => 0
fib(1); // => 1

Then we get to the default case:

fib(2); // == fib(1) + fib(0) == 1 + 0 ==> 1
fib(3); // == fib(2) + fib(1) == 1 + 1 ==> 2
fib(4); // == fib(3) + fib(2) == 2 + 1 ==> 3

This is much easier than trying to figure out fib(4) first since you need to nest. Looking at the function it's easy to see what to try.

Also know that calls to the same function doesn't get any special treatment. It runs until it returns with a value and it's arguments and local variables are local to the call so every fib call has its own n and it waits for the two calls to return to sum the results.

Upvotes: 1

Hunter McMillen
Hunter McMillen

Reputation: 61510

You are correct in that fib(3) should return 2, because 2 is the 3rd number in the Fibonacci sequence (starting at 0)

It helps to write out it out as tree:

       fib(3)
      /     \
    fib(2)   fib(1)
   /     \     \
 fib(1) fib(0)  1
 /        \  
1          0

above you can see how each recursive call goes all the way to 0 or 1 before returning a result back up the previous layer.

Upvotes: 1

Related Questions