# Memoized Fibonacci function in 1 line of JavaScript

Published on in JavaScript and TypeScript

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

## What's Fibonacci?

In mathematics, the Fibonacci numbers, commonly denoted Fn, 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,

F0 = 0,
F1 = 1,

and

Fn = Fn-1 + Fn-2

for n > 1.

The sequence starts:

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

## What's 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.

## 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 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. 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)`, 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

1. See previous footnote.

2. See Dr. Axel Rauschmayer's article Type coercion in JavaScript for details.