# Fast and fabulous Fibonacci functions

11 min read

The Fibonacci sequence is a classic in computer science, often used to benchmark raw computing power (when written recursively) or to demonstrate the difference between iterative and recursive approaches. It also serves as one of the best examples of the power of memoization when written in its recursive form. Even for a single calculation, a Fibonacci function will call itself with the same parameters many times when written naively.

Simply put, `fib(n) = fib(n - 1) + fib(n - 2)`

, with `fib(0) = 0`

and `fib(1) = 1`

. The sequence is infinite and only defined for `n > 0`

.

## Recursive

Read section RecursiveThe simplest recursive solution hardcodes the `n = 0`

and `n = 1`

conditions and simply calls itself exactly as in the mathematical notation. As this is a recursive function, it must be defined with `function [name]`

.

```
function fib(n) {
return n < 2 ? n : fib(n - 1) + fib(n - 2);
}
Array.from({ length: 29 }, (_, i) => fib(i + 1));
```

### Memoized recursive

Read section Memoized recursiveThis memoized approach is orders of magnitude faster and not much harder to write with the logical nullish assignment operator. By initializing the value for `fib(0)`

and `fib(1)`

, it becomes a straightforward assign-or-calculate operation.

```
const fibN = { 0: 0, 1: 1 };
function fib(n) {
return (fibN[n] ??= fib(n - 1) + fib(n - 2));
}
```

### The impact of memoization

Read section The impact of memoizationA recursive version without memoization is outright irresponsible and should only be used for benchmarking purposes. The example below highlights the difference in function calls, each of which has a high cost.

```
let naiveCalls = 0;
function fibNaive(n) {
naiveCalls += 1;
return n < 2 ? n : fibNaive(n - 1) + fibNaive(n - 2);
}
let memoCalls = 0;
const fibN = { 0: 0, 1: 1 };
function fibMemo(n) {
memoCalls += 1;
return (fibN[n] ??= fibMemo(n - 1) + fibMemo(n - 2));
}
fibNaive(25);
fibMemo(25);
[naiveCalls, memoCalls];
```

JavaScript engines are full of optimizations which are especially targeted for hot code like this. Many of these optimizations no longer function when `fibNaive`

is instrumented with a global add of `naiveCalls`

. Try to run it yourself with a higher value; bet too high, and you won’t get to see the answer.

## Iterative

Read section IterativeThis iterative approach simply uses an array with `fib(0)`

and `fib(1)`

pre-defined and adds additional numbers in the sequence to the end. .at() is used to concisely get the last two elements in the array. `fib(0)`

is sliced off in this example to keep parity with the other solutions.

```
const nums = [0, 1];
for (let i = 1; i < 29; i += 1) nums.push(nums.at(-1) + nums.at(-2));
nums.slice(1);
```

## Golden ratio

Read section Golden ratioThe golden ratio (φ) is an irrational number (like π) approximately equal to `1.618033988749`

. It’s commonly seen in geometry, art, and even nature, like in the shells of snails. It turns out that as the Fibonacci sequence is expanded, the ratio between the current number and the previous number approximate the golden ratio:

```
const nums = [0, 1];
for (let i = 1; i < 15; i += 1) nums.push(nums.at(-1) + nums.at(-2));
nums.slice(2).map((cur, i) => cur / nums[i + 1]);
```

Even after only a dozen iterations, it gets remarkably close to φ and this approximation improves with every additional iteration.

This remarkable property holds even for Fibonacci-like sequences with different base terms.

```
const nums = [5, 7];
for (let i = 1; i < 15; i += 1) nums.push(nums.at(-1) + nums.at(-2));
[nums, nums.slice(2).map((cur, i) => cur / nums[i + 1])];
```

And perhaps even more spectacularly, even the number of function calls in the naive recursive version approximates the golden ratio:

```
fibNaive(25);
const naiveCalls25 = naiveCalls;
naiveCalls = 0;
fibNaive(26);
const naiveCalls26 = naiveCalls;
[naiveCalls26, naiveCalls25, naiveCalls26 / naiveCalls25];
```

### Binet’s formula

Read section Binet’s formulaBy following Binet’s formula, we can calculate `fib(n)`

in constant time. This looks nothing like the other approaches and is sure to raise some eyebrows before you get a chance to run the code.

