If you’re not aware,or need a refresher… What’s a fibonacci number?

Usually a question asked in interviews to prompt the responder to talk about recursion and show how they would implement it like that `fib(n) = fib(n - 1) + fib(n - 2)`. In short it’s not the best solution (hint: performance)… and that’s all i’m going to say about that.

## The Solution

Solving fibonacci has been done to death. I’m sure somebody else has already written up a similar solution, maybe even verbatim… either way, the following is based on what’s in my mind hole and i just wanted to put it out there.

``````var fib = (function () {
var  cache = [0,1];
return function (n) {
var i = cache.length,
il = n + 1;
for (; i < il; i += 1) {
cache[i] = cache[i - 1] + cache[i - 2];
}
return cache[n];
}
}());
``````

### You did what now?

• Run an anonymous function

• It creates a closure for `cache` and initialises the array to `[0,1]` (the first 2 values of fibonacci).
• It then returns a `function`, which becomes `fib`. The `cache` of fibonacci values can be accessed in the returned function.
• When we call `fib(n)`

• It cycles through the loop starting at the length of the `cache` array until it’s reached, but not evaluated `n + 1`.
• It then returns the `n`th number from `cache`.

### What makes this good?

• The calculation is linear. Using an array to calculate the current value based on the sum of the previous 2 values, the performance is linear (it takes as long as one for loop takes to get to n).
• It “learns” by storing the calculated values in `cache` which is accessible every time you call `fib `with any value. Which means you’ll get a performance increase the more times you run it. ie. If you’ve already run `fib(10)` and then you run `fib(6)` it won’t run the for loop at all, and will just return the value of `cache`

### Here are it’s negatives, (from what i can see)

• The anonymous function is always run, even if you don’t use `fib(n)`
• `cache` could become a large array and wont ever get garbage collected (unless you destroy `fib`, `fib = null`). Pretty negligible in my mind, as the setup cost is almost none and the size of the array will hardly have an affect on modern day machines.

Matt Sain

Ramblings of a developer, designer and child subscribe

This blog is a public GitHub repository. If you find an error I will not be surprised... but if you fork and edit the blog and send me a pull request you'd be pretty awesome in my book.