javascript: understanding the flow of a fibonacci recursive statement

Question

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.

Yes, it is returning 1 + 1 = 2. 2 is the third element in the fibonacci sequence. — CertainPerformance
– CertainPerformance, Commented Aug 21, 2018 at 2:15
@CertainPerformance if it only returns 1 or 0, how is it ever greater than 2 then? — user10108817
– user10108817, Commented Aug 21, 2018 at 2:16
Because higher calls of fib like fib(4) will result in multiple (eventual) reductions to sums of fib(1). — CertainPerformance
– CertainPerformance, Commented Aug 21, 2018 at 2:17
@user10108817 consider the case of fib(4). What does the tree of recursive calls look like then? You'll see that you can indeed get a result greater than 2. — John Ellmore
– John Ellmore, Commented Aug 21, 2018 at 2:17
To be exact, the first part fib(2) returns fib(2 -1) + fib(2 - 2) = 1 + 0. I think it's easier to write it as math function expansion: fib(3) = fib(2) + fib(0) = (fib(1) + fib(0)) + fib(0) = 2 — Yohanes Gultom
– Yohanes Gultom, Commented Aug 21, 2018 at 2:19

Hunter McMillen · Accepted Answer · 2018-08-21 02:23:35Z

1

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.

answered Aug 21, 2018 at 2:23

Hunter McMillen

61.8k25 gold badges124 silver badges176 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

user10108817 Over a year ago

what I don't quite understand though is won't , regardless of what integer used, it keep running return fib(n - 1) + fib(n - 2) until the conditional of if (n == 0) return 0; or if (n == 1) return 1; are met? Which means, how is the return ever greater than 2?

developwoof Over a year ago

because statement " return fib(n - 1) + fib(n - 2);" would add up the returned value from each iteration, and will further return to its previous iteration after the statement is executed.

Hunter McMillen Over a year ago

@user10108817 If what you are saying is true, the result would never be greater than 1.

Sylwester · Accepted Answer · 2018-08-21 03:12:10Z

1

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.

answered Aug 21, 2018 at 3:12

Sylwester

48.9k4 gold badges52 silver badges83 bronze badges

Collectives™ on Stack Overflow

javascript: understanding the flow of a fibonacci recursive statement

2 Answers 2

3 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related