---
title: Recursion and Backtracking Interview Questions (2026)
description: The recursion and backtracking interview questions that come up — base cases, the call stack, recursion trees, memoization and the backtracking template.
url: https://usegreenroom.app/blog/recursion-backtracking-interview-questions
last_updated: 2026-06-21
---

← Back to blog

DSA

# Recursion and backtracking interview questions

June 21, 2026 · 15 min read

![Recursion and backtracking interview questions and answers — a monotone recursion-tree diagram from Greenroom, the AI mock interviewer](/assets/blog/recursion-backtracking-interview-questions-hero.webp)

It's the round you were dreading. The interviewer says, “Solve this with recursion,” and your brain helpfully replays every time recursion has ever betrayed you: the infinite loop at 2am, the `RecursionError` that filled your terminal, the function that called itself forever like a dog chasing its tail. Recursion is the topic that feels like magic when it works and like a trap when it doesn't — which is exactly why interviewers love it. This guide covers the **recursion and backtracking interview questions** that actually come up — base cases, the call stack, recursion trees, memoization, and the backtracking template — with a clear, speakable answer for each.

## How recursion actually works

**Recursion** is when a function solves a problem by calling *itself* on a smaller version of the same problem, until the problem gets small enough to answer directly. Every correct recursive function has exactly two parts: a **base case**, which is the smallest input you can answer without recursing (and which stops the recursion), and a **recursive case**, which breaks the problem into a smaller subproblem, calls itself, and combines the result. Miss the base case and you get infinite recursion — the dreaded stack overflow. Get the recursive case wrong and you get the wrong answer, confidently.

The mechanism underneath is the **call stack**. Each time a function calls itself, the current call is paused and pushed onto the stack, and a new call starts on top. When a call finally hits the base case and returns, it's popped off, and the call beneath it resumes where it left off. The stack is why recursion “remembers” where to come back to — and why deep recursion costs memory: every paused call sits on the stack until its turn to finish. Picture the calls stacking up like plates, then unwinding back down.

The single best way to understand a recursive function's *cost* is to draw its **recursion tree** — every call as a node, with its child calls branching beneath it. The shape tells you everything: the depth is the maximum stack height (your space complexity), and the total number of nodes is the number of calls (your time complexity). Here's the recursion tree for a naive recursive Fibonacci, the example every interviewer reaches for:

![Monotone green recursion tree diagram for fib(4) showing each recursive call branching into two, with base cases fib(1) and fib(0) as filled leaf nodes](/assets/blog/recursion-backtracking-interview-questions-diagram.webp)
*The call tree for a recursive fib(4). Read the shape: depth is your stack height, total nodes are your call count — and notice fib(2) is computed twice.*

Look closely at that tree and you'll spot the problem that launches a thousand follow-up questions: `fib(2)` is computed *twice*, and in a bigger tree the repetition explodes. That overlap is exactly what **memoization** removes — we'll get there. But first, the core questions.

## Recursion interview questions and answers

### Write factorial recursively and explain the base case.

Factorial is the “hello world” of recursion. `n!` is `n × (n-1)!`, and the base case is `0! = 1`. In code:

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

The thing to say out loud: “The base case is `n <= 1`, which stops the recursion and returns 1. Each recursive call shrinks `n` by one, so we're guaranteed to reach the base case.” That last clause — *guaranteed to reach the base case* — is what interviewers are listening for. A base case that the recursion can never actually hit is the most common recursion bug there is.

### Why does recursion cause a stack overflow, and how do you prevent it?

Every pending recursive call occupies a frame on the call stack, and the stack has a finite size. If your recursion goes too deep — because the input is huge, or because of a missing or unreachable base case — you run out of stack space and the program crashes with a stack overflow (Python raises `RecursionError`, typically around 1000 levels deep by default). You prevent it three ways: make sure the base case is actually reachable, convert deep recursion to iteration using an explicit stack, or — in languages that support it — use tail recursion so the compiler can reuse a single stack frame. The honest interview answer names the depth limit as a real constraint, not a theoretical one.

### What's the difference between recursion and iteration?

**Iteration** repeats work with a loop and explicit variables; **recursion** repeats work by calling itself and uses the call stack to hold state. Anything you can do recursively you can do iteratively and vice versa — they're equivalent in power. The trade-off: recursion is often dramatically more readable for naturally recursive structures (trees, graphs, divide-and-conquer), but it carries call-stack overhead and a depth limit. Iteration is usually more memory-efficient and has no depth ceiling, but can be clumsier to write for tree-shaped problems. The mature answer: “I reach for recursion when the problem is naturally recursive — traversing a tree, say — and for iteration when depth could be large or performance is critical.”

### What is head recursion vs tail recursion?

In **tail recursion**, the recursive call is the *very last* thing the function does — there's no pending work after it returns. In **head recursion** (or just non-tail recursion), there's still work to do after the recursive call comes back, like the `n *` in our factorial. The distinction matters because some compilers can optimise tail recursion into a loop, reusing one stack frame and eliminating the stack-overflow risk — called tail-call optimisation. Worth knowing: CPython does *not* do this optimisation, which is part of why deep recursion in Python hits the limit so readily, while languages like Scala or Scheme handle it gracefully.

