Recursion & Dynamic Programming (DP)

Building Up From Smaller Pieces

Recursion is the programming equivalent of Russian nesting dolls: to solve a big problem, you solve a slightly smaller version of the same problem, and keep going until you hit a version so small it's trivially solved. Dynamic Programming (DP) is what you do when you notice you're opening the same doll over and over — you just remember what's inside.

The Recursion Foundation

Recursion is a method where a function calls itself. It needs two things:

1. Base Case: When to stop (e.g., if n == 0: return 1). Without this, you get infinite recursion and a stack overflow.
2. Recursive Step: The logic that reduces the problem toward the base case.

# Fibonacci — naive recursion
def fib(n):
    if n <= 1:          # base case
        return n
    return fib(n-1) + fib(n-2)   # recursive step

The problem: fib(5) calls fib(4) and fib(3). fib(4) calls fib(3) again. fib(3) is computed twice. For fib(40), the same sub-problems are computed billions of times. Time complexity: $O(2^N)$.

The DP Upgrade

Dynamic Programming is Recursion + Memoization (caching previously computed results). Two equivalent approaches:

Top-Down (Memoization): Write the recursive solution, then add a dictionary to store results. The call tree is the same, but each sub-problem is solved exactly once.

def fib_memo(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
    return memo[n]
# Time: O(N), Space: O(N)

Bottom-Up (Tabulation): Start from the base case and fill a table iteratively. No recursion stack, no risk of stack overflow for large n.

def fib_dp(n):
    if n <= 1:
        return n
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]
# Time: O(N), Space: O(N) — reducible to O(1) by keeping only last two values

1D vs. 2D DP:

• 1D: Problems where the answer at position i depends only on a fixed number of previous positions (e.g., Climbing Stairs, House Robber). State: dp[i].
• 2D: Problems involving two sequences or a grid, where the answer at (i, j) depends on neighboring cells (e.g., Longest Common Subsequence, Unique Paths, Edit Distance). State: dp[i][j].

# 2D DP: Longest Common Subsequence
def lcs(s1, s2):
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i-1] == s2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    return dp[m][n]

Recognizing DP Problems in Interviews

Two signals that a problem requires DP:
1. Overlapping subproblems: The naive recursive solution recomputes the same inputs.
2. Optimal substructure: The optimal solution to the whole problem can be built from optimal solutions to sub-problems.

If you see "number of ways," "minimum cost," "maximum profit," or "longest/shortest subsequence" — think DP first.