Memoized Fibonacci function in 1 line of JavaScript

Published on Aug 5, 2021 in JavaScript and TypeScript

Using recursion, logical OR assignment operator (||=), BigInts and more!

What's Fibonacci?

In mathematics, the Fibonacci numbers, commonly denoted F_n, form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is,

F₀ = 0,
F₁ = 1,

and

F_n = F_n-1 + F_n-2

for n > 1.

The sequence starts:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …

What's memoization?

From Memoization on Wikipedia:

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.

Step 1: Recursive function without memoization

const fib = (n) => {
  if (n < 2) return n
  return fib(n - 1) + fib(n - 2)
}

Negative inputs are returned as-is, and non-number inputs may break the function. This is addressed in the 3rd bonus section; for now, let's just live with it.

Usage:

fib(0) //=> 0
fib(1) //=> 1
fib(2) //=> 1
fib(3) //=> 2
fib(4) //=> 3
fib(5) //=> 5
fib(6) //=> 8
fib(7) //=> 13
fib(8) //=> 21

fib(20) //=> 6_765

console.time()
fib(38) //=> 39_088_169
console.timeEnd() //=> ~450ms on my machine 😬

Demonstration of the lack of memoization:

 
 const log = {}
const fib = (n) => {
  log[n] = log[n] + 1 || 1
  if (n < 2) return n
  return fib(n - 1) + fib(n - 2)
}

fib(10) //=> 55

Object.entries(log)
  .reverse()
  .forEach(([n, times]) => {
    console.log(`fib(${n}) was called ${times} times`)
  })
//=> fib(10) was called 1 times
//=> fib(9) was called 1 times
//=> fib(8) was called 2 times
//=> fib(7) was called 3 times
//=> fib(6) was called 5 times
//=> fib(5) was called 8 times
//=> fib(4) was called 13 times
//=> fib(3) was called 21 times
//=> fib(2) was called 34 times
//=> fib(1) was called 55 times
//=> fib(0) was called 34 times

It's funny that those numbers – how many times fib(n) was called – follow the Fibonacci sequence! (Excluding the last one; looks like the numbers could continue decrementing at the same rate? Interesting.)

No wonder calculating fib(38) takes half a second. fib(1) gets called 39,088,169 times!

Step 2: Memoization

Diff:

+const cache = {}
 const fib = (n) => {
   if (n < 2) return n
+  cache[n] = cache[n] || fib(n - 1) + fib(n - 2)
   return cache[n]
 }

Result:

const cache = {}
const fib = (n) => {
  if (n < 2) return n
  cache[n] = cache[n] || fib(n - 1) + fib(n - 2)
  return cache[n]
}

cache is a "global" object for now. We'll change it later.

Performance is much better now:

console.time()
fib(38) //=> 39_088_169
console.timeEnd() //=> Less than 1ms on my machine 😎

Demonstration of the presence of memoization:


 
 const cache = {}
const log = {}
const fib = (n) => {
  log[n] = log[n] + 1 || 1
  if (n < 2) return n
  cache[n] = cache[n] || fib(n - 1) + fib(n - 2)
  return fib(n - 1) + fib(n - 2)
}

fib(20)

Object.entries(log)
  .reverse()
  .forEach(([n, times]) => {
    console.log(`fib(${n}) was called ${times} times`)
  })
//=> fib(10) was called 1 times
//=> fib(9) was called 1 times
//=> fib(8) was called 2 times
//=> fib(7) was called 2 times
//=> fib(6) was called 2 times
//=> fib(5) was called 2 times
//=> fib(4) was called 2 times
//=> fib(3) was called 2 times
//=> fib(2) was called 2 times
//=> fib(1) was called 2 times
//=> fib(0) was called 1 times

Step 3: Golf ⛳

Code golfing = striving for the shortest possible source code.

Step 3.1: Logical OR assignment operator (`||=`)

The logical OR assignment operator was introduced in the ECMAScript 2021 spec^[1] and is perfect for our case.

Diff:

 const cache = {}
 const fib = (n) => {
   if (n < 2) return n
-  cache[n] = cache[n] || fib(n - 1) + fib(n - 2)
+  cache[n] ||= fib(n - 1) + fib(n - 2)
   return cache[n]
 }

Result:

