From Recursion to Memoization to Tabulation: Solve the Same Problem Three Ways

Recursion, memoization, and tabulation are one method at three levels of efficiency. Plain recursion recomputes the same small problems many times. Memoization stores each answer the first time, working from the top down.

Tabulation computes every answer once inside a loop, from the bottom up. All three share one recurrence, one set of base cases, and one final answer. Only the order of the work and its cost change.

This guide solves Climbing Stairs three ways in Python, then Coin Change in words, then compares the costs.

What recursion, memoization, and tabulation mean

Recursion is a function that calls itself on a smaller input. It stops when the input is small enough to answer directly.

Each smaller input is a subproblem, a smaller copy of the same question. The inputs answered directly are the base cases. The recurrence is the rule that builds one answer from smaller answers.

Memoization means storing each subproblem's answer the first time it is computed. A repeat call returns the stored answer instead of recomputing it. The store is a dictionary or an array, called the cache or the memo.

Tabulation means computing the subproblems in a loop, smallest first, and writing each answer into a table. The final answer is read from the table at the end.

Dynamic programming is the name for either memoization or tabulation. It applies when the same subproblems repeat many times, which is called overlapping subproblems. The basics of recursion itself are covered in what is recursion.

A short comparison of the three terms is in the difference between recursion, memoization, and dynamic programming.

The running example: Climbing Stairs

Climbing Stairs asks how many ways there are to reach step n. Each move climbs one step or two. For n equal to 3 there are three ways: 1+1+1, 1+2, and 2+1.

The state is one number, the step to reach. The recurrence is ways(n) = ways(n - 1) + ways(n - 2), the sum of the counts for the two steps below. The base cases are steps 0 and 1, with one way each.

The recurrence is correct because the last move came from step n minus 1 or from step n minus 2.

Version 1: plain recursion

This block writes the recurrence and the base cases directly as Python.

def climb(n):
    if n <= 1:
        return 1
    return climb(n - 1) + climb(n - 2)

It returns 8 for n equal to 5. It is the clearest version, and the slowest.

The call tree shows the repeated work. A call tree is a drawing of every call, with each call's children below it. Step 5 calls steps 4 and 3, and step 4 calls steps 3 and 2.

So step 3 is computed twice and step 2 three times.

For n equal to 5 the function runs 15 times. For n equal to 30 it runs about 2.7 million times. For n equal to 50, about 40 billion times, which takes tens of minutes in Python.

Every extra step multiplies the calls by about 1.6. That growth is exponential time: the work multiplies by a constant for each extra step.

Version 2: memoization, top down

This block keeps the recursion and adds a dictionary keyed by step number.

def climb(n, memo=None):
    if memo is None:
        memo = {}
    if n <= 1:
        return 1
    if n not in memo:
        memo[n] = climb(n - 1, memo) + climb(n - 2, memo)
    return memo[n]

Each step is now computed once and read from the dictionary after that. The time is linear, which means proportional to n. The dictionary uses linear space too.

The words "top down" describe the direction. The first call asks for step n, the largest subproblem. The recursion solves the smaller ones first, then stores answers as the calls return.

Python's standard library can add the cache with a decorator. A decorator is a line starting with @ that wraps the function below it.

from functools import cache

@cache
def climb(n):
    if n <= 1:
        return 1
    return climb(n - 1) + climb(n - 2)

The decorator stores each result under its arguments, so every argument must be hashable, like a number or a tuple.

Recursion depth is the risk. Python keeps one frame, a record of an unfinished call, for each call in progress. Those frames form the call stack, and the default limit is about 1,000.

The memoized climb still makes n nested calls, so n above the limit raises RecursionError. sys.setrecursionlimit raises the limit, but very deep recursion can still crash the interpreter.

Grokking the Art of Recursion teaches the recursive thinking that the other two versions depend on, through worked problems.

Version 3: tabulation, bottom up

This block replaces the recursion with a loop that fills an array from index 0 upward.

def climb(n):
    if n <= 1:
        return 1
    ways = [0] * (n + 1)
    ways[0], ways[1] = 1, 1
    for i in range(2, n + 1):
        ways[i] = ways[i - 1] + ways[i - 2]
    return ways[n]

The array holds the answer for every step from 0 to n. Each loop pass reads two earlier entries and writes one new one. Time and space are linear, and with no call stack there is no depth limit.

The words "bottom up" describe this direction. The smallest subproblems are written first and the largest one last.

Two variables replace the array. Each entry depends only on the two before it, so older entries can be discarded.

def climb(n):
    prev, cur = 1, 1
    for _ in range(2, n + 1):
        prev, cur = cur, prev + cur
    return cur

Time is still linear, and the space is constant, which means it does not grow with n.

The same three versions on Coin Change

Coin Change gives a list of coin values and a target amount. It asks for the fewest coins that make the amount, or minus 1 if none can. With coins 1, 2, and 5 and amount 11, the answer is 3: two 5s and a 1.

The state is again one number, the amount still to pay. The recurrence has a loop inside it.

