A candidate on LastRound AI's mock interview call last month wrote a working permutations function in under four minutes. Then the interviewer asked what would happen if she deleted the line that popped the last choice back off the path, and she couldn't answer. That gap, between writing recursive code and explaining what the call stack is doing underneath it, is exactly what recursion and backtracking interview questions are built to expose.
Most candidates can write recursion. Fewer can reason about it out loud, which is the actual skill being graded.
What a recursion question is actually checking
A recursive function is any function that calls itself, with two required parts: a base case that stops the calls, and a recursive case that reduces the problem and calls the function again. Every call gets pushed onto the call stack, a system-managed stack of frames, and each frame sits there holding its local variables until the calls below it resolve.
Picture factorial(4). It doesn't return anything until factorial(1) hits the base case and returns 1. Then factorial(2) multiplies that by 2 and returns 2. Then factorial(3) multiplies by 3, returns 6. Then factorial(4) multiplies by 4 and returns 24. Four calls stacked up before a single value came back. That stacking, not the multiplication, is what interviewers are watching for when they ask you to trace your own code line by line.
Recursion versus iteration, and why interviewers still ask about both
Any recursive solution can be rewritten as a loop with an explicit stack, and most bounded loops can be rewritten as recursion. Interviewers mostly don't care which one you default to. They care whether you can name the trade-off out loud: recursion trades memory, one stack frame per call, for code that mirrors the problem's own structure, while iteration trades that clarity for a flat, constant amount of memory.
Tree and graph problems lean recursive because the problem itself branches, so an iterative version usually means building your own explicit stack to fake what the call stack would have done for free. Straight-line problems, summing an array, reversing a string in place, lean iterative because there's nothing to branch into.
Tail recursion, and why it barely matters in Python or JavaScript
Tail recursion is when the recursive call is the very last thing a function does, with no pending work left after it returns, like accumulating a running total in a parameter instead of multiplying after the call comes back. In principle a compiler can reuse the current stack frame for a tail call instead of pushing a new one, collapsing the recursion into constant stack space. Don't count on that here, though: CPython has no tail call optimization, and neither does V8, the engine behind Node and Chrome, so a "tail recursive" solution in Python or JavaScript still grows the stack one frame per call, same as any other recursion. Scheme and a handful of functional languages do optimize it. Know the concept for the interview. Don't rely on it saving you in the language you're actually coding in.
Backtracking is recursion with three rules: choose, explore, un-choose
Backtracking is recursion with a constraint attached. At each step you choose one option from a set, recurse into the consequences of that choice, then undo the choice before trying the next one. That third step, the un-choose, is the one candidates forget, and it's usually the missing line when a backtracking solution returns wrong or duplicate answers instead of crashing outright.
The skeleton looks the same across almost every backtracking problem, whichever object you're actually building:
def backtrack(path, choices):
if is_solution(path):
record(path)
return
for choice in choices:
if not is_valid(choice, path):
continue
path.append(choice) # choose
backtrack(path, next_choices(choices, choice)) # explore
path.pop() # un-choose
Here's that same skeleton applied to subsets, one of the shortest complete examples there is:
def subsets(nums):
result = []
def backtrack(start, path):
result.append(path[:])
for i in range(start, len(nums)):
path.append(nums[i]) # choose
backtrack(i + 1, path) # explore
path.pop() # un-choose
backtrack(0, [])
return resultRun that on [1, 2, 3] and it produces all eight subsets, including the empty one, because every subset gets recorded the moment it's built, not just at the end.
Six backtracking problems that show up over and over
Six shapes cover most of what shows up in a coding round: permutations, subsets, combination sum, N-Queens, sudoku, and word search. They all reuse the choose, explore, un-choose skeleton above. What changes each time is the validity check inside the loop and the shape of the "board" you're building.
| Problem | What you're choosing | Recursion tree size |
|---|---|---|
| Permutations | Next unused element for the current slot | O(n!) |
| Subsets | Include or skip each element | O(2^n) |
| Combination sum | Reuse or move past each candidate number | O(2^target) worst case |
| N-Queens | Column for the queen in the current row | O(n!), pruned hard by the safety check |
| Sudoku solver | Digit 1-9 for the next empty cell | O(9^m), m = empty cells, pruned by row/column/box rules |
| Word search | Next grid direction (up, down, left, right) | O(4^L), L = word length |
The recursion tree size in that table is a worst-case ceiling, not what actually runs. Real backtracking code almost never visits every node, because the validity check inside the loop prunes whole branches before they're explored. N-Queens on an 8x8 board has a raw tree of 8! (40,320) orderings, but a safety check that rejects a queen the moment it shares a column, row, or diagonal with an earlier one cuts the actual work down by roughly two orders of magnitude in practice, though the exact cut depends on board size. That gap, between the theoretical tree and the pruned tree you actually walk, is worth naming out loud in an interview.
Donald Knuth used a version of this same idea, choose a queen's column, recurse, backtrack on failure, to demonstrate his Dancing Links algorithm solving N-Queens for boards up to size 18, in a paper that's still one of the clearer published descriptions of backtracking as a search strategy over an exact-cover problem, according to Knuth's "Dancing Links" paper. If N-Queens ever feels like a toy problem invented for interviews, it's worth knowing it's also real, published computer science.
When recursion blows the stack
Recursion fails a specific way: not slowly, but all at once, when the call stack runs out of room. Python raises a RecursionError once you exceed its interpreter stack limit, and other languages throw a StackOverflowError or crash the process outright. Python's own documentation is explicit that the limit exists "to prevent infinite recursion from causing an overflow of the C stack and crashing Python," and that a RecursionError fires the moment a call would exceed it.
Two separate bugs cause this, and beginners tend to treat them the same even though the fix is different. A missing or unreachable base case means the recursion never stops, so it blows the stack no matter how deep the limit is set. A correct base case on a genuinely deep input, a linked list with 50,000 nodes recursed one node at a time, will also blow the stack, because depth equals stack frames and there's a real ceiling on how many frames an interpreter will let you push. Fix the first bug by fixing your logic. Fix the second by converting to an iterative loop with an explicit stack, or restructuring the recursion so its depth isn't proportional to input size.
Recursion and backtracking interview questions candidates actually get asked
Ten questions we hear repeated across mock sessions and real interview debriefs, roughly in the order they escalate.
What's the difference between a base case and a recursive case?
The base case is the condition that stops the recursion and returns a value directly, without calling the function again. The recursive case is everything else: it reduces the problem toward the base case and calls the function again on that smaller version. Skip the base case, or write one that's never actually reachable from your inputs, and the function recurses until it hits the recursion limit or the platform's stack limit, whichever comes first.
Can you trace the call stack for factorial(4) line by line?
factorial(4) calls factorial(3), which calls factorial(2), which calls factorial(1), which hits the base case and returns 1 without calling anything further. Nothing multiplies until that point. Then the stack unwinds: factorial(2) returns 2, factorial(3) returns 6, factorial(4) returns 24. Four frames sat on the stack at once, each one paused mid-execution, waiting on the call below it to finish first.
When would you pick recursion over iteration in an actual interview?
Pick recursion when the problem's own structure is recursive, trees, graphs, divide-and-conquer, backtracking, because the code ends up mirroring the problem instead of fighting it. Pick iteration for straight-line, single-pass problems with nothing to branch into. I'd lean recursive by default on anything tree-shaped, even knowing it costs more memory, because interviewers usually care more about obvious correctness than peak efficiency.
What is tail recursion, and will it save you from a stack overflow in Python?
Tail recursion is when the recursive call is the last operation in a function, with nothing left to compute after it returns. No, it won't save you in Python. CPython doesn't implement tail call optimization, so a tail-recursive function still pushes one stack frame per call and can still hit a RecursionError on deep enough input. If you actually need to avoid the overflow, convert to a loop.
How is backtracking different from a plain recursive tree traversal?
Plain recursion just explores. Backtracking explores and then explicitly undoes the choice it made before trying the next one, which is what lets the same data structure, a list, a board, a partial path, get reused across every branch instead of copied fresh at each call. Drop the un-choose step and you'll usually still get an answer, just the wrong one, because leftover state from one branch leaks into the next.
What's the time complexity of generating all permutations of n distinct elements?
O(n!) at minimum, since there are exactly n factorial orderings to produce, and each takes O(n) work to build and copy, so runtime lands closer to O(n! · n). This is one of the few backtracking problems where pruning doesn't help much, because every permutation is technically a valid answer. You can't cut a branch early the way you can in N-Queens or sudoku.
How do you avoid counting the same combination twice in combination sum?
Pass a start index into the recursive call and only consider candidates from that index forward, never looping back to earlier numbers. That one change is the fix: without it, [2, 3] and [3, 2] both get recorded as separate answers even though a combination doesn't care about order. Sort the input first if the problem also needs you to skip duplicate values, not just duplicate orderings.
How does N-Queens decide whether a queen placement is safe?
Track which columns, row-minus-column diagonals, and row-plus-column diagonals already have a queen on them, using three sets updated on each choose and cleared on each un-choose. A new queen at (row, col) is safe only if col, row minus col, and row plus col are all still unused. That constant-time check turns a raw O(n!) search into something that actually finishes for board sizes up to around 15 on ordinary hardware.
Why does word search need a visited set, and what breaks if you forget to clear it?
Word search needs a visited marker so the same grid cell can't be reused twice inside one path, since real words don't loop back over themselves on a physical grid. Forget to un-mark the cell after backtracking out of a failed direction, and every other direction from that cell silently treats it as already used, which under-counts valid paths instead of throwing an error. We don't have a clean count of how often this exact bug shows up versus other mistakes, just that graders flag it often, likely because it fails quietly instead of crashing.
How would you turn a backtracking solution into a dynamic programming one?
Ask whether the recursive calls ever repeat the same arguments. If subsets of the same size and same remaining elements come up more than once, cache the result and you've turned backtracking into top-down dynamic programming, cutting an exponential search into something polynomial. If every call genuinely has unique arguments, the way permutations does, there's nothing to cache, and DP wouldn't help even though the shape looks similar. We cover this exact fork, and where it goes wrong, in our dynamic programming interview questions guide.
Recursion and backtracking sit inside a bigger set of recurring interview shapes. If pattern recognition under a live clock is what worries you most, our broader breakdown of coding interview patterns covers all fifteen, backtracking included, and how to spot which one a fresh problem is hiding behind. Google's L4 loop in particular leans on backtracking and DFS across its onsite rounds, which we go through problem by problem in our Google L4 interview questions guide.
What we keep seeing in LastRound AI's live mock sessions isn't candidates who can't write a recursive function. It's candidates who write one, get it working, and then freeze the second an interviewer asks them to explain why. That's a live-conversation problem more than a coding problem, and it's the specific thing LastRound AI's AI interview copilot is built to help with: it listens as the question gets read out loud and surfaces the likely pattern in real time, so you're reasoning about the choose-explore-un-choose structure out loud, not hoping the code speaks for itself.
Write the recursive function. Then close your eyes and describe, out loud, what's sitting on the call stack at the deepest point. If you can't, that's the part to drill next, maybe with one of LastRoundAI's free tools for quick practice, not twenty more LeetCode problems.
How this list was built
Worth being straight about where these questions come from, because plenty of pages in this category are not. The set was compiled from a research pass across official documentation, vendor release notes, published engineering writing and public discussion of hiring processes, then cross-checked against the current version of each technology so nothing here describes behaviour that has since changed.
What that means in practice: these are the questions the material supports as reasonable and current for this role, not a transcript of any one company's loop. We have not sat in on your interview and we are not going to claim we have. Treat the list as well-sourced preparation rather than a leaked question bank, and expect your panel to phrase things their own way.
If you spot something out of date, tell us at contact@lastroundai.com and we will fix it.
Frequently asked questions
What recursion and backtracking topics come up most often?
Interviewers concentrate on the parts that cause production incidents rather than the parts that are pleasant to learn. Expect the fundamentals to be assumed and the follow-up questions to sit one layer below what a tutorial covers.
Do I need hands-on recursion and backtracking experience to pass?
It shows quickly either way. Textbook answers hold up until the interviewer asks what you did when it broke, and that is usually the question that separates candidates. A small real project you can discuss honestly beats a longer list of familiarity claims.
Is recursion and backtracking still worth learning in 2026?
For interview purposes the question is really whether the teams you are targeting use it, which is worth checking against their actual job postings rather than general popularity rankings. Where it is in use it tends to be deeply embedded and slow to replace.
Should I memorise recursion and backtracking syntax for the interview?
Rarely worth it. Most interviewers care that you know what to reach for and why, and will not fail you for forgetting an exact flag. Being confidently wrong about behaviour costs far more than admitting you would check the documentation.
What is the most common mistake in recursion and backtracking interviews?
Answering the question that was asked and stopping there. The strongest candidates add the trade-off or the failure mode without being prompted, which is what signals real use rather than revision.