Loading…

Module M02 · DSA Curriculum

Recursion Fundamentals

Base case, recursive case, and the call-stack mental model that unlocks trees, graphs, and DP.

beginnerTheory Full theoryPrereq:Complexity & Big-O

Read the theory See all problems

What you'll learn

Write any recursion as a base case plus a recursive case that shrinks the input
Use the call-stack model to predict execution order and stack depth
Distinguish head recursion (work after the call) from tail recursion (work before)
Derive recursion complexity with the branches^depth rule and recurrence relations
Recognise when recursion overflows the stack and convert it to iteration
Apply the divide-and-conquer template (split, solve halves, combine)

When to reach for this

Signals (use it)

The problem is defined in terms of itself (tree node = value + subtrees)
"Generate all ..." subsets / permutations / combinations → backtracking recursion
Divide the input in half and combine (merge sort, binary search)
Structure is nested or hierarchical (trees, nested lists, file systems)

Anti-signals (don't)

Simple linear iteration is clearer (don't recurse to sum an array)
Recursion depth could exceed ~10^4–10^5 → risk of stack overflow, prefer iteration
Overlapping subproblems with no memo → exponential blowup, add DP

Theory & deep dive

Recursion is a function that solves a problem by calling itself on a smaller version of the same problem. It feels like magic until you internalise one idea: trust the recursion. Assume the recursive call already returns the correct answer for the smaller input, then just combine it with the current step. Stop trying to trace every call in your head — that way lies madness.

Recursion is the gateway to half of this curriculum. Trees, graphs, backtracking, divide-and-conquer, and top-down DP are all recursion with extra structure. If recursion is shaky, those topics feel impossible; once it clicks, they feel obvious.

This module nails the two-part anatomy (base case + recursive case), the call-stack model that explains why recursion works and when it overflows, how to read a recurrence's complexity, and when to convert recursion to iteration.

The big idea in plain words

Recursion is solving a big problem by trusting a smaller copy of yourself to handle the smaller version - like Russian nesting dolls. You open a doll, find a smaller identical doll inside, and keep going until the tiniest one that doesn't open (the base case). Then everything closes back up.

The secret is to stop tracing every call in your head and simply trust the smaller answer. Example: factorial(3) means '3 times whatever factorial(2) gives me'. You trust factorial(2) hands back 2, so factorial(3) becomes 6. Each call quietly waits on a smaller one until factorial(1) = 1 starts the chain coming back.

The anatomy of every recursion

Every correct recursion has exactly two parts. Miss either and it breaks.

Part	Job	Failure mode if wrong
Base case	The smallest input you answer directly, no recursion.	Missing → infinite recursion → stack overflow
Recursive case	Solve a smaller input, then combine with the current step.	Doesn't shrink → never reaches base case

The golden rule: every recursive call must move strictly closer to a base case. If the input doesn't get smaller (shorter array, fewer nodes, smaller number), the recursion never terminates.

Java· Factorial — base + recursive case

long factorial(int n) {
    if (n <= 1) return 1;        // base case
    return n * factorial(n - 1);  // recursive case (n shrinks)
}

The call-stack mental model

Each call pushes a frame onto the call stack holding its local variables and where to resume. When a call returns, its frame pops and control returns to the caller. The base case is what lets the stack start unwinding.

The calls go down to the base case, then results bubble back up. The maximum number of frames alive at once is the recursion depth — and that is your space cost. Too deep and you get a StackOverflowError / RecursionError.

Watch out

Default stack depth is ~10^4 in Python and ~10^4–10^5 in the JVM. A recursion that goes n deep on n = 10^6 will overflow — convert it to an explicit stack or a loop.

Head vs tail recursion

The distinction is where the work happens relative to the recursive call.

Tail recursion: the recursive call is the last action; nothing happens after it returns. Some languages optimise this into a loop (no stack growth) — but Java and Python do NOT, so it still costs O(depth) stack.
Head recursion: work happens after the recursive call returns (like n * factorial(n-1)). This is the common case and inherently needs the stack to remember the pending work.

Knowing the difference matters because tail-recursive shapes are the easiest to rewrite as clean iterative loops when you need to kill the stack cost.

Complexity of recursion

Two tools cover almost everything.

1. The branches^depth shortcut. Count how many recursive calls each call makes (branches) and how deep the tree goes (depth). Total calls ≈ branches^depth.

2. Recurrence relations for divide-and-conquer, via the Master Theorem intuition:

Recurrence	Example	Complexity
T(n) = T(n-1) + O(1)	factorial, linear recursion	O(n)
T(n) = T(n/2) + O(1)	binary search	O(log n)
T(n) = 2T(n/2) + O(n)	merge sort	O(n log n)
T(n) = 2T(n-1) + O(1)	naive Fibonacci, subsets	O(2^n)

Space is the maximum depth of the recursion (longest root-to-base path), because that's how many frames coexist.

Tip

Naive Fibonacci is O(2^n) because it re-solves the same subproblems. Add a memo (cache) and it drops to O(n) — that single change is the bridge from recursion to dynamic programming.

The divide-and-conquer template

A huge family of efficient algorithms follows one shape: split the input, solve each half recursively, combine the results. Merge sort, quicksort, and many tree algorithms are instances.

Python· Merge sort — divide and conquer

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

def merge(l, r):
    out, i, j = [], 0, 0
    while i < len(l) and j < len(r):
        if l[i] <= r[j]: out.append(l[i]); i += 1
        else: out.append(r[j]); j += 1
    return out + l[i:] + r[j:]

When (and how) to convert to iteration

Convert recursion to iteration when depth could overflow the stack, or when an explicit loop is simply clearer. The mechanical conversion: replace the call stack with your own explicit stack (a list/deque), pushing the state you'd otherwise pass to the recursive call.

Linear tail-style recursions (factorial, list traversal) become simple for/while loops. Tree/graph DFS becomes a while stack: loop that pops a node and pushes its children. BFS uses a queue instead of a stack to get level-order instead of depth-first.

How to talk about this in the interview

“When you choose recursion, say it explicitly: "This problem is self-similar — each subtree is the same shape — so I'll solve it recursively. My base case is an empty node returning 0; the recursive case combines the answers from the left and right subtrees." Always state the base case first; it proves you won't infinite-loop. Then give the complexity using branches^depth or the recurrence, and flag the stack depth as your space cost.”

Common mistakes

–Missing or wrong base case → infinite recursion and stack overflow
–Recursive call that doesn't shrink the input → never terminates
–Forgetting recursion depth is O(depth) space (the call stack)
–Re-solving overlapping subproblems without memoisation → exponential time
–Assuming Java/Python optimise tail calls — they don't; deep tail recursion still overflows
–Mutating shared state across calls without undoing it (a backtracking bug)

Complexity summary

Recursion time is (branches per call)^(depth) for branching recursion, or solved via the recurrence T(n) for divide-and-conquer. Space is the maximum recursion depth (frames alive simultaneously): O(log n) for balanced splits, O(n) for linear or skewed recursion.

Practice problems

0 total

No problems indexed here yet.

Previous module

M01 · Complexity & Big-O

The language interviewers use to compare solutions.

Next module

M03 · Arrays & Hashing

The O(1) lookup lever that unlocks 40% of interview questions.