For each coin no larger than the amount, solve for the amount minus the coin. Keep the smallest of those results, plus one. The base case is amount 0, which needs zero coins.

Plain recursion branches once per coin at every amount, so the time is exponential in the amount. With coins 1, 2, and 5 and amount 11, the function runs 928 times. Most of those calls repeat an amount that was already solved.

Memoization stores the best answer for each amount in a dictionary. Each amount is solved once, with one pass over the coins. So the time is the amount times the number of coins.

Depth is a real concern here. A 1-value coin and an amount in the thousands need more nested calls than Python's default limit allows.

Tabulation makes a table with one entry per amount, from 0 to the target. Entry 0 is zero. Every other entry starts at infinity, written float("inf") in Python, as a placeholder.

The loop then goes through the amounts from 1 upward. At each amount, it reads one earlier entry per coin and keeps the smallest plus one. If the final entry is still infinity, no combination works and the answer is minus 1.

For coins 1, 2, and 5, the finished table is:

Entry 5 is 1 because one coin pays it exactly. Entry 11 is 3 because entry 6 is 2 and one more 5-coin completes it.

The fill order is increasing amount, because each entry reads only smaller amounts. This is the Unbounded Knapsack pattern, one of six in dynamic programming patterns for coding interviews.

The five conversion steps

Define the state. The state is the smallest set of values that identifies one subproblem. For Climbing Stairs it is the step, and for Coin Change it is the amount.

Write the recurrence. Say in words how one state's answer comes from the answers of smaller states. If that takes more than one sentence, the state is probably missing a value.

Name the base cases. These are the states whose answers need no recurrence. A wrong base case changes every later answer, so check each one by hand.

Add the cache. Keep the recursive function and store each state's answer the first time it is computed. This turns plain recursion into memoization in two lines.

Decide the fill order. Find an order in which every state is written before another state reads it. That order becomes the loop of the tabulated version.

When each entry reads only a fixed number of earlier entries, keep that many variables instead of the table.

Which version to use in the interview

Start with recursion, because it shows the interviewer the structure of the solution. Say the state, the recurrence, and the base cases out loud while writing them.

Then add the cache. The exponential version becomes linear in two lines, and the change is easy to check. State the new time and space costs as you do it.

Mention tabulation, and write it if the interviewer asks or if the depth is a concern. A follow-up like "can you do this in constant space" is a request for the two-variable version.

Do not begin with the table version unless you know the problem well. A mistake in the fill order is harder to find in a timed interview than a missing cache. The questions asked most often are listed in common dynamic programming questions in tech interviews.

Cost comparison: time, space, and stack risk

The table compares the versions for a problem with n states, like Climbing Stairs. Costs use big-O notation, which describes how work grows with the input, explained in big-O algorithm complexity.

Common mistakes

A cache key that misses part of the state. If the state has two values and the key has only one, two different subproblems share one stored answer.

In Coin Change II, which counts combinations, the state is the coin index and the amount. The key must include both.

A table filled in the wrong order. If the loop reads an entry before writing it, it reads the placeholder. Trace one small input by hand to confirm the order.

A missing base case. In Coin Change, leaving entry 0 at infinity makes every other entry infinity. In recursion, a missing base case means the function never stops calling itself.

A mutable default argument as the cache. Writing def climb(n, memo={}) creates one dictionary when the function is defined, and every call shares it.

It returns stale answers when a later test changes another input, like the coin list. Use memo=None and create the dictionary inside the function, as in Version 2. With the decorator, call climb.cache_clear() between tests.

Climbing Stairs and Coin Change are two of the six dynamic programming patterns. Grokking Dynamic Programming teaches each pattern one variation at a time, with runnable solutions.

Frequently asked questions

Is memoization the same as dynamic programming? Memoization is one of the two ways to do dynamic programming. It is the top-down way, where a recursive function stores its answers. Tabulation is the bottom-up way, with a loop and a table.

Which is faster, memoization or tabulation? They usually have the same big-O time. Tabulation is faster in practice, because a loop pass costs less than a function call. Memoization is faster when only a few states are needed, because it skips the rest.

When is plain recursion without a cache the right choice? Plain recursion is right when subproblems do not repeat. Tree traversal, merge sort, and backtracking each visit every state once, so a cache saves nothing. Backtracking has its own guide in backtracking interview questions.

How do I avoid Python's recursion limit? Convert the solution to tabulation, which uses a loop and no call stack. If the recursion must stay, sys.setrecursionlimit raises the limit, but very deep recursion can still crash the interpreter.

Does the loop order matter in tabulation? Yes, every entry must be written before any other entry reads it. For minimum coins, amounts go from 1 upward. For counting combinations, the coin loop goes outside the amount loop, so each combination is counted once.

Related reading

• What is recursion?
• The difference between recursion, memoization, and dynamic programming
• Common dynamic programming questions in tech interviews
• Big-O algorithm complexity
• Dynamic programming patterns for coding interviews
• Backtracking interview questions