I can't wrap my head around the simple Fibonacci fn?

JavaScript
1

Hi all,

I’ve been working my way through some dynamic programming curriculum and have just been hitting a wall trying to understand the simple Fibonacci function below which aims to find the nth number in the series:

let fibonacci = (num) => {
  if (num < 2) return num;

  let oneBefore = fibonacci(num - 1)
  let twoBefore = fibonacci(num - 2);
  let numInSequence = oneBefore + twoBefore

  console.log({ oneBefore, twoBefore, numInSequence })

  return numInSequence
}

Now, I understand how the Fibonacci sequence works (ie) add the last two numbers in the series together ( 1, 1, 2, 3, 5, 8, 13 ).

So, when I run this function to find the number in the sequence it works BUT, I don’t understand how the number is generated when working. For example, I run the following examples:

// these make sense
fibonacci(3) // { oneBefore: 1, twoBefore: 1, numInSequence: 2 }
fibonacci(4) // { oneBefore: 2, twoBefore: 1, numInSequence: 3 } 

// these don't make sense 
fibonacci(6) // { oneBefore: 5, twoBefore: 3, numInSequence: 8 }
fibonacci(7) // { oneBefore: 8, twoBefore: 5, numInSequence: 13 }

The last two there don’t make sense anymore, because the variables oneBefore and twoBefore no longer correspond with the literal calculation of n - 1 and n - 2 respectively…

I know this is probably a dumb question… but what am I missing here?

2

Sometimes its best to trace these recursive examples with pen and paper. Your fibonacci(6) example only shows the last log statement. I modified your code to print more:

let call = 0;

let fibonacci = (num) => {
  call++;
  if (num < 2) {
    console.log(`call: ${call} num: ${num}`);
    return num;
  }

  let oneBefore = fibonacci(num - 1)
  let twoBefore = fibonacci(num - 2);
  let numInSequence = oneBefore + twoBefore

  console.log(`call: ${call} num: ${num} oneBefore: ${oneBefore} twoBefore: ${twoBefore} numInSequence: ${numInSequence}`);

  return numInSequence
}

and for console.log(fibonacci(6) it prints

call: 6 num: 1
call: 7 num: 0
call: 7 num: 2 oneBefore: 1 twoBefore: 0 numInSequence: 1
call: 8 num: 1
call: 8 num: 3 oneBefore: 1 twoBefore: 1 numInSequence: 2
call: 10 num: 1
call: 11 num: 0
call: 11 num: 2 oneBefore: 1 twoBefore: 0 numInSequence: 1
call: 11 num: 4 oneBefore: 2 twoBefore: 1 numInSequence: 3
call: 14 num: 1
call: 15 num: 0
call: 15 num: 2 oneBefore: 1 twoBefore: 0 numInSequence: 1
call: 16 num: 1
call: 16 num: 3 oneBefore: 1 twoBefore: 1 numInSequence: 2
call: 16 num: 5 oneBefore: 3 twoBefore: 2 numInSequence: 5
call: 20 num: 1
call: 21 num: 0
call: 21 num: 2 oneBefore: 1 twoBefore: 0 numInSequence: 1
call: 22 num: 1
call: 22 num: 3 oneBefore: 1 twoBefore: 1 numInSequence: 2
call: 24 num: 1
call: 25 num: 0
call: 25 num: 2 oneBefore: 1 twoBefore: 0 numInSequence: 1
call: 25 num: 4 oneBefore: 2 twoBefore: 1 numInSequence: 3
call: 25 num: 6 oneBefore: 5 twoBefore: 3 numInSequence: 8
8

and now you can work backwards from the bottom, finding the line for num: 5 and num: 3 and so on. Every line is the same; add the previous two numbers to get the next, so everything is correct. With recursion, you just have to be able write out or visualize the nested calls to see the pattern.

Hope this helps.

3

Thanks for the help on understanding the multiple calls involved. That really helps. I need to work more on visualizing the function and recursion :slight_smile: I did do some googling and I came across this really helpful tool to visualize the function in action -> https://www.cs.usfca.edu/~galles/visualization/DPFib.html

4

freeCodeCamp.org youtube channel has video on dynamic programming https://www.youtube.com/watch?v=oBt53YbR9Kk with fibonacci used as one of the examples.

For visualizing function execution there’s also handy tool http://pythontutor.com/javascript.html which shows each step in the code.

1 Like
5

Thanks that is a really great video, a lot of super high quality content! I recently bought the JavaScript Algorithms and Data Structures course on Udemy which is very well done and the chapter on recursion has helped a ton. I highly recommend it.