Fast and fabulous Fibonacci functions

June 10, 202211 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

The 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));

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

Memoized recursive

This 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));
}

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

The impact of memoization

A 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];

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

This 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);

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

The 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]);

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])];

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];

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

Binet’s formula

By 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));

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);

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

Iterable

Generator functions

ES2015 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);

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));

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));

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

Numbers 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];

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

By 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))],
];

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

BigInts 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);

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);

Table of Contents