Recursion — DSA Mastery

Call Stack — factorial(4)

Watch calls push onto the stack, then unwind and return values bottom-up.

n =

CALL STACK (top = active)

BOTTOM (main)

The Mental Model

Golden Rule

Don't trace every call! Trust that f(n-1) returns the correct answer. Your job is only: "Given that f(n-1) works, how do I get f(n) from it?"

Every recursive function needs exactly 2 things

1. Base case — the simplest case that doesn't recurse (stops infinite loop).
2. Recursive case — make the problem smaller and call self.

No base case = Stack Overflow

Python default recursion limit is 1000 calls. Missing base case → RecursionError: maximum recursion depth exceeded.

Memoization — Cache Recursive Results

The Problem

Pure recursion for fib(n) = O(2ⁿ) because the same subproblem is solved exponentially many times. fib(5) calls fib(4) and fib(3). fib(4) also calls fib(3). Total calls explode.

The Solution: Cache results

Store computed results in a dict. Before computing, check if already computed. First time: compute and cache. After: return cached value. O(2ⁿ) → O(n).

# Without memo: O(2ⁿ) — exponential
def fib(n):
    if n <= 1: return n
    return fib(n-1) + fib(n-2)

# With memo: O(n) — linear
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]

# Or use @lru_cache decorator
from functools import lru_cache

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

Universal Recursion Template

def solve(problem):
    # 1. Base case — ALWAYS first
    if is_base_case(problem):
        return base_answer

    # 2. Make smaller
    smaller = reduce(problem)

    # 3. Trust it works (leap of faith)
    sub_answer = solve(smaller)

    # 4. Combine to get current answer
    return combine(sub_answer, problem)

Merge Sort — Recursion in Action

def merge_sort(arr):
    if len(arr) <= 1: return arr  # base case
    mid = len(arr) // 2
    left  = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

def merge(l, r):
    res, i, j = [], 0, 0
    while i < len(l) and j < len(r):
        if l[i] <= r[j]: res.append(l[i]); i += 1
        else: res.append(r[j]); j += 1
    return res + l[i:] + r[j:]
# Time: O(n log n) | Space: O(n)

LeetCode Problems

EasyFibonacci NumberBasic recursion + memo
EasyPower of TwoDivide recursively
MediumMerge SortDivide & conquer
MediumPow(x, n)Fast exponentiation
MediumFlatten Nested List IteratorRecursive flatten
HardRegular Expression MatchingRecursion with memo → DP