What Is Recursion? The Foundation Behind Half Your Interview Problems

You have a function. It needs to solve a problem. So it calls itself to solve a smaller version of that problem. Then that call does the same. And again. Until the problem is small enough to answer directly. Then the whole thing unwinds like a spring and hands you the answer.

What is recursion? Exactly that. Not a trick, not dark magic your CS professor pulled out to watch freshmen suffer. A systematic way to break a big problem into smaller identical copies of itself, then assemble the answer on the way back out.

If you're early in your DSA prep, recursion is the concept that unlocks everything else. Tree traversal, backtracking, depth-first search, dynamic programming. Get comfortable here and a huge chunk of interview problems start feeling familiar instead of terrifying.

Two Laws You Can't Break

Every recursive function has exactly two parts. Miss either one and your code either returns the wrong answer or crashes in an extremely memorable way.

The base case is where recursion stops. It's the smallest version of the problem you can answer directly, without calling yourself again. For a function counting down from n, the base case is n = 0. No base case means the function calls itself forever, which sounds philosophical until Python raises a RecursionError at you.

The recursive case is where you call yourself with a smaller input. Each call must get closer to the base case. Not sideways. Not bigger. Closer. If it doesn't, you get infinite recursion, and Python will politely inform you of this after 1,000 frames.

That's the whole structure. Base case plus recursive case. It's basically a loop with a fragile ego.

Start With Factorial

The factorial of n (written n!) is n times every positive integer below it. So 5! = 5 × 4 × 3 × 2 × 1 = 120.

Factorial is the Hello World of recursion. Everyone starts here, not because it's the most interesting use case (it isn't) but because the pattern is impossible to miss.

Notice: 5! = 5 × 4!. And 4! = 4 × 3!. And so on. The problem keeps reducing itself until you hit 1! = 1, which you can answer directly without any further existential crisis.

def factorial(n: int) -> int:
    if n <= 1:        # base case
        return 1
    return n * factorial(n - 1)   # recursive case

Call factorial(5) and here's what happens: the function calls factorial(4), which calls factorial(3), down to factorial(1). That returns 1. Then 2 × 1 = 2 bubbles back up. Then 3 × 2 = 6. Then 4 × 6 = 24. Then 5 × 24 = 120.

The answers get assembled on the way back up. That's the key mental model. Your function doesn't compute anything meaningful going down. It's just stacking up promises. The math happens on the return trip.

What the Call Stack Is Actually Doing

Each function call opens a new frame on the call stack. That frame holds the local variables, the return address, and the parameter for that specific call. When factorial(5) calls factorial(4), the factorial(5) frame waits on the stack doing absolutely nothing while all the calls below it figure their lives out.

At the deepest point of factorial(5), you have five frames sitting on the stack simultaneously. Once factorial(1) returns, the frames unwind from the bottom back up, each one finally doing the multiplication it's been waiting to do.

