Searching a word in a dictionary works by checking the middle, deciding which half to explore, and repeating on a smaller section. That repeated breakdown is recursion: solving a problem by reducing it to smaller versions of itself.

Recursion can feel confusing at first, but once the core ideas click, it becomes a useful tool. It underpins techniques like backtracking, divide and conquer, tree traversals, and dynamic programming.

This chapter covers how recursion works, how the call stack handles it, how to visualize it, and when to use it over iteration.

Recursion is when a function calls itself to solve a smaller version of the same problem. That is the one-sentence definition. Here is what it means in practice.

Every recursive function has two parts:

If you forget the base case, your function will call itself infinitely until the program crashes with a stack overflow. If your recursive case does not make the problem smaller, you will never reach the base case.

The classic example is computing the factorial of a number. Recall that n! = n * (n-1) * (n-2) * ... * 1, and by definition, 0! = 1.

The code mirrors the mathematical definition. The base case handles n == 0, and the recursive case expresses n! in terms of (n-1)!. Each call reduces n by one, so we are guaranteed to eventually reach the base case.

For problems that have a naturally recursive structure, the code is often a direct translation of the definition.

When you call a function in Java, the runtime creates a stack frame for that call. A stack frame stores everything the function needs: its parameters, local variables, and where to return to when it finishes. These frames are pushed onto the call stack, a last-in-first-out (LIFO) data structure that the JVM manages for you.

With recursion, each recursive call pushes a new frame onto the stack. The function does not resume until the call it made returns. This creates a chain of paused function calls, each waiting for the one below it to finish.

Here is a trace of factorial(4):

The following animation shows the call stack at different points:

Once factorial(0) returns 1, the stack starts unwinding. Each frame resumes, multiplies its n by the returned value, and passes the result back up. The stack shrinks one frame at a time until factorial(4) finally returns 24.

This is why recursion uses O(n) space for a function with n recursive calls. Each call adds a frame, and the stack can only hold so many before running out of memory. In Java, the default stack size is 512KB to 1MB depending on OS, which typically supports tens of thousands of frames for small methods (the exact depth depends on per-frame size). Go deeper than that and you get a StackOverflowError.

Every recursive call costs memory (one stack frame) and time (function call overhead). Keep this in mind when deciding between recursion and iteration.

When writing a recursive function, you do not need to mentally trace through every single recursive call to convince yourself it works. Instead, you take what is called the recursive leap of faith: you trust that the recursive call will correctly solve the smaller subproblem, and you focus only on what the current call needs to do.

Here is the approach applied to a concrete problem.

Suppose you want to write a function that sums all elements in an array. Here is how to think about it with the recursive leap of faith:

You do not need to think about what happens when sum calls itself for i + 2, i + 3, and so on. You only need to know three things:

If all three are true, the function is correct. This is the same reasoning behind mathematical induction, and it works here for the same reasons.

The recursive leap of faith is especially useful for tree problems. Consider computing the height of a binary tree:

You do not trace through the entire tree in your head. You trust that height(node.left) and height(node.right) return the correct heights of their respective subtrees, then add 1 for the current node and take the maximum.

This mental model matters for backtracking and dynamic programming problems, where the recursion trees can be enormous and impossible to trace mentally.

Drawing a recursion tree is a useful skill for analyzing any recursive function. A recursion tree shows every call the function makes, organized as a tree where each node is one call and each edge represents a recursive invocation.

Recursion trees help you:

Factorial Recursion Tree

The recursion tree for factorial(4) is a straight line because each call makes exactly one recursive call:

This is a linear recursion tree. It has n + 1 nodes, confirming that factorial runs in O(n) time and O(n) space.

Fibonacci Recursion Tree

The Fibonacci function makes two recursive calls per invocation:

Here is the recursion tree for fib(5):

Two things stand out:

1. The tree is huge. Each level roughly doubles the number of nodes. At level 0 we have 1 node, at level 1 we have 2, at level 2 we have up to 4, and so on. The total number of nodes is approximately 2^n, which means the naive Fibonacci implementation runs in O(2^n) time. For fib(50), that is tens of billions of calls, which would take several minutes to run, and the cost keeps doubling for every additional input.

2. There are overlapping subproblems. Look at the tree carefully. fib(3) is computed twice. fib(2) is computed three times. fib(1) is computed five times. We are doing the same work over and over. This observation leads to dynamic programming, where you store results of subproblems to avoid recomputing them. We will cover that in detail in the dynamic programming section of this course.

How to Draw a Recursion Tree

Here is a step-by-step approach you can use for any recursive function:

Practice this on paper with small inputs.

Every recursive function can be converted to an iterative one, and vice versa. So when should you use which?

Comparison

When Recursion Is Clearer

Recursion works well when the problem has a naturally recursive structure:

When Iteration Is Better

Iteration wins when:

Converting Recursion to Iteration

Converting the factorial function from recursive to iterative is straightforward because factorial uses linear recursion (one recursive call per invocation):

Recursive version:

Iterative version:

The iterative version uses O(1) space instead of O(n) and avoids all function call overhead. For simple linear recursion like this, the iterative version is preferred.

For more complex recursion (like tree traversals or backtracking), conversion to iteration requires an explicit stack data structure, which often makes the code harder to read without any real benefit. In those cases, the recursive version is the better choice.

Not all recursive functions use the call stack in the same way. There is a special form called tail recursion where the recursive call is the last thing the function does. No computation happens after the recursive call returns.

Compare the two forms.

Not tail recursive (regular recursion):

In this version, after factorial(n - 1) returns, the function still needs to multiply the result by n. So it cannot discard its stack frame yet. It has to hold onto n while waiting.

Tail recursive version:

