Recursion & DP

Recursion & Dynamic Programming

Recursion breaks a problem into smaller sub-problems. DP = recursion + memoization (top-down) or tabulation (bottom-up) to avoid redundant work.

When to use DP: overlapping subproblems + optimal substructure.

Recursion Template

def solve(n):
    # 1. Base case(s) — must exist to terminate
    if n == 0:
        return 1
    # 2. Recursive case — smaller sub-problem
    return n * solve(n - 1)

Top-Down DP (Memoization)

Without memo, triple step is O(3ⁿ). With memo it's O(n).

# Option 1: lru_cache decorator (cleanest)
from functools import lru_cache

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

# Option 2: manual memo dict
def fib(n, memo={}):
    if n <= 1: return n
    if n in memo: return memo[n]
    memo[n] = fib(n-1, memo) + fib(n-2, memo)
    return memo[n]

Bottom-Up DP (Tabulation)

def fib(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]

# Space-optimised: only need last 2 values
def fib_opt(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

Triple Step (Stair Climbing)

@lru_cache(maxsize=None)
def count_ways(n):
    if n < 0: return 0
    if n == 0: return 1       # one way to stand at bottom: do nothing
    return count_ways(n-1) + count_ways(n-2) + count_ways(n-3)

Coin Change (number of ways)

Key insight: process each coin in an outer loop to avoid counting permutations as distinct combinations.

def coin_change_ways(amount, coins):
    dp = [0] * (amount + 1)
    dp[0] = 1                      # one way to make 0: use no coins
    for coin in coins:
        for amt in range(coin, amount + 1):
            dp[amt] += dp[amt - coin]
    return dp[amount]

0/1 Knapsack

def knapsack(weights, values, capacity):
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for w in range(capacity + 1):
            dp[i][w] = dp[i-1][w]           # skip item i
            if weights[i-1] <= w:
                dp[i][w] = max(dp[i][w],
                               dp[i-1][w - weights[i-1]] + values[i-1])
    return dp[n][capacity]

Powerset Generation (Backtracking)

Generate all 2ⁿ subsets:

def powerset(nums):
    result = [[]]
    for n in nums:
        result += [subset + [n] for subset in result]
    return result
# Time: O(2^n), Space: O(2^n)

Permutation Generation

def permutations(s):
    if len(s) == 0: return [""]
    result = []
    for i, char in enumerate(s):
        rest = s[:i] + s[i+1:]
        for perm in permutations(rest):
            result.append(char + perm)
    return result
# Time: O(n!), Space: O(n!)

Backtracking Template

Build solution incrementally, backtrack when a constraint is violated:

def backtrack(candidate, result, ...):
    if is_complete(candidate):
        result.append(candidate[:])   # save a copy
        return
    for next_choice in generate_choices(candidate):
        if is_valid(next_choice):
            candidate.append(next_choice)    # make move
            backtrack(candidate, result, ...)
            candidate.pop()                  # undo move (backtrack)

Common problems: N-Queens, Sudoku solver, permutations, combinations, word search.

Recursive Multiplication (no * operator)

def multiply(a, b):
    """Multiply using bit shifts and addition."""
    if b == 0: return 0
    if b == 1: return a
    half = multiply(a, b >> 1)   # b // 2 via right shift
    if b % 2 == 0:
        return half + half
    else:
        return half + half + a   # odd: add one more a
# x * 2 = x << 1 (left shift)

DP Pattern Summary

| Pattern | Example problems | |---------|-----------------| | 1D DP | Fibonacci, climbing stairs, house robber | | 2D DP | Longest common subsequence, edit distance, unique paths | | Knapsack | Subset sum, coin change, partition equal subsets | | Interval DP | Matrix chain multiplication, burst balloons |

Key Interview Tips

• Always identify the recurrence relation before writing code
• Draw the recursion tree — overlapping sub-trees = use DP
• Top-down is easier to write; bottom-up is more space-efficient
• State definition is everything in DP — what does dp[i] represent?
• For backtracking: always undo your move after recursing