const cache = {}
const fib = (n) => {
  if (n < 2) return n
  cache[n] ||= fib(n - 1) + fib(n - 2)
  return cache[n]
}

Step 3.2: Return value of the assignment operator

In JavaScript, assignments have return values:

Like most expressions, assignments like x = y have a return value.

[...]

That means that (x = y) returns y, (x += y) returns the resulting sum x + y, (x **= y) returns the resulting power x ** y, and so on.

In the case of logical assignments, (x &&= y), (x ||= y), and (x ??= y), the return value is that of the logical operation without the assignment, so x && y, x || y, and x ?? y, respectively.

Diff:

 const cache = {}
 const fib = (n) => {
   if (n < 2) return n
-  cache[n] ||= fib(n - 1) + fib(n - 2)
-  return cache[n]
+  return (cache[n] ||= fib(n - 1) + fib(n - 2))
 }

Result:

const cache = {}
const fib = (n) => {
  if (n < 2) return n
  return (cache[n] ||= fib(n - 1) + fib(n - 2))
}

The outermost parentheses in the return statement are added by Prettier, but they are optional.

Step 3.3: Ternary operator

Diff:

 const cache = {}
-const fib = (n) => {
-  if (n < 2) return n
-  return (cache[n] ||= fib(n - 1) + fib(n - 2))
-}
+const fib = (n) => (n < 2 ? n : (cache[n] ||= fib(n - 1) + fib(n - 2)))

Result:

const cache = {}
const fib = (n) => (n < 2 ? n : (cache[n] ||= fib(n - 1) + fib(n - 2)))

Step 3.4: Pass cache as a parameter

Diff:

-const cache = {}
-const fib = (n) => (n < 2 ? n : (cache[n] ||= fib(n - 1) + fib(n - 2)))
+const fib = (n, _cache = {}) =>
+  n < 2 ? n : (_cache[n] ||= fib(n - 1, _cache) + fib(n - 2, _cache))

Result:

const fib = (n, _cache = {}) =>
  n < 2 ? n : (_cache[n] ||= fib(n - 1, _cache) + fib(n - 2, _cache))

Yay, we got rid of the "global" cache object.

The downside of passing cache as a parameter is that the cache is discarded afterwards. This reduces performance if fib() is called many times:

// Before (global cache):
console.time()
Array.from({ length: 50_000 }, () => fib(1_000))
console.timeEnd()
//=> ~5ms

// After (cache as parameter):
console.time()
Array.from({ length: 50_000 }, () => fib(1_000))
console.timeEnd()
//=> ~2,000ms

Okay, that's silly. Who would call fib(1_000) 50,000 times? 😅 But the point remains that the performance is worse.

The new function parameter is prefixed with an underscore to denote that it's a "private" parameter not meant to be used by the user of the function.

Though it can be used, and doing so will fix the performance problem:

console.time()
const cache = {}
Array.from({ length: 50_000 }, () => fib(1_000, cache))
console.timeEnd()
//=> ~5ms

I think an optional cache parameter is the best of both worlds: you can just call fib(n) and not have to care about creating a cache object, but you can also easily create a persistent cache if you need to.

Step 3.5: Obfuscate the code to fit on a single line 😅

We are almost there! The code from the previous step could already be placed on a single line, but I want to let Prettier format my code.

Renaming _cache to c almost makes the code fit on a single line:

const fib = (n, c = {}) =>
  n < 2 ? n : (c[n] ||= fib(n - 1, c) + fib(n - 2, c))

It's only 1 character too long!

We can further reduce the code's length by using the decrement operator instead of n - 1 and n - 2. Note that we have to use it in prefix position:

const fib = (n, c = {}) => (n < 2 ? n : (c[n] ||= fib(--n, c) + fib(--n, c)))

Now the code fits on a single line! 💪

We could golf more by changing const to let, renaming fib to f, and removing unnecessary spaces and parentheses:

let f=(n,c={})=>n<2?n:c[n]||=f(--n,c)+f(--n,c)

But that would be silly.

In fact, this whole step 3.5 is kind of silly. I would prefer the code from step 3.4. It spans on two lines, but at least it's readable.

Bonuses

These are bonuses, so we don't necessarily have to aim for the line length of one. 😜

Bonus 1: Arbitrarily large integers with BigInts

The Number.MAX_SAFE_INTEGER constant represents the maximum safe integer in JavaScript (2^53 - 1).