### What's the time and space complexity of recursive Fibonacci?

Naive recursive Fibonacci — `fib(n) = fib(n-1) + fib(n-2)` — is **O(2ⁿ) time**, because each call spawns two more and the tree roughly doubles at each level (look back at the diagram). Its **space complexity is O(n)**, though, not O(2ⁿ) — a subtle point interviewers love. At any moment, only one path from root to a leaf is on the call stack, and the deepest that path goes is n. So the *tree* is exponential, but the *stack* is linear. Being able to separate “number of calls” (time) from “max stack depth” (space) is a strong signal. For the full breakdown, see our [Big O notation interview questions](/blog/big-o-notation-time-complexity-interview-questions) guide.

### What is memoization and how does it help?

**Memoization** caches the result of each subproblem the first time you compute it, so repeated calls with the same input return instantly from the cache instead of recomputing. For Fibonacci, that overlapping `fib(2)` (and `fib(3)`, and so on) gets computed once and reused, collapsing the time complexity from **O(2ⁿ) down to O(n)** — a staggering improvement that turns an un-runnable function into a trivial one. In Python it's almost free: add `@functools.lru_cache` above the function. Memoization is the bridge from recursion to **dynamic programming** — top-down DP is, essentially, recursion plus memoization. If an interviewer shows you a recursive solution with overlapping subproblems, “memoize it” is very often the answer they're fishing for.

### How do you find the complexity of a recursive function in general?

Count the **branching factor** (how many recursive calls per invocation) and the **depth** (how the input shrinks each call). One call that shrinks the input by one is O(n). Two calls that each shrink it by one is O(2ⁿ). Two calls that each work on *half* the input, with O(n) work to combine — that's merge sort — is O(n log n). For the standard divide-and-conquer shapes the Master Theorem gives a formula, but in an interview, drawing the recursion tree and summing the work per level is almost always enough and far easier to narrate.

## Backtracking: the template that solves half the hard problems

**Backtracking** is recursion with a twist: you build a solution one choice at a time, and when a choice leads to a dead end, you *undo it* (backtrack) and try the next option. It's a systematic, depth-first exploration of all possibilities, pruning branches that can't lead to a valid answer. The beautiful thing is that an enormous family of “hard” interview problems — permutations, combinations, subsets, N-Queens, Sudoku, word search, generating valid parentheses — all collapse onto the *same five-line template* once you see it:

![Monotone green checklist titled The backtracking template, listing define the goal, loop the choices, choose, explore, and un-choose](/assets/blog/recursion-backtracking-interview-questions-figure.webp)
*The backtracking template — choose, explore, un-choose. The same five steps solve permutations, subsets, N-Queens and Sudoku.*

In code, that template looks like this — here generating all subsets, but the skeleton is identical for almost every backtracking problem:

```
def subsets(nums):
    result, path = [], []
    def backtrack(start):
        result.append(path[:])        # record the current solution
        for i in range(start, len(nums)):
            path.append(nums[i])      # choose
            backtrack(i + 1)          # explore
            path.pop()                # un-choose (backtrack)
    backtrack(0)
    return result
```

The `path.append` → `backtrack` → `path.pop` sandwich *is* backtracking. The `pop` is the un-choose step that resets state before trying the next option, and forgetting it is the number-one backtracking bug. Once you can recognise this shape, problems that looked terrifying become “oh, it's the subsets template with a different goal condition.”

### How is backtracking different from brute force?

Brute force generates *every* candidate and then checks which are valid. Backtracking is smarter: it abandons a partial candidate the moment it can't possibly become valid — a step called **pruning**. In N-Queens, brute force would place all queens and then check; backtracking refuses to place a queen on an attacked square in the first place, cutting off entire branches of the search tree before exploring them. That pruning is the whole point — it's why backtracking can handle problems a naive brute force never could.

### Walk through solving N-Queens with backtracking.

Place queens one row at a time. For the current row, try each column; if a column isn't attacked by any already-placed queen (check the column and both diagonals), *place* the queen, *recurse* to the next row, and if that fails, *remove* the queen and try the next column. When you've placed a queen in every row, you've found a valid board. The structure is exactly choose-explore-un-choose: place, recurse, remove. The pruning — skipping attacked columns — is what keeps it tractable. If you can narrate this with the choose/explore/un-choose vocabulary, you've shown you understand the *pattern*, not just memorised one problem.

## Recursion vs iteration: how to practise, and what most people get wrong

Most candidates prepare for recursion the way they prepare for everything else: grind problems on **LeetCode** until the patterns stick. That genuinely works for building recognition — after enough subset and permutation problems, you'll spot the backtracking template instantly. But LeetCode has the same quiet blind spot it always does: it grades your *code*, in silence, and never once makes you *explain* how the recursion unwinds, or trace the call stack out loud, or answer “what's the space complexity — and why isn't it exponential?” Those are the exact questions a human interviewer asks, and they're the ones that make people freeze.

