May 20, 2026•5 min read

From Recursion to Dynamic Programming: Demystifying Memoization and Tabulation

Many programmers dread the term Dynamic Programming (DP). It sounds mathematical, academic, and intimidating.

But at its heart, Dynamic Programming is simply an optimization technique. It’s the art of remembering things you have already calculated so you don’t have to calculate them again.

If you have ever solved a problem by writing down intermediate steps on a scratchpad instead of starting from scratch every time, you have done Dynamic Programming.

Here at Curious Folk, we love simple explanations for complex ideas. In this article, we’ll demystify DP. We’ll look at the basics of Recursion, see how it falls short when dealing with repeating calculations, and explore the two strategies of Dynamic Programming: Memoization (Top-Down) and Tabulation (Bottom-Up).

1. Recursion: The Loop of Self-Similarity

Before we can understand Dynamic Programming, we must understand Recursion. Recursion is when a function calls itself to solve a smaller instance of the same problem.

Every recursive function needs two things:

A Base Case: The condition where the function stops calling itself and returns a direct value. Without this, you get an infinite loop that crashes the program (a Stack Overflow).
A Recursive Step: The logic where the function calls itself with a slightly smaller input, moving closer to the base case.

Let’s look at the classic mathematical example: The Fibonacci Sequence. In this sequence, each number is the sum of the two preceding ones: 0, 1, 1, 2, 3, 5, 8, 13, 21...

Mathematically: F(n) = F(n-1) + F(n-2) with base cases F(0) = 0 and F(1) = 1.

Here is how we write it recursively in JavaScript:

function fib(n) {
    if (n === 0) return 0; // Base case 1
    if (n === 1) return 1; // Base case 2
    return fib(n - 1) + fib(n - 2); // Recursive step
}

The Problem: The Exploding Call Tree

While the code above is simple and elegant, it is incredibly inefficient for larger inputs.

Let’s visualize the call tree when we try to calculate fib(5):

                          fib(5)
                       /          \
                 fib(4)            fib(3)
                /      \          /      \
            fib(3)    fib(2)    fib(2)   fib(1)
           /      \    /    \    /    \
       fib(2)   fib(1) fib(1) fib(0) fib(1) fib(0)
       /    \
   fib(1)  fib(0)

Look closely at the tree.

We calculate fib(3) two separate times.
We calculate fib(2) three separate times.
We calculate fib(1) five separate times.

As n grows, the number of redundant calculations grows exponentially. The time complexity of this naive recursion is O(2ⁿ). To put that in perspective:

Calculating fib(10) takes ~1,000 steps.
Calculating fib(40) takes ~1,000,000,000,000 (one trillion) steps! Your browser or runtime will freeze.

This flaw represents the first prerequisite for Dynamic Programming: Overlapping Subproblems (solving the exact same sub-problems repeatedly).

2. Top-Down Dynamic Programming: Memoization

How do we solve this? We use a notebook (or a cache map) to remember the answers!

This is Memoization (not a typo, there’s no “r”). It is a Top-Down approach. We start at the target problem (e.g., fib(5)), and as we work our way down, we save the results of each subproblem in a cache. If we see the subproblem again, we skip the recursion and read from the cache.

                          fib(5)
                       /          \
                 fib(4)          [fib(3) - Read from Cache!]
                /      \
            fib(3)    [fib(2) - Read from Cache!]
           /      \
       fib(2)   [fib(1)]
       /    \
   [fib(1)] [fib(0)]

By reading from the cache, we cut off entire branches of the recursion tree.

Memoized Code in JavaScript:

function fibMemo(n, memo = {}) {
    // Check if we've already solved this
    if (n in memo) return memo[n];
    
    // Base cases
    if (n === 0) return 0;
    if (n === 1) return 1;
    
    // Save the result to our memo/cache map
    memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
    return memo[n];
}

Memoized Code in Python:

