Recursion Interview Questions — base case first, or it eats you

Recursion is when a function calls itself on smaller versions of the problem until a base case stops it. Interviews test whether you can name the base case and say what each call returns. Writing the recursive signature is the easy part.

Recursion questions feel slippery because the code is short and the thinking is not.

You can get halfway through a solution, realize your helper is doing two jobs, and then spend the rest of the round patching the shape instead of solving the problem.

The current StrongYes corpus already carries the signals. Intuit calls out recursion-heavy OA work. DeepMind still mixes recursion into Google-style coding rounds. Scale AI already frames recursive decomposition as part of its timed screen. The local problem spine already includes subsets, generate-parentheses, word-search, decode-ways, and coin-change. As of April 10, 2026, interviewing.io still breaks out Recursion as its own topic with 12 interview replays, and NeetCode still keeps a standalone recursion guide live.

What interviewers are actually testing

A strong recursion answer usually proves five things:

1. You can define the smaller version of the problem before you write code.
2. You can say exactly when the recursion stops.
3. You know what the helper returns versus what it updates or carries along.
4. You can account for call-stack space instead of pretending recursion is free.
5. You know when the problem has crossed into backtracking or memoization.

Weak candidates say, "I will solve it recursively."

Strong candidates say, "My helper returns the answer for the subtree rooted here," or "My helper explores one partial path and undoes the choice before it returns."

That sentence matters because it tells the interviewer you understand the contract, not just the syntax.

The name-the-shape decision tree

Here is the same reasoning as a flowchart. Walk through it once — out loud if possible — before you write any recursive call. The most common recursion-interview mistake is writing def helper(...) before naming what the helper is responsible for, so this tree is designed to force a shape decision first.

Diagram

Copy source

Rendering diagram...

Green terminals are the shapes where naming the contract basically finishes the design — the helper returns one precise thing and the interviewer can follow you. Amber is where the real interview lives: backtracking hides a landmine in the undo step, memoization hides one in naming the repeated state. Miss either and the code still "works" on the happy path but collapses under scrutiny. Red is the judgment call — recursion is the cleanest explanation but the wrong production choice when stack depth is adversarial, and knowing when to say "I'd switch to an explicit stack" is the sentence that separates strong candidates from clever ones.

The five recursion question families that keep repeating

1. Return-a-value recursion questions

This is the family behind:

• Maximum Depth of Binary Tree
• Balanced Binary Tree
• Same Tree
• many divide-the-tree and bubble-an-answer-up prompts

These questions are cleaner when every call returns one precise thing.

For Balanced Binary Tree, a messy solution computes height in one helper and balance in another and ends up revisiting the same work. The cleaner version gives the helper one contract: return height if the subtree is balanced, otherwise return a sentinel.

PYTHON

Copy

def is_balanced(root): def height(node): if not node: return 0 left_height = height(node.left) if left_height == -1: return -1 right_height = height(node.right) if right_height == -1: return -1 if abs(left_height - right_height) > 1: return -1 return 1 + max(left_height, right_height) return height(root) != -1

The sentence to say out loud is:

"My helper returns subtree height, but -1 means this branch is already unbalanced, so I can stop carrying normal heights upward."

2. Choose, explore, undo questions

This is the family behind:

• Subsets
• Permutations
• Generate Parentheses
• Word Search

This is where plain recursion turns into backtracking.

The job is no longer "return one answer upward." The job is:

• choose one option
• recurse on the smaller state
• undo the choice before trying the next option

If you skip the undo story, your explanation sounds random even when the code works.

PYTHON

Copy

def subsets(nums): result = [] path = [] def dfs(index): if index == len(nums): result.append(path[:]) return path.append(nums[index]) dfs(index + 1) path.pop() dfs(index + 1) dfs(0) return result

The useful line is:

"At each index, I branch into include and skip. path is path-local state, so I undo the include before exploring the skip branch."

