Recursion Interview Questions: How to Think Recursively

Recursion trips people up because they try to trace the whole call stack in their head. Do not. The trick is to trust the recursion: define what the function returns for one input, assume it already works for smaller inputs, and combine those results. If you can state the base case and the recursive case in plain English, the code writes itself. This guide gives you a template, five worked examples from our question bank, and the mistakes we see most often in mock interviews.

The mental model: three questions

Every recursive solution answers three questions. Get these right and the rest is syntax.

What is the smallest input I can answer immediately? That is your base case. For a factorial it is n == 0. For a tree it is a null node. For string matching it is "both strings are empty."
How do I shrink the problem toward that base case? Every recursive call must move closer to the base case, or you get infinite recursion. Shrink by index, by node, by remaining length, by numeric value.
Assuming the recursive call returns the correct answer for the smaller input, how do I build my answer from it? This is the leap of faith. Do not trace it. Assume solve(smaller) is correct and use its result.

That third step is where most candidates freeze. The whole point of recursion is that you never manually unwind the stack. You define the contract once and reuse it.

A template you can reuse

Here is the shape almost every recursive interview answer takes:

def solve(state):
    # 1. Base case: smallest input, answer directly
    if is_base_case(state):
        return base_value

    # 2. Recurse on one or more smaller states
    #    (trust that these return correct answers)
    sub = solve(next_state(state))

    # 3. Combine and return
    return combine(state, sub)

Backtracking, tree traversal, and divide and conquer are all specializations of this. When the recursion branches into multiple choices and you undo state between calls, you are doing backtracking. When it splits input in half and merges, you are doing divide and conquer. When it walks children, it is a tree or graph depth-first search.

Worked examples from the question bank

Start simple: Power of Three

"Power of Three" (junior) asks whether an integer n equals 3 raised to some power. The recursive contract is clean: a number is a power of three if it is 1, or if it is divisible by 3 and the quotient is also a power of three.

def isPowerOfThree(n):
    if n < 1:        # base case: nothing below 1 qualifies
        return False
    if n == 1:       # base case: 3^0
        return True
    return n % 3 == 0 and isPowerOfThree(n // 3)

Notice how each call divides n by 3, so it reaches the base case in log-base-3 steps. This is the fastest problem in the set to prove you understand base cases and shrinking. The follow-up (solve it without loops or recursion) is a nice segue into the math trick of checking whether the max 32-bit power of three is divisible by n.

Counting with recursion: Unique 3-Digit Even Numbers

"Unique 3-Digit Even Numbers" (junior) asks how many distinct three-digit even numbers you can form from a digit array. This is a classic "build a sequence position by position" recursion: choose the first digit (not zero), the second, and the third (must be even), tracking used indices. The base case is "three digits chosen." A hash set of the assembled numbers handles the distinctness requirement. It is a gentle introduction to the branching that powers full backtracking problems, and interviewers love it because the constraints (no leading zero, last digit even, no reusing an array slot) force you to be precise about state.

Recursion that returns structures: All Possible Full Binary Trees

"All Possible Full Binary Trees" (mid_senior) is where the leap of faith pays off. A full binary tree with n nodes has a root plus a left subtree of i nodes and a right subtree of n - 1 - i nodes, and both i and n - 1 - i must be odd (full trees only exist with an odd node count).

def allPossibleFBT(n):
    if n % 2 == 0:
        return []
    if n == 1:
        return [TreeNode(0)]
    result = []
    for left_count in range(1, n, 2):
        right_count = n - 1 - left_count
        for L in allPossibleFBT(left_count):
            for R in allPossibleFBT(right_count):
                result.append(TreeNode(0, L, R))
    return result

You never think about how the subtrees are built. You assume allPossibleFBT(left_count) hands you every valid left subtree and combine them. This is the pattern for any problem that generates all structures of a given size, and it lives at the intersection of recursion and tree reasoning.

Two-dimensional base cases: Wildcard Matching

"Wildcard Matching" (staff) matches a string s against a pattern p where ? matches one character and * matches any sequence. The recursion is over two indices, i into s and j into p:

If p[j] is *, either it matches zero characters (advance j) or one more character (advance i).
If p[j] is ? or equals s[i], advance both.
Base case: j reaches the end of p; return true only if i also reached the end of s.

Written naively this is exponential. Memoize on (i, j) and it becomes polynomial. That transition is the single most important recursion skill for staff-level interviews.

Recursion with a moving pointer: Basic Calculator

"Basic Calculator" (staff) evaluates an expression string with +, -, and parentheses, no built-in eval allowed. The natural structure is recursive: when you hit (, recurse to evaluate the sub-expression until the matching ), then treat the returned value as a single number. A shared index (or an iterator) tells each call where to resume. This is the same recursive-descent idea real parsers use, and it shows an interviewer you can manage state across calls, not just crunch numbers.

When recursion becomes dynamic programming

Wildcard Matching hints at the big pattern: if your recursion recomputes the same (state) many times, cache it. Add a dictionary keyed on the arguments, check it at the top, store before you return. That single change turns exponential brute force into a memoized solution, which is the entire foundation of dynamic programming. In interviews we tell candidates to always write the recursive version first, confirm correctness, then optimize. Trying to write bottom-up tabulation cold is where people make off-by-one errors and lose time.

The mistakes we see every day

Running mock interviews, the same recursion failures repeat:

Missing or wrong base case. This is the top cause of infinite recursion and wrong answers. Write the base case first, before the recursive case.
Recursing without shrinking. If a call does not move toward the base case, you loop forever. State exactly what gets smaller.
Ignoring the stack limit. In Python the default recursion depth is around 1,000 calls, and exceeding it raises a RecursionError; you can raise it with sys.setrecursionlimit, but for deep linear recursion an iterative version is usually the right call. Python has a default maximum recursion depth of 1000, and if a function exceeds this limit it can be increased using sys.setrecursionlimit(n).
Assuming tail recursion is free. CPython does not eliminate tail calls, so a tail-recursive loop still grows the stack. Guido van Rossum has explained that tail call optimization can make programs harder to debug because it removes frame objects from the call stack, which removes debugging information. If depth is a concern, convert to iteration with an explicit stack.
Recomputing subproblems. If you see the same arguments twice, memoize.

How to practice recursion for interviews

Order matters. Start with "Power of Three" and "Unique 3-Digit Even Numbers" to lock down base cases and branching. Move to "All Possible Full Binary Trees" for structure-returning recursion. Then push into "Wildcard Matching" and "Basic Calculator," which force you to handle two-dimensional state and memoization. Say the three questions out loud before you write code: base case, how it shrinks, how you combine. When you can articulate those in one breath, you are ready. You can drill these with feedback on our practice page.

FAQ

How do I find the base case in a recursion problem?

Ask what the smallest possible input is and what the answer is for it: an empty string, a null node, n == 0, or a single element. If a problem has multiple ways to be "smallest" (like both strings being empty in matching), handle each explicitly. Writing the base case first prevents most infinite-recursion bugs.

When should I use recursion versus iteration in an interview?

Use recursion when the problem is naturally defined in terms of smaller versions of itself: trees, backtracking, divide and conquer, and expression parsing. Use iteration when the recursion is a simple linear loop or when input depth could blow the stack. Many interviewers accept either as long as your reasoning is clear.

Is recursion or dynamic programming better for interviews?

They are the same tool at different stages. Recursion expresses the logic; memoization or tabulation makes it efficient. Write the recursive solution first to prove correctness, then add caching if subproblems repeat. Jumping straight to a DP table without the recursion usually causes indexing errors.

How deep can recursion go before it breaks?

It depends on the language runtime. In CPython the default is roughly 1,000 frames before a RecursionError, and each frame consumes stack memory. For inputs that could exceed that, convert to an explicit stack-based iteration or raise the limit deliberately.

Do interviewers care about recursion versus a "clever" iterative trick?

They care that your solution is correct, clear, and that you can explain the complexity. A clean recursive solution that you can walk through beats a cryptic one-liner. Optimize only after you have a working version and have stated the trade-off out loud.