Python makes memoization incredibly easy with the built-in @lru_cache decorator:

from functools import lru_cache

@lru_cache(maxsize=None)
def fib_memo(n):
    if n < 2:
        return n
    return fib_memo(n-1) + fib_memo(n-2)

With memoization, the time complexity drops from O(2ⁿ) to O(n) (Linear Time). Calculating fib(40) now takes just 40 operations and completes in less than a millisecond!

3. Bottom-Up Dynamic Programming: Tabulation

While memoization is great, it still uses recursion, which means your computer has to allocate stack frames on the call stack (which takes up O(n) auxiliary space). If n is too large (like n = 10000), you could crash with a “Maximum call stack size exceeded” error.

To avoid recursion entirely, we use the Bottom-Up approach: Tabulation.

Instead of starting at n and breaking it down, we start at the base cases (fib(0) and fib(1)) and fill a table (usually an array) iteratively from the bottom up.

The Array Filling Visualization:

  Index:   0    1    2    3    4    5
  Array: [ 0 | 1 | ? | ? | ? | ? ]  --> Base cases initialized
  Array: [ 0 | 1 | 1 | ? | ? | ? ]  --> 0 + 1 = 1
  Array: [ 0 | 1 | 1 | 2 | ? | ? ]  --> 1 + 1 = 2
  Array: [ 0 | 1 | 1 | 2 | 3 | ? ]  --> 1 + 2 = 3
  Array: [ 0 | 1 | 1 | 2 | 3 | 5 ]  --> 2 + 3 = 5 (Done!)

Tabulated Code in JavaScript:

function fibTab(n) {
    if (n <= 1) return n;
    
    // Initialize our table
    const table = new Array(n + 1).fill(0);
    table[1] = 1;
    
    // Fill the table iteratively
    for (let i = 2; i <= n; i++) {
        table[i] = table[i - 1] + table[i - 2];
    }
    
    return table[n];
}

Space Optimization:

Notice that to calculate the next number in Fibonacci, we only ever need the last two numbers. We don’t actually need to store the entire table in memory! We can optimize our space complexity to O(1):

function fibSpaceOptimized(n) {
    if (n <= 1) return n;
    
    let prev2 = 0; // F(i-2)
    let prev1 = 1; // F(i-1)
    let current = 0;
    
    for (let i = 2; i <= n; i++) {
        current = prev1 + prev2;
        prev2 = prev1;
        prev1 = current;
    }
    
    return current;
}

Cheat Sheet: Memoization vs. Tabulation

Here is a quick reference table comparing the two DP strategies:

Feature	Memoization (Top-Down)	Tabulation (Bottom-Up)
Approach	Starts at target, breaks down recursively, caches answers.	Starts at base case, builds up iteratively, fills a table.
Mechanics	Recursion + Cache map	Loop + Array
Stack Space	Uses Call Stack space (O(n)). Risk of stack overflow.	No call stack overhead. Uses memory table space.
Ease of Code	Often easier to write directly from a recursive formula.	Can be harder to structure and plan the loop bounds.
Performance	Slightly slower due to function calls and recursion overhead.	Faster because it’s a simple loop.

When Can You Use Dynamic Programming?

You can apply DP to a problem if it satisfies two core characteristics:

Overlapping Subproblems: The problem can be broken down into subproblems, and you solve the same subproblems repeatedly (e.g., calculating fib(2) multiple times).
Optimal Substructure: The optimal solution to the parent problem can be constructed from the optimal solutions of its subproblems. (e.g., to get fib(5), we combine the optimal answers of fib(4) and fib(3)).

Dynamic Programming is the secret key to solving classic algorithmic problems like the Knapsack Problem, Longest Common Subsequence, Edit Distance, and Dijkstra’s Shortest Path.

So the next time you see a problem with repetitive branching math, grab a cache array, fill it from the bottom up, and enjoy the O(n) performance! 🚀