snippetjavascriptTip

Optimizing recursive functions in JavaScript

Submitted by: @import:30-seconds-of-code·Mar 2, 2026·

Viewed 0 times

javascriptoptimizingrecursivefunctions

Problem

Recursion is a programming technique where the final solution is computed by breaking down the problem into smaller instances of the same problem and computing the solution for each one. The most common implementation is a function that calls itself, reducing the problem every time until it reaches an instance of the problem whose solution is either trivial to compute or already known.
@Quick refresher
Let's look at a very well-known example, calculating the nth term of the Fibonacci sequence, implemented using recursion in JavaScript:
To understand recursion better, let's add a console.log() call before each return and figure out what exactly is happening:
As you can see, for each value of n, fibonacciNumber will be called twice, once with n - 1 and once with n - 2 and this will continue until it's called with either 1 or 0. While this is straightforward to write and understand, it is inefficient as it will have to calculate the same value more than once.

Solution

const fibonacciNumber = n =>
  n < 2 ? fibonacciNumber(n - 1) + fibonacciNumber(n - 2) : n;

Let's look at a very well-known example, calculating the nth term of the Fibonacci sequence, implemented using recursion in JavaScript:
To understand recursion better, let's add a console.log() call before each return and figure out what exactly is happening:
As you can see, for each value of n, fibonacciNumber will be called twice, once with n - 1 and once with n - 2 and this will continue until it's called with either 1 or 0. While this is straightforward to write and understand, it is inefficient as it will have to calculate the same value more than once.
The solution to this problem, and the first trick that you can use to speed up recursive functions, is to use memoization. We already published a great article on memoization a little while back, so be sure to check it out to learn more about the subject. Here's our fibonacciNumber function, using memoization:
As you can see in the example above, the value for each n is only computed once. While the Fibonacci sequence doesn't require any costly calculations, this could make a huge difference for a more computationally expensive problem. It will also be a lot more noticeable for higher values of n where the number of calculations will increase significantly.
The second and final trick stems from the very definition of recursive programming turned on its head. If we can solve a smaller instance of the problem and use it for the solution of a larger instance of the problem, it should be possible to work iteratively from the smaller problem to the larger one, instead of recursively. Here's this idea in practice for our fibonacciNumber function:

Code Snippets

const fibonacciNumber = n =>
  n < 2 ? fibonacciNumber(n - 1) + fibonacciNumber(n - 2) : n;

const fibonacciNumber = n => {
  console.log(`[CALLED] fibonacciNumber(${n})`);
  const r = n >= 2 ? fibonacciNumber(n - 1) + fibonacciNumber(n - 2) : n;
  console.log(`[RETURN] ${r} for n=${n}`);
  return r;
}

fibonacciNumber(4);
// [CALLED] fibonacciNumber(4)
// [CALLED] fibonacciNumber(3)
// [CALLED] fibonacciNumber(2)
// [CALLED] fibonacciNumber(1)
// [RETURN] 1 for n=1
// [CALLED] fibonacciNumber(0)
// [RETURN] 0 for n=0
// [RETURN] 1 for n=2
// [CALLED] fibonacciNumber(1)
// [RETURN] 1 for n=1
// [RETURN] 2 for n=3
// [CALLED] fibonacciNumber(2)
// [CALLED] fibonacciNumber(1)
// [RETURN] 1 for n=1
// [CALLED] fibonacciNumber(0)
// [RETURN] 0 for n=0
// [RETURN] 1 for n=2
// [RETURN] 3 for n=4

const fibonacciCache = new Map();

const fibonacciNumber = n => {
  console.log(`[CALL] fibonacciNumber(${n})`);
  const cacheKey = `${n}`;
  let r;
  if(fibonacciCache.has(cacheKey)) {
    r = fibonacciCache.get(cacheKey);
    console.log(`[MEMO] Cache hit for ${n}: ${r}`);
  }
  else {
    r = n >= 2 ? fibonacciNumber(n - 1) + fibonacciNumber(n - 2) : n;
    fibonacciCache.set(cacheKey, r);
    console.log(`[CALC] Computed and stored value for ${n}: ${r}`);
  }
  return r;
}

fibonacciNumber(4);
// [CALL] fibonacciNumber(4)
// [CALL] fibonacciNumber(3)
// [CALL] fibonacciNumber(2)
// [CALL] fibonacciNumber(1)
// [CALC] Computed and stored value for 1: 1
// [CALL] fibonacciNumber(0)
// [CALC] Computed and stored value for 0: 0
// [CALC] Computed and stored value for 2: 1
// [CALL] fibonacciNumber(1)
// [MEMO] Cache hit for 1: 1
// [CALC] Computed and stored value for 3: 2
// [CALL] fibonacciNumber(2)
// [MEMO] Cache hit for 2: 1
// [CALC] Computed and stored value for 4: 3

Context

From 30-seconds-of-code: recursion-performance-optimization

Revisions (0)

No revisions yet.