```
const fib = (n) => Math.round(Math.pow((1 + Math.sqrt(5)) / 2, n) / Math.sqrt(5));
Array.from({ length: 29 }, (_, i) => fib(i + 1));
```

Calculating `sqrt(5)`

can also be done once outside the function. The exponentiation operator is a more concise way of calculating x to the power n.

```
const sqrt5 = Math.sqrt(5);
const fib = (n) => Math.round(((1 + sqrt5) / 2) ** n / sqrt5);
```

## Iterable

Read section Iterable### Generator functions

Read section Generator functionsES2015 introduced the now little used generator functions which have largely been superseded by async functions. Their main advantage remains the ability to generate infinite sequences which suits certain problems well.

```
function* fib() {
let previous = 0;
let current = 1;
for (;;) {
yield current;
const next = previous + current;
previous = current;
current = next;
}
}
const seq = fib();
Array.from({ length: 29 }, (_, i) => seq.next().value);
```

Of course, generator functions can still receive arguments, which can be leveraged to succinctly convert them to an array with `Array.from`

, which can convert any halting (i.e. returns `done: true`

at some point) iterable to an array. Generator functions return an iterable.

```
function* fib(n) {
let previous = 0;
let current = 1;
// If this function should also return fib(0), uncomment:
// yield previous;
do {
yield current;
const next = previous + current;
previous = current;
current = next;
} while (--n);
}
Array.from(fib(29));
```

Generator functions are just syntactic sugar for the iterable protocol, which can be implemented by any object using `Symbol.iterator`

. An iterable returns a single function `next`

which returns `{ value: any, done: boolean }`

. The previous example therefore does the exact same as the following.

```
function fib(n) {
return {
[Symbol.iterator]() {
let previous = 0;
let current = 1;
return {
next() {
const ret = { value: current, done: !n-- };
const next = previous + current;
previous = current;
current = next;
return ret;
},
};
},
};
}
Array.from(fib(29));
```

An infinitely generating fib function with a manual `Symbol.iterator`

definition would always return `{ value, done: false }`

.

## Finite precision

Read section Finite precisionNumbers in JavaScript are implemented as 64-bit floating point and have finite precision. Past `2^53 - 1`

(defined as `Number.MAX_SAFE_INTEGER`

), integers are no longer precise. In the Fibonacci sequence, this is `fib(79)`

onward.

```
const fibN = { 0: 0, 1: 1 };
function fib(n) {
return (fibN[n] ??= fib(n - 1) + fib(n - 2));
}
[fib(78), fib(79), fib(78) > Number.MAX_SAFE_INTEGER, fib(79) > Number.MAX_SAFE_INTEGER];
```

### BigInt to the rescue

Read section BigInt to the rescueBy using the infinite-precision BigInt , this problem can be avoided altogether. BigInts are much slower than numbers, but can contain any integer - the available memory’s the limit.

The `[number]n`

notation can be used to create bigints. Our `fib`

function only depends on the hardcoded values we use to seed the sequence (0 and 1). If these are both bigints, all other numbers calculated by our function will be as well.

```
const bigfibN = { 0: 0n, 1: 1n };
function bigfib(n) {
return (bigfibN[n] ??= bigfib(n - 1) + bigfib(n - 2));
}
[
[fib(78), fib(79), fib(100)],
[bigfib(78), bigfib(79), bigfib(100)],
[bigfib(78) - BigInt(fib(78)), bigfib(79) - BigInt(fib(79)), bigfib(100) - BigInt(fib(100))],
];
```

As expected, for `fib(78)`

which is within `Number.MAX_SAFE_INTEGER`

, there is no discrepancy. For `fib(79)`

, the precision error is only `1`

. For larger values, this discrepancy will continue to grow.

### Infinite generator with infinite precision

Read section Infinite generator with infinite precisionBigInts make for an especially good choice combined with infinite (non-halting) generators. As with the previous example, all that needs to be changed is the `0`

and `1`

terms.

```
function* fib() {
let previous = 0n;
let current = 1n;
for (;;) {
yield current;
const next = previous + current;
previous = current;
current = next;
}
}
const seq = fib();
Array.from({ length: 200 }, (_, i) => seq.next().value).slice(197, 200);
```