Safe in this context refers to the ability to represent integers exactly and to correctly compare them. For example, Number.MAX_SAFE_INTEGER + 1 === Number.MAX_SAFE_INTEGER + 2 will evaluate to true, which is mathematically incorrect.

2^53 - 1 sounds large, but it's exceeded quite quickly when calculating Fibonacci numbers:

fib(78)                 //=>  8_944_394_323_791_464
Number.MAX_SAFE_INTEGER //=>  9_007_199_254_740_991
fib(79)                 //=> 14_472_334_024_676_220 (incorrect!)

A quick Duck search shows that our result for fib(79) is incorrect; the correct value is our result plus one.

We should instead use BigInt values, introduced in the ECMAScript 2020 spec^[2]. BigInts can be used for arbitrarily large integers.

BigInts can be created in two ways:

by appending n to the end of an integer literal (100n)
by calling the BigInt() constructor without the new operator (BigInt(100), BigInt(100n) or BigInt('100')).

BigInts can't be mixed with regular numbers, so we have to change n - 1 to n - 1n and n - 2 to n - 2n. However, BigInts can be compared with regular numbers, so we don't have to change n < 2.

After introducing BigInts to the code from step 3.4, the code looks like this:

const fib = (n, _cache = {}) =>
  n < 2 ? n : (_cache[n] ||= fib(n - 1n, _cache) + fib(n - 2n, _cache))

fib(78n)                //=>  8_472_334_024_676_464n
Number.MAX_SAFE_INTEGER //=>  9_472_334_024_676_991
fib(79n)                //=> 14_472_334_024_676_221n (correct!)

fib(1_000n) //=> 43_466_557_686_937_472_334_024_676_675_472_334_024_676_660_472_334_024_676_481_472_334_024_676_417_472_334_024_676_879_472_334_024_676_295_472_334_024_676_634_472_334_024_676_239_472_334_024_676_642_472_334_024_676_187_472_334_024_676_928_472_334_024_676_137_472_334_024_676_875n 😅

Performance seems about the same. The above code runs in less than 2ms on my machine.

Note that our function has to be called with a BigInt. Calling it with a regular number will throw a TypeError:

fib(100)
//=> Chrome: "Uncaught TypeError: Cannot mix BigInt and other types, use explicit conversions"
//=> Firefox: "Uncaught TypeError: can't convert BigInt to number"

We'll change this in the 3rd bonus section.

Bonus 2: Avoiding stack overflows

We can now support arbitrarily large integers, except we can't because too large inputs cause stack overflow errors:

fib(10_000n)
//=> Chrome: "Uncaught RangeError: Maximum call stack size exceeded"
//=> Firefox: No problem on my machine!

fib(100_000n)
//=> Chrome: "Uncaught RangeError: Maximum call stack size exceeded"
//=> Firefox: "Uncaught InternalError: too much recursion"

Here's what we can do:

Make our function async.
Periodically pause our function with await, Promises and timeouts, so that the call stack can be periodically emptied.

Like so; I put a log statement for demonstration (notice also the non-highlighted async and await keywords):



    const fib = async (n, _cache = {}) => {
  if (n < 2) return n
  if (n % 1_000n === 0n) {
    console.log('Pausing at n =', n)
    await new Promise((resolve) => setTimeout(resolve))
  }
  _cache[n] ||= (await fib(n - 1n, _cache)) + (await fib(n - 2n, _cache))
  return _cache[n]
}

Using await inside the second if statement pauses the function until the new Promise is resolved, i.e. until resolve() is called.

Using setTimeout() puts the calling of resolve() to the end of the browser's task queue. Tasks are processed only when the call stack is empty. In other words, our function resumes only after the call stack has been emptied, so now we won't get stack overflow errors.

If you are not following, please read Jake Archibald's great article Tasks, microtasks, queues and schedules.

Usage:

console.time()

await fib(100n)
//=> 354_224_848_179_261_915_075n

console.timeEnd()
//=> ~10ms

console.time()

await fib(5_000n)
//=> Pausing at n = 5000n
//=> Pausing at n = 4000n
//=> Pausing at n = 3000n
//=> Pausing at n = 2000n
//=> Pausing at n = 1000n
//=> Pausing at n = 1000n
//=> Pausing at n = 2000n
//=> Pausing at n = 3000n
//=> Pausing at n = 4000n
//=> (returns a big-ass number)

