Fibonacci and Memoization

Jason Lim
Jason Lim
Jul 23, 2018 · 4 min read
source: mathisfun.com

During a recent coding test I was asked to write a function that returns the Fibonacci number at given index. For those unfamiliar, the Fibonacci sequence is a series of numbers starting with 0 and 1. The following numbers are found by adding up the last two numbers. From index 0 to 9, the series is 0, 1, 1, 2, 3, 5, 8, 13, 21, 34. I was able to do this successfully through an iterative method.

// iterative solution - O(n)function fib(n) {
let fibo = [0, 1]
for(let i = 2; i <= n; i ++) {
let res = fibo[i - 1] + fibo[i - 2]
fibo.push(res)
}
return fibo[fibo.length - 1]
}

Next, I was asked if I could implement this function in a recursive fashion. I sat there for a few minutes trying to figure out what my base case would be and how I would recurse toward the base case. However, I could not solve this.

Following the coding test I immediately went to searching for how to write a Fibonacci function recursively. The answer I found at multiple sources looked like this.

function fib(n) {
if (n < 2) {
return n
}
return fib(n - 1) + fib(n - 2)
}

Now I knew the answer to this particular question if asked. The function itself is easy to remember. However, I wanted to understand this implementation better.

Recursion in general can be a bit hard to wrap your head around. To aid in analyzing this function I diagramed it below.

From this visualization you can see the recursive implementation reaches the correct answer through the addition of 1s (and 0s). It’s good to understand recursion by visualizing the call stack. In the case of fib(4), function fib is called 9 times. For a computer keeping track of the fib function 9 times is not a huge burden, so this is not a big deal.

It will become a big deal as the entered index increases. Let’s look at the visualization of fib(5).

Incrementing the index by 1 raised the number of fib calls to 15. You can imagine what problem this will raise once we want to find the Fibonacci number at higher indexes. Its complexity in Big O notation is O(2^n).

// recursive solution - O(2^n)function fib(n) {
if (n < 2) {
return n
}
return fib(n - 1) + fib(n - 2)
}

The same thing I noticed while creating the visualization was the repeated fib(n) calls. When fib(5) recurses down to fib(4) and fib(3), fib(4) will recurse down again to fib(3) and fib(2). I thought, if there is a way to store the return value of fib(3) then the other fib(3) can just refer to the stored value and not recurse. What I wanted to achieve is called memoization.


Memoization

In computing, memoization or memoisation is an optimization technique used primarily to speed up computer programs by storing the results of expensive function calls and returning the cached result when the same inputs occur again.

https://en.wikipedia.org/wiki/Memoization

// generic memoization functionfunction memoize(fn) {
let cache = {}
return function(...args) {
if (cache[args]) {
return cache[args]
}
const res = fn.apply(this, args)
cache[args] = res
return res
}
}
// apply memoization to fib functionfib = memoize(fib)

The above memoization function can be used to memoize any function. As you can see there is an object called cache which we will be using to store our return values. It will check if the cache has a reference to the argument and if not then it will the apply the function to the argument and then store the return value. This will reduce the number of recursive calls and the visualization should look something like this.

O(n) + O(1) = O(n)

Jason Lim

Written by

Jason Lim

jason-lim.info

More From Medium

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade