Recursion and Backtracking Questions
Recursion mechanics (base and recursive cases, tracing call stack frames, what lives on the stack versus the heap, tail calls, recursion depth limits and stack overflow diagnosis, recursion-to-iteration conversion with an explicit stack or trampoline, recursion versus iteration trade-offs) and recursion on nested data and simple divide-and-conquer (Euclid's gcd, string reversal, flattening nested lists and dictionaries lazily with generators, recursive maximum subarray). Also backtracking search over combinatorial spaces: permutations (including duplicates and the k-th permutation), subsets, combinations, combination sum, generating balanced parentheses, N-Queens (with bitmasks and symmetry), Sudoku (with minimum-remaining-values ordering), word search, palindrome partitioning, Knight's Tour and Hamiltonian paths. Covers the choose/explore/undo template, how it differs from plain DFS, state-leakage bugs, pruning, and recursion-tree complexity (O(b^d)) including call-tree counts. Memoized recursion, tree traversals, and general graph search are covered elsewhere.
You are implementing binary tree traversals in a codebase that must handle very deep trees (depth over 10,000). Decide between recursion and an iterative stack-based approach, weighing stack overflow risk, readability, maintainability, and performance, and justify the choice.
Sample Answer
Recommendation
Use the iterative traversal with an explicit stack. A tree that can be deeper than 10,000 levels is a tree whose shape you do not control, and for that shape recursion risks a crash that no test with ordinary data will find. The explicit stack costs about eight extra lines and the same O(n) time. Keep the recursive version for trees that are guaranteed shallow.
Why depth is the whole issue
A traversal visits every node once. The call stack is the region of memory where each active function call keeps its local variables and return address; one frame is added per call and removed on return. A recursive traversal uses one frame per level of the tree, so its stack use is proportional to the tree's height h (the longest root-to-leaf path), not to the node count n. For a balanced tree (one where the two sides of every node have nearly the same height) h is about log2(n), tiny: a million nodes need about 20 levels. For a degenerate tree (every node has one child, so it is really a linked list, which is what sorted-order inserts into a plain binary search tree produce) h equals n.
The call stack has a fixed size, chosen when the thread starts, while a list or std::vector on the heap (the general pool of memory for dynamically allocated objects, not to be confused with the heap data structure) grows until memory runs out. Past the limit the program fails: Python raises RecursionError, and C++ typically dies with a segmentation fault.
The three orders, and the iterative loop on a small tree
The three classic depth-first traversal orders differ only in when the current node is visited relative to its two subtrees. In-order visits the left subtree, then the node, then the right subtree (on a binary search tree this yields the values in sorted order). Pre-order visits the node first, then left, then right. Post-order visits left, then right, then the node last. The rest of this answer uses in-order.
The iterative loop keeps a list of nodes whose visit is still pending, with the nearest pending ancestor at the end. Run on this five-node tree it prints every push and pop with the stack contents:
class Node:
__slots__ = ("val", "left", "right")
def __init__(self, val, left=None, right=None):
self.val, self.left, self.right = val, left, right
def inorder_traced(root):
stack, node, order = [], root, []
while stack or node:
while node:
stack.append(node)
node = node.left
print(f"push {stack[-1].val:<2} stack={[n.val for n in stack]}")
node = stack.pop()
order.append(node.val)
print(f"pop {node.val:<2} visit {node.val} stack={[n.val for n in stack]}")
node = node.right
return order
# 4
# / \
# 2 5
# / \
# 1 3
tree = Node(4, Node(2, Node(1), Node(3)), Node(5))
print("in-order:", inorder_traced(tree))
Output:
push 4 stack=[4]
push 2 stack=[4, 2]
push 1 stack=[4, 2, 1]
pop 1 visit 1 stack=[4, 2]
pop 2 visit 2 stack=[4]
push 3 stack=[4, 3]
pop 3 visit 3 stack=[4]
pop 4 visit 4 stack=[]
push 5 stack=[5]
pop 5 visit 5 stack=[]
in-order: [1, 2, 3, 4, 5]
Read it as three moves. Walk left, pushing each node (push 4, push 2, push 1) until there is no left child. Pop the top and visit it (pop 1 visit 1), then step to its right child. If that right child is empty, the next pop returns to the parent (pop 2); if it exists, the walk-left starts again from it (push 3). The stack is exactly the list of ancestors still waiting to be visited, which is what the recursive version keeps in its call frames.
Evidence, run on a worst-case chain
A tree where every node has only a left child, 12,000 deep, in Python 3.12:
import sys
class Node:
__slots__ = ("val", "left", "right")
def __init__(self, val, left=None, right=None):
self.val, self.left, self.right = val, left, right
def inorder_recursive(root, visit):
if root is None:
return
inorder_recursive(root.left, visit)
visit(root.val)
inorder_recursive(root.right, visit)
def inorder_iterative(root, visit):
stack, node = [], root
while stack or node:
while node: # walk left as far as possible, remembering the way back
stack.append(node)
node = node.left
node = stack.pop()
visit(node.val)
node = node.right
def left_chain(depth):
root = None
for v in range(depth, 0, -1):
root = Node(v, left=root) # every node has only a left child: the worst shape
return root
if __name__ == "__main__":
depth = 12_000
tree = left_chain(depth)
print("default recursion limit:", sys.getrecursionlimit())
seen = []
try:
inorder_recursive(tree, seen.append)
print("recursive: visited", len(seen))
except RecursionError:
print("recursive: RecursionError after visiting", len(seen), "nodes")
seen = []
inorder_iterative(tree, seen.append)
print("iterative: visited", len(seen), "first/last:", seen[0], seen[-1])
balanced = Node(2, Node(1), Node(3))
out = []
inorder_iterative(balanced, out.append)
print("balanced tree order:", out)
Output:
default recursion limit: 1000
recursive: RecursionError after visiting 0 nodes
iterative: visited 12000 first/last: 12000 1
balanced tree order: [1, 2, 3]
The recursive call fails at the default limit of 1000 frames before it visits a single node (the deepest node is visited first in an in-order walk). The iterative version visits all 12,000.
Raising the limit is a fix that depends on the runtime. In this Python 3.12 container, raising the limit lets the recursive version finish at depth 12,000:
import sys
from tree import Node, inorder_recursive, left_chain
sys.setrecursionlimit(50_000)
tree = left_chain(12_000)
seen = []
inorder_recursive(tree, seen.append)
print("raised limit, depth 12000: visited", len(seen))
raised limit, depth 12000: visited 12000
In C++ there is no such setting inside the language: the stack size comes from the operating system. In this container the limit is 8192 KB and the same shape behaves as follows:
#include <cstdlib>
#include <iostream>
#include <vector>
struct Node { int val; Node* left; Node* right; };
void inorder_recursive(const Node* n, long long& visited) {
if (!n) return;
inorder_recursive(n->left, visited);
++visited;
inorder_recursive(n->right, visited);
}
long long inorder_iterative(const Node* root) {
std::vector<const Node*> stack;
const Node* node = root;
long long visited = 0;
while (!stack.empty() || node) {
while (node) { stack.push_back(node); node = node->left; }
node = stack.back(); stack.pop_back();
++visited;
node = node->right;
}
return visited;
}
int main(int argc, char** argv) {
long long depth = std::atoll(argv[1]);
std::vector<Node> pool(depth);
for (long long i = 0; i < depth; ++i)
pool[i] = {int(i), i + 1 < depth ? &pool[i + 1] : nullptr, nullptr};
std::cout << "iterative visited " << inorder_iterative(&pool[0]) << std::endl;
long long visited = 0;
inorder_recursive(&pool[0], visited);
std::cout << "recursive visited " << visited << std::endl;
}
stack limit (KB): 8192
iterative visited 10000
recursive visited 10000
depth 10000 exit code 0
iterative visited 100000
recursive visited 100000
depth 100000 exit code 0
iterative visited 10000000
Segmentation fault
depth 10000000 exit code 139
At depths 10,000 and 100,000 both versions work; at 10,000,000 the iterative version still finishes (it printed its count first) and the recursive one is killed by a segmentation fault. The Segmentation fault line in the output is not printed by the program: the program is killed by signal 11 before it can print anything, and the shell that launched it reports that signal on its error stream (so the line's position among the others can shift when output is piped). Exit code 139 is the shell's way of reporting 128 plus the signal number 11. The exact depth at which it dies depends on the frame size, the compiler flags and the stack limit, which is why a test that passes on a developer machine proves little about a production thread with a smaller stack.
Weighing the four criteria
| Criterion | Recursion | Explicit stack |
|---|---|---|
| Stack overflow risk | Proportional to height; fatal on skewed input | Heap memory, proportional to height; fails only when memory is exhausted, far later |
| Readability | Three lines that mirror the definition | Eight lines; the "walk left, remember the way back, pop" loop must be learned |
| Maintainability | Easiest to extend for pre- and post-order | In-order and pre-order are easy; post-order needs a "last visited" marker or two stacks |
| Performance | 2n + 1 calls (one per node plus one per empty child), each creating and discarding a frame | n pushes and n pops on one list; no calls beyond the loop itself. Both are O(n) |
Cost is the same order either way: n visits, and extra space proportional to the height h. The iterative version moves that space from the call stack to the heap, where it is allowed to be large.
What would change the choice
- The tree is balanced by construction (an AVL tree or a red-black tree, both binary search trees that rebalance themselves on every insert, or a B-tree, the many-children balanced tree used in databases and file systems): height is at most about 2 log2(n), so recursion is safe and clearer.
- The input is trusted and small (a config tree, an expression of a few dozen nodes): recursion is fine.
- You need O(1) extra space: Morris traversal temporarily rewires empty right pointers to climb back up, then restores them. It uses no stack but changes the tree while it runs, so it is unsafe when other threads read the tree.
- You control the stack size of the thread that runs the traversal: giving that thread a larger stack postpones the crash, it does not remove it, because a deeper tree still needs more.
Common mistakes
- Making only the traversal iterative and leaving other recursive operations (copying, comparing, printing, freeing the tree) on the same tree: they hit the same limit.
- Testing recursion only on a balanced tree.
- Writing
while stack:instead ofwhile stack or node:. The stack is empty at the start, so the loop never runs.
Running the code
docker run --rm -v "$PWD":/w -w /w python:3.12 sh -c 'python tree.py; python tree_limit.py; sh tree_cpp.sh'
tree_cpp.sh is the short script below; save the listings as tree.py (the 12,000-deep chain), tree_limit.py, tree_cpp.cpp and tree_cpp.sh. The five-node walk-through near the top is a separate listing: save it as tree_trace.py and run python tree_trace.py the same way.
g++ -O0 -o tree_cpp tree_cpp.cpp
echo "stack limit (KB): $(ulimit -s)"
for d in 10000 100000 10000000; do
./tree_cpp $d
echo "depth $d exit code $?"
done
Implement a recursive function that returns all permutations of a list of distinct integers without using library permutation helpers. Show the output for [1, 2, 3], explain how you avoid shared-state bugs, and state the time and space complexity.
Sample Answer
The idea in plain words
A permutation is an ordering of all the items. For n distinct items there are n! of them (n choices for the first slot, n-1 for the next, and so on). The backtracking idea: fill the slots from left to right; at each slot, try every item that has not been used yet, recurse to fill the remaining slots, then take the item back so the next candidate can try the same slot.
The brute-force alternative, generating all n^n sequences and discarding the ones with repeats, wastes almost all of its work. Backtracking never builds a repeat in the first place.
Approach 1: a used array
Keep path (the arrangement so far) and used[i] (whether nums[i] is already in path). A full-length path is one permutation.
Approach 2: swap in place and swap back
Treat the array itself as the state. Slots before index first are fixed. To fill slot first, swap each candidate arr[i] (for i >= first) into that slot, recurse on first + 1, then swap back. This needs no used array and no separate path list.
from itertools import permutations
from typing import List
def permutations_used(nums: List[int]) -> List[List[int]]:
result: List[List[int]] = []
path: List[int] = []
used = [False] * len(nums)
def backtrack() -> None:
if len(path) == len(nums):
result.append(path[:]) # copy: path keeps changing
return
for i in range(len(nums)):
if used[i]:
continue
used[i] = True # choose
path.append(nums[i])
backtrack() # explore
path.pop() # undo
used[i] = False
backtrack()
return result
def permutations_swap(nums: List[int]) -> List[List[int]]:
arr = nums[:] # work on a copy of the input
result: List[List[int]] = []
def backtrack(first: int) -> None:
if first == len(arr):
result.append(arr[:])
return
for i in range(first, len(arr)):
arr[first], arr[i] = arr[i], arr[first] # choose: put arr[i] at slot first
backtrack(first + 1) # explore
arr[first], arr[i] = arr[i], arr[first] # undo: swap back
backtrack(0)
return result
print(permutations_used([1, 2, 3]))
print(permutations_swap([1, 2, 3]))
for n in range(0, 7):
items = list(range(n))
expected = [list(p) for p in permutations(items)]
assert permutations_used(items) == expected
assert sorted(permutations_swap(items)) == sorted(expected)
print("checks passed")
print("empty list:", permutations_used([]), permutations_swap([]))
def leaky(nums):
result, path, used = [], [], [False] * len(nums)
def backtrack():
if len(path) == len(nums):
result.append(path) # BUG: no copy
return
for i in range(len(nums)):
if not used[i]:
used[i] = True; path.append(nums[i])
backtrack()
path.pop(); used[i] = False
backtrack()
return result
print("without copying:", leaky([1, 2, 3]))
def swap_no_undo(nums):
arr, result = nums[:], []
def backtrack(first):
if first == len(arr):
result.append(arr[:])
return
for i in range(first, len(arr)):
arr[first], arr[i] = arr[i], arr[first]
backtrack(first + 1)
# BUG: no swap back here
backtrack(0)
return result
print("swap without swapping back:", swap_no_undo([1, 2, 3]))
Output (the itertools import is only used by the check against the standard library; the solutions do not call it):
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 2, 1], [3, 1, 2]]
checks passed
empty list: [[]] [[]]
without copying: [[], [], [], [], [], []]
swap without swapping back: [[1, 2, 3], [1, 3, 2], [3, 1, 2], [3, 2, 1], [1, 2, 3], [1, 3, 2]]
Both methods find the same six permutations. For a sorted input the used version yields them in lexicographic order, meaning dictionary order: compare first items, and break ties with the second item, then the third (the check above compares it, in order, with itertools.permutations for range(n) inputs). The swap version produces [3, 2, 1] before [3, 1, 2] because swapping reorders the tail (the swap trace below shows exactly where), so compare results as sets or sorted lists, not by position.
Trace of the used version on [1, 2, 3]
This instrumented version of the used recursion prints each choose and undo, indented by depth (depth only controls the indentation); the swap version's instrumented copy follows it in the same block:
from typing import List
def permutations_used_traced(nums: List[int]) -> None:
path: List[int] = []
used = [False] * len(nums)
def backtrack(depth: int) -> None:
pad = " " * depth
if len(path) == len(nums):
print(f"{pad}full {path} -> record")
return
for i in range(len(nums)):
if used[i]:
continue
used[i] = True
path.append(nums[i])
print(f"{pad}choose {nums[i]} path={path}")
backtrack(depth + 1)
path.pop()
used[i] = False
print(f"{pad}undo {nums[i]} path={path}")
backtrack(0)
def permutations_swap_traced(nums: List[int]) -> None:
arr = nums[:]
def backtrack(first: int) -> None:
pad = " " * first
if first == len(arr):
print(f"{pad}full {arr} -> record")
return
for i in range(first, len(arr)):
arr[first], arr[i] = arr[i], arr[first]
print(f"{pad}swap slots {first},{i} arr={arr}")
backtrack(first + 1)
arr[first], arr[i] = arr[i], arr[first]
print(f"{pad}swap back {first},{i} arr={arr}")
backtrack(0)
permutations_used_traced([1, 2, 3])
print("--- swap version ---")
permutations_swap_traced([1, 2, 3])
The first half of its output is the used trace:
choose 1 path=[1]
choose 2 path=[1, 2]
choose 3 path=[1, 2, 3]
full [1, 2, 3] -> record
undo 3 path=[1, 2]
undo 2 path=[1]
choose 3 path=[1, 3]
choose 2 path=[1, 3, 2]
full [1, 3, 2] -> record
undo 2 path=[1, 3]
undo 3 path=[1]
undo 1 path=[]
choose 2 path=[2]
choose 1 path=[2, 1]
choose 3 path=[2, 1, 3]
full [2, 1, 3] -> record
undo 3 path=[2, 1]
undo 1 path=[2]
choose 3 path=[2, 3]
choose 1 path=[2, 3, 1]
full [2, 3, 1] -> record
undo 1 path=[2, 3]
undo 3 path=[2]
undo 2 path=[]
choose 3 path=[3]
choose 1 path=[3, 1]
choose 2 path=[3, 1, 2]
full [3, 1, 2] -> record
undo 2 path=[3, 1]
undo 1 path=[3]
choose 2 path=[3, 2]
choose 1 path=[3, 2, 1]
full [3, 2, 1] -> record
undo 1 path=[3, 2]
undo 2 path=[3]
undo 3 path=[]
Read it as: after choose 1, the slots 2 and 3 are filled by every arrangement of {2, 3}; undo 1 returns path to empty so the first slot can try 2.
Trace of the swap version on [1, 2, 3]
The second half of the same program's output, after the --- swap version --- line. Each line shows the whole array arr; indentation equals first, the number of slots already fixed:
swap slots 0,0 arr=[1, 2, 3]
swap slots 1,1 arr=[1, 2, 3]
swap slots 2,2 arr=[1, 2, 3]
full [1, 2, 3] -> record
swap back 2,2 arr=[1, 2, 3]
swap back 1,1 arr=[1, 2, 3]
swap slots 1,2 arr=[1, 3, 2]
swap slots 2,2 arr=[1, 3, 2]
full [1, 3, 2] -> record
swap back 2,2 arr=[1, 3, 2]
swap back 1,2 arr=[1, 2, 3]
swap back 0,0 arr=[1, 2, 3]
swap slots 0,1 arr=[2, 1, 3]
swap slots 1,1 arr=[2, 1, 3]
swap slots 2,2 arr=[2, 1, 3]
full [2, 1, 3] -> record
swap back 2,2 arr=[2, 1, 3]
swap back 1,1 arr=[2, 1, 3]
swap slots 1,2 arr=[2, 3, 1]
swap slots 2,2 arr=[2, 3, 1]
full [2, 3, 1] -> record
swap back 2,2 arr=[2, 3, 1]
swap back 1,2 arr=[2, 1, 3]
swap back 0,1 arr=[1, 2, 3]
swap slots 0,2 arr=[3, 2, 1]
swap slots 1,1 arr=[3, 2, 1]
swap slots 2,2 arr=[3, 2, 1]
full [3, 2, 1] -> record
swap back 2,2 arr=[3, 2, 1]
swap back 1,1 arr=[3, 2, 1]
swap slots 1,2 arr=[3, 1, 2]
swap slots 2,2 arr=[3, 1, 2]
full [3, 1, 2] -> record
swap back 2,2 arr=[3, 1, 2]
swap back 1,2 arr=[3, 2, 1]
swap back 0,2 arr=[1, 2, 3]
Read it as: at first = 0, swapping slot 0 with slot 2 turns [1, 2, 3] into [3, 2, 1], so the free tail is now [2, 1] and its first arrangement [3, 2, 1] is recorded before the swap at slots 1,2 produces [3, 1, 2]. That is why [3, 2, 1] precedes [3, 1, 2]. Each swap back line restores the array to what it was before the matching swap, so the next candidate starts from a clean state.
How shared-state bugs are avoided
- Copy on record:
path[:]orarr[:]stores a snapshot. Thewithout copyingline of the output shows what happens without it: six entries that are all the same (now empty) list. - Symmetric undo: every
choosehas an exact reverse right after the recursive call (path.pop()plusused[i] = False; the second swap). If one half is missing, later branches see leftovers. - The input is not mutated: the swap version copies
numsfirst, so the caller's list is unchanged.
Complexity
- Time: there are n! permutations, each copied in O(n) when recorded, so O(n * n!) just for the output. The search tree (every call, partial and full) has about e * n! nodes in total, where e is the constant 2.718... . At depth j (j slots filled) there are n!/(n-j)! nodes: choices for the first slot times choices for the second, and so on. For n = 3 the depths 0, 1, 2, 3 have 1, 3, 6, 6 nodes, which sum to 16, and 16 / 3! = 2.67. That ratio is already near e and climbs toward it: adding n!/(n-j)! for j = 0 to 7 gives 13700 nodes for n = 7, and 13700 / 7! = 2.7183. So the whole tree is only about 2.7 times the number of leaves. The
usedversion scans n slots at each node, so it is also O(n * n!) overall. The swap version does O(1) work per child (no scan), also O(n * n!) because of the copies. - Space: O(n) auxiliary (recursion depth n, plus
pathandused), not counting the output, which is n * n! numbers. If the caller does not need every permutation at once, a generator that yields each one keeps memory at O(n).
Edge cases and common mistakes
- Empty list returns
[[]](one permutation, the empty one); a single item returns[[x]]. - With duplicate values both routines emit repeated permutations. For the
usedversion, sort the input and skipnums[i]when it equalsnums[i - 1]andused[i - 1]is false. That sorted-neighbour rule does not carry over to the swap version, because swaps move values around and equal values stop being neighbours; there, keep a set of the values already tried in the current slot and skip any repeat. - Using
used = []as a list of values and testingx in usedmakes each check O(n); a boolean array is O(1). - Forgetting to copy (the
without copyingline) or forgetting to swap back (theswap without swapping backline, which lists[1, 2, 3]and[1, 3, 2]twice and never produces[2, 1, 3]or[2, 3, 1]).
Running the code
python3.12 permutations_backtracking.py
Save the program above as permutations_backtracking.py. No packages are needed (standard library only).
Implement the Euclidean algorithm recursively to compute gcd(a, b). Explain the base case, handle zero and negative inputs, and analyze the running time. Example: gcd(48, 18) is 6.
Sample Answer
The idea
The greatest common divisor (gcd) of two integers is the largest integer that divides both. Euclid's insight: any number that divides both a and b also divides the remainder of a divided by b, and the other way round, so gcd(a, b) equals gcd(b, a mod b). The pair gets smaller each step while the answer stays the same. When the second number reaches 0, the first number is the answer, because every number divides 0.
For gcd(48, 18): 48 mod 18 = 12, then 18 mod 12 = 6, then 12 mod 6 = 0, so the answer is 6.
The code
def gcd(a: int, b: int) -> int:
"""Greatest common divisor by Euclid's algorithm. gcd(0, 0) is defined as 0."""
a, b = abs(a), abs(b) # gcd ignores signs; Python's % on negatives is easy to misread
return _gcd(a, b)
def _gcd(a: int, b: int) -> int:
if b == 0: # base case: nothing left to divide by
return a
return _gcd(b, a % b) # (a, b) and (b, a mod b) have the same common divisors
print(gcd(48, 18))
print(gcd(-48, 18), gcd(48, -18), gcd(0, 5), gcd(5, 0), gcd(0, 0), gcd(7, 13))
Output:
6
6 6 5 5 0 1
Trace for gcd(48, 18)
def gcd_traced(a, b, depth=0):
print(f"{' ' * depth}gcd({a}, {b}) -> {a} % {b} = {a % b if b else '-'}")
if b == 0:
return a
return gcd_traced(b, a % b, depth + 1)
print(gcd_traced(48, 18))
Output:
gcd(48, 18) -> 48 % 18 = 12
gcd(18, 12) -> 18 % 12 = 6
gcd(12, 6) -> 12 % 6 = 0
gcd(6, 0) -> 6 % 0 = -
6
Each line is one call, indented by depth. The recursive step is the tail of the function (its last action): the result of the inner call is returned unchanged, with nothing left to do afterwards.
Base case, zero and negative inputs
- Base case:
b == 0returnsa. Without it the next step would computea % 0and raiseZeroDivisionError. - Why it terminates:
a % bis always smaller thanband never negative when both are non-negative, so the second argument strictly shrinks and must hit 0. - Zero:
gcd(0, 5)takes one step togcd(5, 0)and returns 5;gcd(5, 0)returns 5 at once;gcd(0, 0)returns 0 by convention (there is no greatest divisor, since every integer divides 0). - Negatives: the public function takes
absof both arguments first. gcd ignores signs, and the remainder operator differs between languages: in Python-48 % 18is 6 (the sign follows the divisor), while in Java or C it is -12. Without theabs,gcd(48, -18)returns -6 in Python: 48 % -18 is -6, the next call isgcd(-18, -6), and the chain ends on -6.
Running time
Each call does one remainder, so the cost is the number of calls. The key fact: every two steps, the first number at least halves. Write the pair as (a, b) with remainder r = a mod b. If b is at most half of a, then r < b <= a/2. If b is more than half of a, then the quotient is 1 and r = a - b < a/2. Either way r is below a/2, and after two calls the pair is (r, ...) with r as its first number. For gcd(48, 18) the first numbers are 48, 18, 12, 6: after two steps 48 has become 12, which is below 24. Halving at least every two steps means at most 2 log2(min(a, b)) + 3 calls, where log2 is the logarithm base 2 (how many times a number can be halved before reaching 1). The added 3 is a small constant for the first and last calls, which matters only for tiny inputs: gcd(1, 399) takes 3 calls although log2(1) = 0, and the last line of output below shows 3.0 as the largest excess of the call count over 2 log2(min(a, b)) across every pair below 400.
The slowest inputs are consecutive Fibonacci numbers (1, 1, 2, 3, 5, 8, 13, ..., each the sum of the two before it). In each step the quotient a // b is 1, the smallest possible, so the step only subtracts b once, which removes the least it can. The last block of output below shows it on (89, 55): every line has quotient 1 until the final step. The ratio of consecutive Fibonacci numbers tends to the golden ratio 1.618, so each call shrinks the numbers by only that factor, and the number of calls for a number near 2^63 is about 63 / log2(1.618) = 63 x 1.4404, which is where the constant 1.44 comes from.
import math
import random
def calls(a, b):
n = 1
while b:
a, b = b, a % b
n += 1
return n
fib = [1, 1]
while len(fib) < 92:
fib.append(fib[-1] + fib[-2])
for k in (10, 20, 40, 60, 90):
a, b = fib[k + 1], fib[k]
print(f"gcd({a}, {b}): {calls(a, b)} calls")
random.seed(5)
worst = 0
for _ in range(100000):
a, b = random.randrange(1, 2**63), random.randrange(1, 2**63)
worst = max(worst, calls(a, b))
print("largest call count over 100000 random 63-bit pairs:", worst)
# why Fibonacci pairs are slowest: every quotient is 1, and consecutive terms differ by the golden ratio
a, b = 89, 55
while b:
print(f"{a} = {a // b} x {b} + {a % b}")
a, b = b, a % b
phi = (1 + 5 ** 0.5) / 2
print(f"ratio of consecutive Fibonacci numbers: {fib[91] / fib[90]:.6f}, 1 / log2(ratio) = {1 / math.log2(phi):.4f}")
print(f"1.4404 x 63 = {1.4404 * 63:.1f}")
# the bound 2 x log2(min) + 3 on small inputs, where the constant matters
excess = max(calls(a, b) - 2 * math.log2(min(a, b)) for a in range(1, 400) for b in range(1, 400))
print(f"largest (calls - 2 x log2(min)) over all pairs below 400: {excess:.1f}")
Output:
gcd(144, 89): 11 calls
gcd(17711, 10946): 21 calls
gcd(267914296, 165580141): 41 calls
gcd(4052739537881, 2504730781961): 61 calls
gcd(7540113804746346429, 4660046610375530309): 91 calls
largest call count over 100000 random 63-bit pairs: 59
89 = 1 x 55 + 34
55 = 1 x 34 + 21
34 = 1 x 21 + 13
21 = 1 x 13 + 8
13 = 1 x 8 + 5
8 = 1 x 5 + 3
5 = 1 x 3 + 2
3 = 1 x 2 + 1
2 = 2 x 1 + 0
ratio of consecutive Fibonacci numbers: 1.618034, 1 / log2(ratio) = 1.4404
1.4404 x 63 = 90.7
largest (calls - 2 x log2(min)) over all pairs below 400: 3.0
For a 63-bit Fibonacci pair the code needs 91 calls, in line with the 1.4404 x 63 = 90.7 printed in the last line; random 63-bit pairs needed at most 59 in 100,000 trials. So the time is O(log min(a, b)) calls, each a constant-time remainder on machine-size integers. (Python integers are arbitrary precision, so for huge numbers each remainder costs more.)
Space and recursion depth
The recursion depth equals the number of calls, so space is O(log min(a, b)) stack frames. For 64-bit values that is under a hundred frames. Python's default limit is 1000 frames, and a Fibonacci pair of about 700 bits (consecutive Fibonacci numbers near the 1,000th are about 700 bits long and need about 1,000 calls) does exceed it: the recursive version raises RecursionError there, so for arbitrarily large integers write the loop instead: while b: a, b = b, a % b, which uses O(1) space.
Edge cases and common mistakes
- Forgetting the base case, or writing
if a == 0in a way that never reaches it. - Calling
gcd(a % b, b)instead ofgcd(b, a % b): the order of arguments matters for termination. - Returning a negative gcd for negative input.
- Treating
gcd(0, 0)as an error; most libraries return 0 (Python'smath.gcd(0, 0)is 0). - Assuming a <= b is required: if a < b the first call simply swaps them (
gcd(18, 48)goes togcd(48, 18)).
Follow-ups
- The least common multiple:
abs(a * b) // gcd(a, b), dividing before multiplying in fixed-width languages to avoid overflow. - gcd of a list: fold the function across the list.
- Extended Euclid: also return x and y with a x + b y = gcd, the basis of modular inverses.
Running the code
Python 3.12, standard library only.
python3 gcd.py ; python3 gcd_trace.py ; python3 gcd_steps.py (the three listings)
Write factorial(n) twice in Python, once recursively and once iteratively. Compare time and space for both, and explain whether tail-call optimization would change the recursive version's space and why Python does not do it.
Sample Answer
The idea
The factorial of n (written n!) is the product 1 x 2 x ... x n, with 0! = 1. It can be defined by itself: n! = n x (n-1)!, with 1 (or 0) as the stopping point. That definition is the recursive version. A loop multiplying 2, 3, ..., n into a running product is the iterative version. Both compute the same number with the same n - 1 multiplications; what differs is how much stack they use. The call stack is the fixed-size region of memory that holds one stack frame (a block with that call's arguments, local variables and return point) for every call that has started but not finished. The recursive version keeps one frame alive per pending multiplication; the loop keeps none.
A third form carries the running product in a parameter called an accumulator: factorial_tail(n, acc) multiplies as it goes down, so nothing is left to do when the inner call returns. The listing below includes it.
The code
import math
import sys
def factorial_recursive(n: int) -> int:
if n < 0:
raise ValueError("factorial is undefined for negative numbers")
if n <= 1: # base case: 0! = 1! = 1
return 1
return n * factorial_recursive(n - 1)
def factorial_iterative(n: int) -> int:
if n < 0:
raise ValueError("factorial is undefined for negative numbers")
result = 1
for k in range(2, n + 1):
result *= k
return result
def factorial_tail(n: int, acc: int = 1) -> int:
"""Tail-recursive form: the recursive call is the last thing done, and the product rides in acc."""
if n < 0:
raise ValueError("factorial is undefined for negative numbers")
if n <= 1:
return acc
return factorial_tail(n - 1, acc * n)
for n in (0, 1, 5, 20):
assert factorial_recursive(n) == factorial_iterative(n) == factorial_tail(n) == math.factorial(n)
print(factorial_recursive(5), factorial_iterative(5), factorial_tail(5), factorial_recursive(20))
print("recursion limit:", sys.getrecursionlimit())
for fn in (factorial_recursive, factorial_tail, factorial_iterative):
for n in (900, 1500):
try:
fn(n)
print(f"{fn.__name__}({n}): ok")
except RecursionError:
print(f"{fn.__name__}({n}): RecursionError")
Output:
120 120 120 2432902008176640000
recursion limit: 1000
factorial_recursive(900): ok
factorial_recursive(1500): RecursionError
factorial_tail(900): ok
factorial_tail(1500): RecursionError
factorial_iterative(900): ok
factorial_iterative(1500): ok
factorial_tail is the tail-recursive form: it carries the running product in acc, so the recursive call is the very last thing the function does. factorial_recursive is not tail-recursive, because after the inner call returns it still has to multiply by n.
Time and space
max_depth = 0
def factorial_counted(n, depth=1):
global max_depth
max_depth = max(max_depth, depth)
if n <= 1:
return 1
return n * factorial_counted(n - 1, depth + 1)
for n in (5, 50, 500):
max_depth = 0
value = factorial_counted(n)
print(f"n={n}: deepest frame count={max_depth}, result has {value.bit_length()} bits")
Output:
n=5: deepest frame count=5, result has 7 bits
n=50: deepest frame count=50, result has 215 bits
n=500: deepest frame count=500, result has 3768 bits
The output shows the call depth equals n (the frames alive at the deepest point) and how big the result gets: a 500! needs 3,768 bits. bit_length() returns how many binary digits a number needs.
| Recursive | Iterative | |
|---|---|---|
| Multiplications | n - 1 | n - 1 |
| Time | O(n) multiplications | O(n) multiplications |
| Extra stack | O(n) frames | O(1) |
| Result size | O(n log n) bits | O(n log n) bits |
The result size in the table has a short reason: n! is at most n^n (n factors, each at most n), and a number of at most n^n needs at most floor(n log2 n) + 1 bits (the + 1 only matters for tiny n: 1! = 1 needs one bit while n log2 n is 0). The bound is loose: by Stirling's approximation n! has about n log2 n - 1.44 n bits (plus a small logarithmic term), so the bound overshoots by an amount that grows in proportion to n, and the ratio of actual bits to n log2 n climbs toward 1 as n grows (0.60, 0.76 and 0.84 for the three values of n in the listing below, which prints both quantities):
import math
for n in (5, 50, 500):
bits = math.factorial(n).bit_length()
print(f"n={n}: {n}! has {bits} bits; n * log2(n) = {n * math.log2(n):.0f}")
Output:
n=5: 5! has 7 bits; n * log2(n) = 12
n=50: 50! has 215 bits; n * log2(n) = 282
n=500: 500! has 3768 bits; n * log2(n) = 4483
Python integers are arbitrary precision (they grow as large as memory allows instead of overflowing at 64 bits), so a multiplication is not constant time once the product is large: each step multiplies a big number by a small one, which costs time proportional to the number's length. Counting multiplications, which is the usual interview answer, both versions are O(n), and both must hold the same result of O(n log n) bits. The recursive version also holds n stack frames at once, and CPython allows 1000 by default, which is why factorial_recursive(1500) raises RecursionError while factorial_iterative(1500) returns.
Would tail-call optimization change the space?
Tail-call optimization (TCO) means that when a function's last action is a call, the runtime reuses the current stack frame instead of adding another, so the recursion runs in constant stack space. For factorial_tail that would change the space from O(n) to O(1); for factorial_recursive it would not, because the multiplication happens after the call returns, so the frame cannot be dropped. To benefit, you must first rewrite to the accumulator form, as factorial_tail does.
Why Python does not do it
CPython never reuses the frame for a tail call: factorial_tail(1500) raises RecursionError in the output just like the plain version. Python's creator explained the decision in a 2009 blog post: eliminating tail calls removes frames from tracebacks (the list of active calls Python prints when an error is raised), which makes debugging harder; he also objected that code written to rely on it would break on implementations without it, and that rebinding names at run time makes it impossible to know at compile time that a call is a self-call. His recommended alternative is to write the loop. Raising the limit with sys.setrecursionlimit only moves the wall, and a very high limit can crash the interpreter, so a loop (or math.factorial) is the real answer for large n. Scheme (a Lisp-family language) requires TCO by specification; compilers for C-family languages may do it as an optimisation but are not required to.
Edge cases and common mistakes
- n = 0 and n = 1 both return 1; a base case of only
n == 0works but makes one more call. - Negative input has no factorial. The code raises
ValueError, because then <= 1base case would otherwise quietly return 1. - A base case of
n == 1alone, without the negative-input check, makesfactorial(0)recurse through -1, -2, ... untilRecursionError; with the check in the listing it raisesValueErrorat -1 instead. - Believing the accumulator form is automatically O(1) in Python: it is not.
- Floats:
factorial_recursive(5.0)andfactorial_tail(5.0)return120.0by accident, whilefactorial_iterative(5.0)raisesTypeErrorbecauserangeneeds integers. Reject non-integers up front so all versions behave the same.
Follow-ups
- Compute n! mod m for huge n: reduce after each multiplication so numbers stay small.
- Memoise factorials for many queries: one table of prefix products answers each query in O(1).
- Recursion to iteration in general: the explicit stack, or the trampoline pattern (a loop that repeatedly calls a function that returns the next function to call, instead of letting each call nest).
Running the code
Python 3.12, standard library only.
python3 factorial.py ; python3 factorial_depth.py ; python3 factorial_bits.py (the three listings)
Implement backtracking in Python for the Combination Sum variant where the candidate list may contain duplicates and each number may be used at most once: return unique combinations that reach the target. Explain how you avoid duplicate combinations.
Sample Answer
The idea in plain words
We need every distinct combination of candidates that adds up to target, using each list entry at most once, where the list can contain repeated values such as [1, 1, 2]. The input is treated as positive integers.
Two ideas solve it. First, sort the list so equal values are neighbours. Second, in the loop that chooses the next element, skip a value when it equals the value just before it at the same loop level. That skip is what removes duplicate combinations. Choosing the first 1 or the second 1 as the starting element would grow the same set of combinations, so only the first of the equal values is allowed to start a branch at that level. A deeper level can still use the second 1, which is how [1, 1, 6] is found.
Brute force and why it is not enough
Trying every subset of the n entries and collecting the sums that match costs O(n * 2^n), and then a set is needed to drop repeats such as [1, 2, 5] built from either 1. Backtracking with a running remainder cuts a branch as soon as the remainder is exceeded, and the duplicate rule avoids building repeats at all.
Approach, step by step
- Sort
candidates. backtrack(start, remaining)chooses from indicesstartonwards. Whenremaining == 0, record a copy ofpath.- For each index
ifromstart: ifi > startandnums[i] == nums[i-1], skip it. Otherwise, ifnums[i] > remaining,break(the list is sorted, so everything after is also too large). Otherwise choose it, recurse withstart = i + 1so the same entry cannot be reused, and undo.
The condition i > start (not i > 0) matters. It means "this is not the first option at this level", so a value may repeat on a deeper level, where start has moved on.
Code
import random
from itertools import combinations
from typing import List
def combination_sum_once(candidates: List[int], target: int) -> List[List[int]]:
nums = sorted(candidates) # equal values become neighbours
results: List[List[int]] = []
path: List[int] = []
def backtrack(start: int, remaining: int) -> None:
if remaining == 0:
results.append(path[:])
return
for i in range(start, len(nums)):
if i > start and nums[i] == nums[i - 1]:
continue # same value already tried at this position
if nums[i] > remaining:
break # sorted, so every later value is too big as well
path.append(nums[i])
backtrack(i + 1, remaining - nums[i]) # i + 1: each element used at most once
path.pop()
backtrack(0, target)
return results
def brute_force(candidates: List[int], target: int) -> List[List[int]]:
found = set()
for r in range(len(candidates) + 1):
for chosen in combinations(sorted(candidates), r):
if sum(chosen) == target:
found.add(chosen)
return sorted(list(c) for c in found)
print(combination_sum_once([10, 1, 2, 7, 6, 1, 5], 8))
print(combination_sum_once([2, 5, 2, 1, 2], 5))
print(combination_sum_once([], 0), combination_sum_once([3], 5), combination_sum_once([1, 1, 1], 2))
random.seed(11)
for _ in range(500):
cands = [random.randint(1, 6) for _ in range(random.randint(0, 9))]
target = random.randint(1, 15)
got = combination_sum_once(cands, target)
assert sorted(got) == brute_force(cands, target)
assert len(got) == len({tuple(c) for c in got})
print("matches brute force over index subsets on 500 random inputs, with no repeated combination")
Output:
[[1, 1, 6], [1, 2, 5], [1, 7], [2, 6]]
[[1, 2, 2], [5]]
[[]] [] [[1, 1]]
matches brute force over index subsets on 500 random inputs, with no repeated combination
The check compares against a brute force over all index subsets, for 500 seeded random inputs of up to 9 values from 1 to 6, and asserts that no combination appears twice. Empty input with target 0 returns [[]] (the empty combination sums to 0), and an unreachable target returns [].
Worked trace
The instrumented run below uses [10, 1, 2, 7, 6, 1, 5] with target 8. The skip line shows the duplicate rule firing at the top level (the second 1), and the break lines show the size pruning. Indentation is the depth.
def combination_sum_traced(candidates, target):
nums = sorted(candidates)
results, path = [], []
print("sorted:", nums, "target:", target)
def backtrack(start, remaining):
pad = " " * len(path)
if remaining == 0:
results.append(path[:])
print(f"{pad}found {path}")
return
for i in range(start, len(nums)):
if i > start and nums[i] == nums[i - 1]:
print(f"{pad}skip index {i} (value {nums[i]}): same as index {i - 1} at this level")
continue
if nums[i] > remaining:
print(f"{pad}break at index {i} (value {nums[i]} > remaining {remaining})")
break
path.append(nums[i])
print(f"{pad}take index {i} (value {nums[i]}) -> {path}, remaining {remaining - nums[i]}")
backtrack(i + 1, remaining - nums[i])
path.pop()
backtrack(0, target)
return results
print(combination_sum_traced([10, 1, 2, 7, 6, 1, 5], 8))
Output:
sorted: [1, 1, 2, 5, 6, 7, 10] target: 8
take index 0 (value 1) -> [1], remaining 7
take index 1 (value 1) -> [1, 1], remaining 6
take index 2 (value 2) -> [1, 1, 2], remaining 4
break at index 3 (value 5 > remaining 4)
take index 3 (value 5) -> [1, 1, 5], remaining 1
break at index 4 (value 6 > remaining 1)
take index 4 (value 6) -> [1, 1, 6], remaining 0
found [1, 1, 6]
break at index 5 (value 7 > remaining 6)
take index 2 (value 2) -> [1, 2], remaining 5
take index 3 (value 5) -> [1, 2, 5], remaining 0
found [1, 2, 5]
break at index 4 (value 6 > remaining 5)
take index 3 (value 5) -> [1, 5], remaining 2
break at index 4 (value 6 > remaining 2)
take index 4 (value 6) -> [1, 6], remaining 1
break at index 5 (value 7 > remaining 1)
take index 5 (value 7) -> [1, 7], remaining 0
found [1, 7]
break at index 6 (value 10 > remaining 7)
skip index 1 (value 1): same as index 0 at this level
take index 2 (value 2) -> [2], remaining 6
take index 3 (value 5) -> [2, 5], remaining 1
break at index 4 (value 6 > remaining 1)
take index 4 (value 6) -> [2, 6], remaining 0
found [2, 6]
break at index 5 (value 7 > remaining 6)
take index 3 (value 5) -> [5], remaining 3
break at index 4 (value 6 > remaining 3)
take index 4 (value 6) -> [6], remaining 2
break at index 5 (value 7 > remaining 2)
take index 5 (value 7) -> [7], remaining 1
break at index 6 (value 10 > remaining 1)
break at index 6 (value 10 > remaining 8)
[[1, 1, 6], [1, 2, 5], [1, 7], [2, 6]]
The combination [1, 1, 6] is still found, because the second 1 is allowed at depth 2, where start is already past the first one.
Complexity
The search tree has at most 2^n nodes (each element is taken or not), and each recorded combination costs O(n) to copy, so the worst case is O(n * 2^n) plus O(n log n) for the sort. The early break and the duplicate skip cut work but do not change that bound: on the example above the traced search makes 17 backtrack calls where the 7 entries have 2^7 = 128 subsets. Space is O(n) for path and the recursion depth, plus the output.
Edge cases and common mistakes
- Skipping with
i > 0instead ofi > start. That version loses[1, 1, 6]since the second1is skipped even where the first is already in the path. - Not sorting. Equal values need not be neighbours, so the neighbour comparison misses repeats (the unsorted list
[1, 3, 1, 3]with target 4 returns four combinations instead of one), and thebreakabandons values that would still fit ([5, 2]with target 2 returns[]). - Recursing with
iinstead ofi + 1, which allows an entry to be reused (that is the original Combination Sum, a different problem). - Trusting the prune
nums[i] > remainingbeyond positive input. On the sorted list every later value is at least as large, so none of them can fit, which is why the sort is what makesbreaksafe. Negative values defeat the prune itself:[-2, -3, 1]with target -5 returns[]although[-3, -2]qualifies. Zeros leave the prune valid, but target 0 then returns[[]]and misses[0]and[0, 0], because the search stops as soon asremaining == 0. - Appending
pathitself rather than a copy, so every result shows the final state.
Running the code
python3.12 combination_sum_once.py
python3.12 combination_sum_once_trace.py
Standard library only.
Unlock Full Question Bank
Get access to all 33 Recursion and Backtracking interview questions and detailed answers.
Sign in to ContinueJoin thousands of developers preparing for their dream job.