The space complexity of a recursive function is O(maximum stack depth), not O(total calls made). For factorial, that's O(n). For binary search, it's O(log n). For a balanced binary tree DFS, it's O(h) where h is the height. Recursion space complexity goes deeper on this, including why Python's 1,000-frame default can bite you on large inputs. (Spoiler: 1,000 sounds like a lot until you're parsing a linked list with 10,001 nodes.)

If you want to understand exactly what a stack frame contains at the hardware level, call stack mechanics walks through the actual x86-64 instructions. It's dense, but the kind of dense that makes you feel smart afterward.

The Leap of Faith

Here's the mental shift that makes recursion click: when you're writing the recursive case, assume the recursive call already works. Don't trace the whole chain in your head. Don't draw every arrow. Just trust it.

For factorial(n), the recursive case is n * factorial(n - 1). Don't simulate factorial(n - 1) down to the base case and back up. Just accept: "if I call factorial with a smaller number, I get the right answer back." Then write the one line that uses that answer.

This is the leap of faith, and it's what separates engineers who write recursive code in two minutes from engineers who spend the rest of their time slot drawing call trees on the whiteboard.

It works because of induction. If the base case is correct and the recursive case always gets closer to the base case, the whole thing is provably correct. You don't have to verify every possible call chain. You just have to trust the two rules.

Trust the base case. Trust that smaller works. Write the line that connects them.

The Problem Type You'll Actually See in Interviews

Factorial teaches the mechanics. But interview problems look more like this.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def max_depth(root: TreeNode | None) -> int:
    if root is None:          # base case: empty tree has depth 0
        return 0
    left_depth = max_depth(root.left)
    right_depth = max_depth(root.right)
    return 1 + max(left_depth, right_depth)

LeetCode 104. The base case handles None. The recursive case trusts that max_depth already works for the left and right subtrees. You just use the answers.

Tree problems are natural fits for recursion because every node is the root of its own subtree. The structure is self-similar all the way down. The moment you see a binary tree in an interview, recursion should be the first thing you reach for, not the last.

Time Complexity: Count the Work at Each Level

For a recursive function, the time complexity is the total work done across all calls. This trips people up because you have to think about the whole call tree, not just one invocation.

For factorial(n), you make n calls and do O(1) work in each. Total: O(n).

For binary search, you make O(log n) calls and do O(1) work per call. Total: O(log n).

For max_depth, you visit every node exactly once. That's O(n) where n is the number of nodes.

The pattern: draw the recursion tree, figure out how many nodes it has, multiply by the work per node. Recursion time complexity covers the Master Theorem for divide-and-conquer recurrences and walks through merge sort, Fibonacci, and more. Interviewers love asking about this stuff.

Three Patterns Recursion Enables

Once you have recursion down, three major interview patterns open up.

Divide and conquer. Split the input in half, recurse on each half, combine the results. Merge sort is the canonical example. Binary search is a degenerate version where you only recurse on one half and throw the other away.

Tree and graph traversal. Every DFS is recursive in structure, whether you implement it with actual recursion or an explicit stack. If you can solve it on a single node plus its children, you can solve it on any tree. Depth-first search shows how DFS generalizes across trees, graphs, and grids.

Backtracking. Generate all valid solutions by exploring choices, then undo them and try the next option. Permutations, subsets, N-Queens. The recursive structure handles the "undo" automatically when a call returns, which is elegant. Backtracking algorithm covers this pattern with code.

Dynamic programming is also built on recursion. The memoized version is literally a recursive function with a cache. Dynamic programming framework starts with this angle if you want to see the connection explicitly.

Where It Falls Apart

Forgetting the base case. Classic. Your function recurses forever, Python counts to 1,000, and then it throws a RecursionError with an unhelpful stack trace that is 1,000 lines long. Every line says the same thing. Check that every branch either hits the base case or gets provably closer to it.

The base case is wrong. factorial(0) should return 1, not 0. Off-by-one errors in the base case produce silently wrong answers, which are significantly worse than crashes because nothing tells you something is wrong. Trace through one or two small examples manually after writing the function. Yes, manually. Get the pen.

Mutating shared state across calls. This one is sneaky and it shows up constantly in backtracking problems. If you append to a list and pass that list down, every call is sharing the same object. When the call unwinds and you expect the list to be smaller, it isn't. You've been accumulating garbage the whole time.

# Wrong: path is shared and grows permanently
def dfs(node, path):
    path.append(node.val)   # mutates shared list
    ...

# Right: each call gets its own copy
def dfs(node, path):
    dfs(child, path + [node.val])   # new list per branch

Not trusting the recursion. Writing an iterative loop inside the recursive case because you don't believe the function call below you works. This produces overcomplicated code that usually has its own bugs. Write the recursive structure cleanly. Apply the leap of faith. Trust the base case.

When to Reach for Recursion

Use recursion when the problem has a recursive structure: trees, graphs, divide-and-conquer, generate-all problems. The code will be shorter and clearer than the iterative version. The intent will be obvious to anyone reading it.

Don't use it when you have deep input and Python's 1,000-frame limit could bite you. A linked list with 10,000 nodes and a naive recursive traversal will crash before it gets halfway. Convert to iteration instead. When to convert recursion to iteration covers this tradeoff and when it actually matters in practice.

Practicing Recursion Out Loud

Reading recursive code is one skill. Writing it from scratch under interview pressure is another skill entirely. They don't transfer as much as you'd think.

The failure mode isn't forgetting the pattern. It's losing track of what the function is supposed to return, mid-problem, because you started mentally tracing the call stack instead of applying the leap of faith. That's a pressure artifact, and it responds to practice under interview-like conditions, not to reading more LeetCode solutions.

SpaceComplexity runs voice-based mock interviews where you have to talk through your recursive reasoning as you code. If you can explain "the base case is X, the recursive case reduces toward it because Y" out loud to an interviewer asking follow-up questions, you actually understand it. If you can only understand it while staring at it silently, you'll discover that gap at the worst possible time.