**GeeksforGeeks** and YouTube walkthroughs are great for *seeing* a recursion tree drawn out, and you should absolutely use them to build intuition. But watching someone else trace `fib(5)` is passive; doing it yourself, narrating each call and return while someone can interrupt with “wait, why did that return 2?”, is the active skill the interview actually tests. And generic **ChatGPT prompting** can quiz you, but it's still a text exchange — you type, it reads. The interview is spoken, with follow-ups, under mild pressure, while you also try to write correct code on a shared screen. That combination is its own skill.

[Greenroom](/) is built for exactly that gap. It runs **spoken** mock interviews where an AI interviewer asks you to solve a recursive or backtracking problem, then probes the way a real engineer would — “trace the call stack for me,” “what's the base case,” “can you memoize that?” — and gives feedback on how clearly you explained it, not just whether the code ran. That's the verbal muscle LeetCode, GeeksforGeeks, and a static ChatGPT prompt all skip. Pair it with our [common coding interview mistakes](/blog/common-coding-interview-mistakes) and [coding interview communication tips](/blog/coding-interview-communication-tips).

> **The core truth:** recursion questions reward people who can *narrate the unwinding* — base case, the call stack, where the work repeats — not just people who can produce working code. The code is half the answer; explaining how it runs is the half that gets offers.

## From recursion to dynamic programming

Once recursion, memoization, and backtracking click, you've quietly unlocked the door to **dynamic programming** — because top-down DP is just recursion plus memoization, and many DP problems are backtracking with the redundant work cached. The progression that builds real confidence is: master the base-case-and-recursive-case discipline, learn to draw and read recursion trees, internalise the choose/explore/un-choose template, then add memoization. Keep going with our [data structures interview questions](/blog/data-structures-interview-questions), the [Big O notation guide](/blog/big-o-notation-time-complexity-interview-questions), and the full [DSA coding interview preparation](/blog/dsa-coding-interview-preparation-india) roadmap.

## Frequently asked questions

### What is recursion in simple terms?

Recursion is when a function solves a problem by calling itself on a smaller version of the same problem, until the problem becomes small enough to answer directly. Every correct recursive function has two parts: a base case, which is the smallest input you can answer without recursing and which stops the recursion, and a recursive case, which breaks the problem into a smaller subproblem, calls itself, and combines the result. The call stack keeps track of each paused call until it is ready to finish.

### What is the difference between recursion and backtracking?

Recursion is the general technique of a function calling itself on smaller subproblems. Backtracking is a specific use of recursion where you build a solution one choice at a time and undo a choice when it leads to a dead end, then try the next option. Backtracking adds pruning, meaning it abandons a partial solution as soon as it cannot possibly become valid, which makes it far more efficient than brute force on problems like permutations, subsets, N-Queens and Sudoku.

### Why does recursion cause a stack overflow?

Each pending recursive call occupies a frame on the call stack, and the stack has a finite size. If the recursion goes too deep, because the input is very large or because the base case is missing or unreachable, the program runs out of stack space and crashes with a stack overflow. In Python this raises a RecursionError at around 1000 levels deep by default. You prevent it by ensuring the base case is reachable, converting deep recursion to iteration with an explicit stack, or using tail recursion in languages that optimise it.

### What is memoization and how does it speed up recursion?

Memoization caches the result of each subproblem the first time it is computed, so later calls with the same input return instantly from the cache instead of recomputing. For naive recursive Fibonacci, which recomputes the same values many times, memoization collapses the time complexity from O(2 to the n) down to O(n). It is the bridge from recursion to dynamic programming, because top-down dynamic programming is essentially recursion plus memoization. In Python you can add it with the functools lru_cache decorator.

### What is the time and space complexity of recursive Fibonacci?

Naive recursive Fibonacci is O(2 to the n) in time, because each call spawns two more and the recursion tree roughly doubles at every level. Its space complexity, however, is O(n), not exponential, because at any moment only one path from the root to a leaf sits on the call stack, and that path is at most n deep. Separating the number of calls, which is the time, from the maximum stack depth, which is the space, is a common follow-up that interviewers use to test depth of understanding.

### How do I get better at recursion interview questions?

Practise narrating the recursion out loud, not just writing it. Interviewers ask you to trace the call stack, name the base case, and explain why the space complexity is not exponential, so rehearse saying those answers verbally. Grinding LeetCode builds pattern recognition but grades only your code silently, and watching walkthroughs is passive. Pair them with spoken mock interviews that ask you to solve a recursive or backtracking problem and then push back with follow-ups, which is exactly what a real interviewer does.

Recursion and backtracking questions reward people who can narrate the unwinding out loud, under real follow-up questions. [Greenroom](https://usegreenroom.app/) runs spoken coding mock interviews that ask you to trace the call stack and explain your base case — with feedback on every answer. Free to start.