In the tail recursive version, the recursive call is the last operation, with no pending work. The current frame's n and accumulator are no longer needed once the call is made.

Why Does This Matter?

Some languages and compilers perform tail call optimization (TCO). When they detect a tail recursive call, they reuse the current stack frame instead of creating a new one. This turns the recursion into a loop behind the scenes, giving you O(1) space instead of O(n).

Here is what the call stack looks like with and without TCO:

The Java Caveat

Java does not perform tail call optimization. The JVM does not reuse stack frames for tail recursive calls, so tail recursive Java code uses exactly the same O(n) stack space as regular recursion.

So why learn about it? A few reasons:

To convert a tail recursive function to iteration, replace the recursive call with a loop:

The loop updates the accumulator and reduces n, the same work the tail recursive version does at each call.

Here is a real problem that ties together the ideas above: computing x raised to the power n.

Naive Approach: O(n)

The most straightforward approach multiplies x by itself n times:

This works, but it makes n recursive calls. For pow(2, 1000), that is 1000 calls. Can we do better?

Optimized Approach: O(log n) using Fast Exponentiation

A mathematical identity helps here:

Instead of reducing n by 1 each time, we cut it in half. This gives us O(log n) calls instead of O(n). Calling fastPow(x, n/2) once and squaring the result is what gives the O(log n) bound. Writing fastPow(x, n/2) * fastPow(x, n/2) instead makes two recursive calls per level and degrades the algorithm back to O(n).

Step-by-Step Trace

Here is a trace of pow(2, 10):

Only 5 recursive calls for n = 10, compared to 10 calls with the naive approach. The recursion tree looks like this:

It is a straight line with log2(n) nodes, confirming the O(log n) time and space complexity. This technique is called fast exponentiation or exponentiation by squaring, and it shows up in interview problems and competitive programming.

The recursive leap of faith applies here too. We trusted that fastPow(x, n / 2) would give us the correct answer for the half-sized problem, and we squared the result (with an extra multiplication for odd n).

Here are the common mistakes to watch for when writing recursive code.

Mistake 1: Missing or Incorrect Base Case

Without a base case, the function recurses forever and crashes with a StackOverflowError.

Also watch out for base cases that are too narrow. If your function can receive negative inputs but your base case only checks n == 0, negative inputs will recurse infinitely.

Mistake 2: Not Reducing the Problem Size

Each recursive call must make progress toward the base case. If the input does not get smaller, you have an infinite loop.

Mistake 3: Modifying Shared State Without Restoring It

When multiple recursive branches share state (like a list or array), you must undo changes before exploring the next branch. This comes up often in backtracking, which we cover in the next chapter.

Mistake 4: Stack Overflow from Excessive Depth

Even correct recursive code will crash if the input is too large. Java's default stack size is 512KB to 1MB depending on OS, which typically supports tens of thousands of frames for small methods (the exact depth depends on per-frame size).

As a rule of thumb, if recursion depth can exceed roughly 10,000 in Java or Python, convert to iteration or use an explicit stack. The actual limit depends on JVM or runtime configuration and per-frame size, but 10K is a safe ceiling to start considering alternatives. For algorithms that may run on adversarial inputs (deeply nested JSON, linked lists from untrusted sources), explicit stacks prevent stack-bomb denial of service.

Solutions:

Mistake 5: Redundant Computation

Computing the same subproblem multiple times is the biggest performance trap in recursion. We saw this with the Fibonacci example, where the naive recursive solution is O(2^n).

Adding a memo (cache) turns exponential time into linear time. This technique is called memoization, and it leads into dynamic programming, which we will cover later in the course.

Recursive solutions to problems like Fibonacci recompute the same subproblems exponentially many times. Looking back at the fib(5) recursion tree from earlier, fib(3) is computed twice, fib(2) is computed three times, and fib(1) is computed five times. Each repeated call expands its own full subtree of work. For fib(50), the total call count grows into the tens of billions even though there are only 51 distinct subproblems.

The fix is to store each computed result the first time it is calculated and return it from the cache on subsequent calls.

With the cache in place, the recursion tree collapses into a directed acyclic graph. Each unique subproblem is solved once, and every later reference reads the cached value in O(1). For Fibonacci, this drops the time from O(2^n) to O(n) with O(n) extra space for the cache.

Top-Down vs Bottom-Up

Memoized recursion is top-down dynamic programming. You start at the original problem, recurse downward, and cache results as the recursion unwinds. Iterative DP is bottom-up: you compute the base cases first and build up the table of answers in order, without any recursion.

Both approaches reach the same time complexity when every subproblem is needed. Bottom-up avoids the recursion stack entirely, which makes it faster in practice and immune to stack overflow on large inputs. Top-down is often easier to write because the structure mirrors the original recursive definition, and it only computes subproblems that are actually reached, which can be a win when the state space is large but sparsely visited.

When Memoization Helps and When It Doesn't

Memoization only helps when subproblems overlap. For algorithms like merge sort or binary search, each recursive call works on a different slice of the input and is never repeated. Adding a cache to those algorithms wastes memory with no speedup. Memoization pays off on problems where the same subproblem is revisited many times: Fibonacci, edit distance, longest common subsequence, coin change, and most other classic DP problems.

A quick way to check: draw the recursion tree for a small input. If you see the same arguments appearing in multiple nodes, memoization will help. If every node has unique arguments, it will not.

The Pure Function Requirement

Memoization assumes the recursive function is pure. The same inputs must always produce the same output, with no side effects. If the function depends on mutable external state, randomness, or the current time, caching the first result is incorrect because later calls might legitimately need a different answer. Before adding a cache, confirm that the function's output depends only on its arguments.