Introduction

Recursion, memoization, and dynamic programming are related, but they are not synonyms. Recursion is a control-flow technique, memoization is a caching strategy, and dynamic programming is a broader problem-solving method built around overlapping subproblems and optimal substructure.

They often appear together, which is why people blur them together. The clean way to separate them is to ask what each one contributes: recursion expresses the problem, memoization avoids repeating work, and dynamic programming organizes the computation so the repeated work disappears systematically.

Recursion

A recursive function solves a problem by calling itself on smaller inputs until it reaches a base case.

Classic Fibonacci recursion:

1def fib(n):
2    if n <= 1:
3        return n
4    return fib(n - 1) + fib(n - 2)
5
6print(fib(6))

This is recursion in its pure form. It is concise and mirrors the mathematical definition, but it repeats the same subproblems many times. For fib(6), the function recomputes fib(4), fib(3), and smaller values again and again.

So recursion by itself is about how the solution is expressed, not whether it is efficient.

Memoization

Memoization is the technique of caching function results so the same input is solved only once.

Here is Fibonacci with memoization:

1def fib(n, cache=None):
2    if cache is None:
3        cache = {}
4
5    if n in cache:
6        return cache[n]
7
8    if n <= 1:
9        cache[n] = n
10    else:
11        cache[n] = fib(n - 1, cache) + fib(n - 2, cache)
12
13    return cache[n]
14
15print(fib(6))

This still uses recursion, but now repeated subproblems are remembered. The complexity drops from exponential to linear for Fibonacci because each value is computed once.

Memoization is often called top-down dynamic programming because you start with the original problem and recursively demand smaller answers, caching as you go.

Dynamic Programming

Dynamic programming is the larger method. It applies when:

• the problem has overlapping subproblems
• the full problem can be built from optimal solutions to smaller problems

You can implement dynamic programming top-down with memoization, or bottom-up with tabulation.

Bottom-up Fibonacci:

1def fib(n):
2    if n <= 1:
3        return n
4
5    dp = [0, 1]
6    for i in range(2, n + 1):
7        dp.append(dp[i - 1] + dp[i - 2])
8
9    return dp[n]
10
11print(fib(6))

This version avoids recursion entirely. It fills a table from the smallest cases upward until it reaches the final answer.

That is why dynamic programming is not the same thing as recursion. Many dynamic programming solutions are iterative.

How They Relate

The relationship is:

• recursion is a way to define or compute a problem
• memoization is a way to cache recursive or repeated computations
• dynamic programming is the algorithm design approach that exploits repeated subproblems systematically

Memoization is often one implementation style of dynamic programming, but not the only one.

For example, depth-first search on a tree may be recursive without memoization. That is recursion, but not dynamic programming if there are no overlapping subproblems. On the other hand, shortest-path algorithms or knapsack solvers may use dynamic programming with loops and tables and no recursion at all.

When to Choose Which

Use plain recursion when the problem structure is recursive and the input sizes are small enough that repeated work is not a concern.

Add memoization when recursion is natural but repeated subproblems make the plain recursive version too slow.

Use bottom-up dynamic programming when you want predictable iteration order, better control over memory, or to avoid recursion depth limits.

In interviews and algorithm classes, moving from recursion to memoization to bottom-up dynamic programming is a common progression because it shows both understanding and optimization.

Common Pitfalls

• Calling every recursive solution "dynamic programming." Recursion alone is not enough.
• Thinking memoization and dynamic programming are unrelated. Memoization is often a top-down form of dynamic programming.
• Choosing recursion for very deep problems and hitting recursion depth or stack limits.
• Building a full DP table when only a few cached states are actually needed.

Summary

• Recursion is a technique where a function calls itself on smaller inputs.
• Memoization caches results so repeated recursive calls do not recompute the same state.
• Dynamic programming is the broader method for problems with overlapping subproblems.
• Memoization is often top-down dynamic programming; tabulation is bottom-up dynamic programming.
• A solution can be recursive without being dynamic programming, and dynamic programming can be iterative without recursion.