A common theme in dynamic programming algorithm questions on Leetcode or in job interviews, is that the underlying problem is some twist on or manipulation of the numbers of the Fibonacci sequence. The Fibonacci sequence is a series of numbers where the next number is the sum of the previous two. Normally it starts at 0,1 followed by 1,2,3,5,8,13,21 and so on. To find the nth number of a Fibonacci sequence, we can use a for loop to sum it up iteratively using something like the following:

const fib = (n) => {
if (n === 1) return 0;
let prevprev;
let prev = 0;
let fibNumber = 1;
for (let i = 2; i < n; i++) {
prevprev = prev;
prev = fibNumber;
fibNumber = prevprev + prev;
}
return fibNumber;
}

Recursive Fibonacci

The most basic recursive way to solve for the nth Fibonacci number is to keep on making recursive calls to find the previous two numbers in the series until we hit the stopping point of fib(1) or fib(2) as we know those are our two starting numbers of 0 and 1. The code for this would look something like the following :

const fib = (n) => {
if (n === 1) return 0;
if (n === 2) return 1;
return fib(n-1) + fib(n-2);
}
https://stackoverflow.com/questions/35959100/explanation-on-fibonacci-recursion

Memoization

Memoization, or memo for short, is a technique we can use to store certain values as we go to save ourselves from going down paths we already know the answer to. To add memoization to the recursive code we have above, we need to add an object to our recursion to store the values we’ve discovered. This only requires a couple extra lines of code but saves us a tremendous amount of runtime.

const fib = (n, memo ={}) => {
if (n === 1) return 0;
if (n === 2) return 1;
if (n in memo) return memo[n];
memo[n] = fib(n-1, memo) + fib(n-2, memo);
return memo[n];
}

Current Web Development student at https://flatironschool.com/

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store