// Tutorial //

Understanding Recursion & Memoization via JavaScript

Published on January 26, 2020
Default avatar
By Joshua Hall
Developer and author at DigitalOcean.
Understanding Recursion & Memoization via JavaScript

While we believe that this content benefits our community, we have not yet thoroughly reviewed it. If you have any suggestions for improvements, please let us know by clicking the “report an issue“ button at the bottom of the tutorial.

In this article, you’re going to learn how to use recursive programming, what it is, and how to optimize it for use in algorithms. We’ll be using JavaScript as our programming language of choice to understand the concept of recursion.


I’ll be using Big O Notation to compare optimization strategies, which you can brush up on here.

What is Recursion?

Recursion is any time a function calls itself inside itself, potentially creating a infinite loop. If you’ve ever worked with canvas animations then you’ve already used recursion since we use an animate function that updates our animation before rerunning itself.

In the below example, we’re passing in a number, doubling it, then passing that value to itself again. In theory, this would continue forever but because computers are limited we generally can’t have infinite recursion. You’ll get an error like too much recursion or Maximum call stack size exceeded if you don’t include some exit condition to stop the function, in the following case as soon as it’s over 100:

const double = num => {
  num = num + num;

  if (num > 100) return 'Exit'; // Try removing this
  return double(num);


You’re probably thinking, “that’s cool and all, but can’t I just use a loop for anything recursion can do?”. Well yes, but actually no. Recursion comes in handy when dealing with various searching and sorting algorithms or traversing data structures that are more complicated than simple lists. When done correctly, you can also get much better performance, like O(log n) while all loops are O(n).


You don’t have to play around with recursion for long to realize that it’s pretty easy to overwhelm your computer. This is because most recursive functions are O(n^2) or even O(n!). Since JavaScript runs on call stacks every time a new recursive layer is added, a lot of memory and processing power must be used to manage it all, despite most of it being redundant.

Let’s try something simple like generating a fibonacci sequence. A fibonacci sequence is where every digit is the sum of the two items before it, 0, 1, 1, 2, 3, 5, 8, 12…

const fibonacci = num => {
  if (num < 2) return num;

  return fibonacci(num - 1) + fibonacci(num - 2);

for (let i = 0; i < 1000; i++) console.log(fibonacci(i)); // 3 minutes before page crashed...

That’s just horrendous. Using up resources for 1,000 layers of the same information is too much even for my, relatively, decent computer.

Instead, we can work around this by adding a storage variable, or a “memo”, that will contain our values as the stack progresses. Every time our function runs, its value will be added to its corresponding index in the memo and the next layer will refer to that to calculate our result.

const fibonacci = (num, memo) => {
  memo = memo || {};

  if (memo[num]) return memo[num];
  if (num < 2) return num;

  return memo[num] = fibonacci(num - 1, memo) + fibonacci(num - 2, memo);

for (let i = 0; i < 1000; i++) console.log(fibonacci(i)); // 143 Milliseconds


Let’s try applying this to another recursive function. This takes a number and outputs its factorial, so 3! should return 6 because 3x2x1=6.

const factorial = n => {
  let num = n;

  if (n === 0) return 1;
  for (let i = 0; i < n; i++) {
    num = n * factorial(n - 1);

  return num;

console.log(factorial(3)); // 7 Milliseconds
console.log(factorial(6)); // 8 Milliseconds
console.log(factorial(9)); // 15 Milliseconds
console.log(factorial(12)); // 11,588 Milliseconds

For me, anything above 12 crashes the page because this function has the complexity of O(n!) as each layer in the stack has to handle the complexity of the one before it.

Instead, let’s try memoizing it and see the difference.

const factorial = (n, memo) => {
  memo = memo || {};

  if (memo[n]) return memo[n];
  if (n === 0) return 1;
  for (let i = 0; i < n; i++) {
    memo[n] = n * factorial(n - 1, memo);

  return memo[n];

console.log(factorial(12));  // 4 milliseconds
console.log(factorial(120));  // 12 milliseconds
console.log(factorial(1200)); // 24 milliseconds
console.log(factorial(12000));  // 1408 milliseconds

I don’t know about you, but I think that’s an incredible improvement, it can now handle 10,000 times the computations in 1/8th the time.

Closing Thoughts

Recursion is one of those things you need to get very comfortable with because it will return repeatedly, or haunt you, throughout your programming career. It will be essential for learning to traverse trees and lists and sort various data sets in the future.

If you’ve enjoyed this tutorial and our broader community, consider checking out our DigitalOcean products which can also help you achieve your development goals.

Learn more here

About the authors
Default avatar
Developer and author at DigitalOcean.

Still looking for an answer?

Was this helpful?
Leave a comment

This textbox defaults to using Markdown to format your answer.

You can type !ref in this text area to quickly search our full set of tutorials, documentation & marketplace offerings and insert the link!