console.timeEnd()
//=> ~1,200ms

Two problems though:

The function is now very slow.
The page becomes janky with large inputs (e.g. fib(5_000n)).

Jankiness could be reduced by pausing more often (e.g. if (n % 100n === 0n)), but it would make the function even slower (more pausing means more waiting).

At this point it would anyway be better to use a non-recursive function (see the 4th bonus section). It would be much faster and would have no stack overflow problems. Move it to a Web Worker and the page wouldn't become janky even with enormous inputs.

Sidetrack: `await new Promise(setTimeout)`

If we were code golfing, we could shorten our pausing code like this:

// Before
await new Promise((resolve) => setTimeout(resolve))

// After
await new Promise(setTimeout)

The shortened code works because the Promise constructor takes one function parameter (executor), which in turn takes two function parameters (resolutionFunc and rejectionFunc). So, new Promise(setTimeout) expands to:

new Promise((resolutionFunc, rejectionFunc) =>
  setTimeout(resolutionFunc, rejectionFunc)
)

setTimeout's second parameter (delay in milliseconds) gets coerced into a number, so basically Number(rejectionFunc)^[3], which is NaN, which is the same as omitting the second parameter.

Of course, the shorter code shouldn't be generally used because it's too cryptic.

Bonus 3: Input validation and TypeScript types

As mentioned in step 1, negative inputs are returned as-is, and non-number inputs may break the function. Let's add input validation:


 







  const fib = async (n, _cache = {}) => {
  if (n < 0) throw new Error('n must be non-negative')
  if (n < 2) return n
  if (n % 1_000n === 0n) {
    await new Promise((resolve) => setTimeout(resolve))
  }
  _cache[n] ||= (await fib(n - 1n, _cache)) + (await fib(n - 2n, _cache))
  return _cache[n]
}

await fib(-1) //=>  Error: n must be non-negative
await fib(-1n) //=> Error: n must be non-negative

It would be nice to accept regular numbers as well. It would be no "validation," but let's add that:




 






  const fib = async (n, _cache = {}) => {
  if (n < 0) throw new Error('n must be non-negative')
  if (n < 2) return BigInt(n)
  if (typeof n !== 'bigint') n = BigInt(n)
  if (n % 1_000n === 0n) {
    await new Promise((resolve) => setTimeout(resolve))
  }
  _cache[n] ||= (await fib(n - 1n, _cache)) + (await fib(n - 2n, _cache))
  return _cache[n]
}

await fib(10) //=>  55n
await fib(10n) //=> 55n

Now that our function is ready, let's add TypeScript types:


   





 
 const fib = async (
  n: number | bigint,
  _cache: { [key: string]: bigint } = {}
): Promise<bigint> => {
  if (n < 0) throw new Error('n must be non-negative')
  if (n < 2) return BigInt(n)
  if (typeof n !== 'bigint') n = BigInt(n)
  if (n % 1_000n === 0n) {
    await new Promise((resolve) => setTimeout(resolve))
  }
  _cache[n.toString()] ||=
    (await fib(n - 1n, _cache)) + (await fib(n - 2n, _cache))
  return _cache[n.toString()]
}

Eh, quite ugly and way more than 1 line (14). 😅

Note that instead of _cache[n] I had to explicitly use _cache[n.toString()]. A reason for this can be found in the TypeScript Index Signature section of the TypeScript Deep Dive book.

Bonus 4: Non-recursive non-memoized function

I wanted to see how much faster a non-recursive function would be:

const fib = (n) => {
  let a = 0n
  let b = 1n
  let c = 0n
  while (n--) [a, b, c] = [b, c, b + c]
  return c
}

fib(10) //=> 55n (correct)

console.time()
fib(5_000)
console.timeEnd() //=> ~3ms

console.time()
fib(100_000)
console.timeEnd() //=> ~90ms

Much faster, so this whole blog post was a bit silly in the end. 🙈

Footnotes

See list of finished ECMAScript proposals on GitHub. ↩
See previous footnote. ↩
See Dr. Axel Rauschmayer's article Type coercion in JavaScript for details. ↩

Memoized Fibonacci function in 1 line of JavaScript

Table of contents

Sidetrack: await new Promise(setTimeout)

Footnotes

Sidetrack: `await new Promise(setTimeout)`