If this category is still shaky, pair this page with Backtracking Pattern: Search Trees Without Panic.

3. Split-and-combine questions

This is the family behind:

• merge sort
• tree reconstruction
• expression or interval decomposition
• any prompt where the whole answer is assembled from smaller answers

These questions feel different from backtracking because you are not exploring many candidate paths. You are splitting the problem into smaller pieces and combining their results.

The common mistake is writing the recursive calls before naming the combine step.

Ask yourself:

• what smaller subproblem does the left call solve?
• what smaller subproblem does the right call solve?
• what exact line combines them into the parent answer?

If you cannot answer the third question, you probably do not have the right recursive shape yet.

4. Memoized recursion questions

This is the family behind:

• Decode Ways
• Word Break
• Coin Change
• climbing-stairs-style recurrence problems

The first recursive draft is often fine. The problem is that it repeats the same subproblem over and over.

This is where interviewers want to hear whether you can spot overlapping subproblems and define state.

The clean narration is:

"The recursive choice is fine, but the real state is just the current index," or "The real state is the remaining amount."

Once you say that, memoization stops feeling like a trick. It becomes a lookup table keyed by the state you already named.

This is also the bridge into Dynamic Programming Patterns: The Minimal Mental Model.

5. Recursion-vs-iteration judgment questions

This is the family people ignore until the interviewer asks about constraints.

Sometimes recursion is the cleanest explanation. Sometimes it is the wrong production choice.

That shows up when:

• the recursion depth can get huge
• the language has a shallow recursion limit
• the same traversal is easier to reason about with an explicit stack or queue

As of April 10, 2026, interviewing.io's current recursion guide still calls out space complexity and deep recursion as recurring discussion points, and NeetCode's current guide still anchors the topic around base cases and forward progress toward a stop condition. That matches what strong candidates do in a real round: they use recursion when it clarifies the state, then they say when stack depth becomes a real concern.

If the prompt is a giant grid search or a very deep tree, say it plainly:

"This recursive version is the cleanest to explain, but if constraints make stack depth risky, I would switch to an explicit stack."

That is judgment, not hedging.

Common mistakes that cost easy points

Writing the recursive call before naming the base case

If you do not know when the function stops, you do not know what the function does yet.

Giving one helper two jobs

Either the helper returns a value, or it mutates shared state, or it carries path-local context. It can do more than one of those, but if you cannot explain the split clearly, the code usually turns brittle.

Forgetting the call stack counts as space

If recursion depth can grow to n, say the stack can grow to O(n).

Missing the moment recursion becomes memoization

When the same state repeats, brute-force recursion is not "clean." It is unfinished.

Treating backtracking like normal DFS

If the branch needs to unchoose, say that out loud. Path-local state is the whole interview there.

A better 90-minute recursion prep block

If recursion questions still feel abstract, do one block like this:

1. 20 minutes: solve one return-a-value problem such as Balanced Binary Tree and say the helper contract before you code.
2. 20 minutes: solve Subsets or Generate Parentheses and narrate choose, explore, undo.
3. 20 minutes: solve Word Search and say what state is path-local versus board-global.
4. 20 minutes: solve Decode Ways or Coin Change, then add memoization only after you name the repeated state.
5. 10 minutes: explain when you would keep recursion and when you would switch to an explicit stack or queue.

That block covers the failures that actually repeat:

• vague base cases
• mushy helper contracts
• missing undo logic
• ignored stack space
• late memoization insight

If you want the adjacent surfaces after this, read Binary Tree Interview Questions for Software Engineers: Traversals, Path State, and BST Judgment, Matrices Interview Questions for Software Engineers: Grid Traversal, Mutation Order, and Boundary Discipline, and Backtracking Pattern: Search Trees Without Panic.

Then pick one recursion problem, solve it out loud, and listen for whether your explanation names the base case, the helper contract, and the stack story before the code gets complicated.