You're in a long queue and someone asks: "what's your position?" You don't count 40 heads. You tap the person ahead: "what's YOUR position?" They tap the person ahead of them. The question ripples to the front, where someone says "I'm first" — and the answers ripple back, each person adding one.
That is recursion, complete: a problem answered in terms of a smaller copy of itself, a front-of-queue case that answers without asking, and answers assembling on the way back. This lesson makes the machinery visible — the call stack — then upgrades recursion into backtracking: recursion that explores choices and cleans up after every guess.
The two-part contract
Every correct recursive function honours two clauses:
- A base case — an input answered directly, no recursive call. The person at the front of the queue.
- Progress — every recursive call moves strictly toward that base case: smaller n, shorter list, fewer choices left.
def factorial(n):
if n <= 1: # base case: answered directly
return 1
return n * factorial(n - 1) # progress: n shrinks by 1
print(factorial(4))Result
24
Break either clause and the calls never stop — Python kills the run at ~1000 frames with RecursionError. Base case + guaranteed progress: check these two FIRST, in your code and in anyone else's.
The machinery: watch the call stack
Nothing magical happens at a recursive call. The current function pauses; a new frame — with its own copy of the local variables — is pushed onto the call stack; when it returns, the paused frame resumes exactly where it stopped. At factorial(4)'s deepest moment, four frames are alive, none finished. Each holds its own n, which is why the multiplications later resolve correctly, in reverse order.
Two consequences you already know pieces of: the call stack is a real stack (most recent call finishes first — LIFO), and those alive frames are memory — recursion costs O(depth) space even when it allocates nothing.
Code after the call is not dead
Predict the output before reading on — this exact shape appears in written rounds constantly:
def fun(n):
if n == 0:
return
print("down", n)
fun(n - 1)
print("up ", n) # what happens to THIS line?
fun(3)Result
down 3 down 2 down 1 up 1 up 2 up 3
The second print is deferred, not skipped: each paused frame resumes after its call returns, in reverse order — so "up" prints 1, 2, 3. Everything elegant about postorder work on trees — computing from children upward — is this one mechanism.
How to think recursively (without tracing)
Tracing four frames is educational. Tracing forty is impossible — and unnecessary. The working method is the leap of faith: assume the recursive call returns the correct answer for its smaller input, and ask only — how do I build my answer from that?
For factorial: "IF factorial(n−1) is correct, then n × that is correct for n." Add a correct base case and you have a proof by induction — two things verified, not forty frames. This is the same discipline the tree lessons drilled: state the base case, state the one-step assembly, trust the middle.
Backtracking: choose, explore, un-choose
Now point recursion at a new kind of problem: choices. Generate all subsets of [1, 2, 3]. No formula produces them; you must explore: for each element, try excluding it, and try including it. The possibilities form a tree of decisions:
def subsets(nums):
out, path = [], [] # ONE shared path for all branches
def explore(i):
if i == len(nums): # every element decided
out.append(path[:]) # snapshot (copy!) the current path
return
explore(i + 1) # choice A: exclude nums[i]
path.append(nums[i]) # CHOOSE
explore(i + 1) # choice B: include nums[i] - EXPLORE
path.pop() # UN-CHOOSE: the backtrack
explore(0)
return out
print(subsets([1, 2]))Result
[[], [2], [1], [1, 2]]
The template is three beats — choose (mutate the shared path), explore (recurse), un-choose (undo the mutation) — and the counting check confirms it: 2 elements × 2 choices each = 2² = 4 subsets ✓. For n elements, 2ⁿ; permutations (order matters) give n!. These counts tell you when exhaustive search is even feasible: 2²⁰ ≈ 10 lakh, fine; 20! — never.
Dry run: subsets of [1, 2]
explore(0) path=[]
explore(1) exclude 1 path=[]
explore(2) -> record [] out=[[]]
choose 2 path=[2]
explore(2) -> record [2] out=[[], [2]]
un-choose 2 path=[] <- restored!
choose 1 path=[1]
explore(1) exclude 2 path=[1]
explore(2) -> record [1] out=[[], [2], [1]]
choose 2 path=[1, 2]
explore(2) -> record [1, 2] out=[[], [2], [1], [1, 2]]
un-choose 2 path=[1]
un-choose 1 path=[] <- clean exitWatch the two marked lines: each un-choose returns path to exactly the state its caller left it in. Every branch starts clean because every branch cleans up.
Why does the undo matter so much?
Delete the path.pop() mentally and re-run the dry run. After recording [2], path stays [2]; then choose 1 makes [2, 1]; the outputs turn into nonsense — branches contaminate each other, because they all share ONE path object.
And its sibling bug: appending path instead of the snapshot path[:]. Then out holds four references to the SAME list, which ends empty — all your answers mutate into one. These two — the missing pop and the missing copy — are THE backtracking bugs, and interviewers probe both deliberately. Choose, explore, un-choose: the undo is what the word "backtrack" means.
The disease to remember: repeated subproblems
One more experience before leaving this lesson, because the next two lessons grow out of it. Write the naive Fibonacci:
def fib(n):
if n <= 1:
return n
return fib(n - 1) + fib(n - 2)
# fib(35): ~3 crore calls - seconds of waiting
# fib(50): ~4,000 crore calls - hoursDraw fib(5)'s call tree and the disease is visible: fib(3) computed twice, fib(2) three times — the tree doubles per level, O(2ⁿ), recomputing identical subproblems. The recursion is CORRECT; it just has no memory.
Hold this exact pain. Recursion that re-asks the same question is the entry ticket to dynamic programming — lesson 7 cures fib with three added lines and collapses 2ⁿ to n.
Pruning: refusing doomed branches
Backtracking's trees are exponential — so why does N-Queens (place N queens on an N×N board, none attacking another) finish in milliseconds? Because you don't walk branches you can prove are dead. Before placing a queen, check the square isn't attacked; if it is, the entire subtree of boards below that placement is skipped — millions of nodes, killed by one O(1) check:
def solve(row, cols, diag1, diag2, n, count=[0]):
if row == n:
count[0] += 1 # a full valid arrangement
return
for col in range(n):
if col in cols or (row - col) in diag1 or (row + col) in diag2:
continue # PRUNE: attacked -> skip the subtree
cols.add(col); diag1.add(row - col); diag2.add(row + col)
solve(row + 1, cols, diag1, diag2, n) # explore
cols.discard(col); diag1.discard(row - col); diag2.discard(row + col)Note the three sets answering "attacked?" in O(1) — a data structure choice doing algorithmic work — and the choose/explore/un-choose beats again (add, recurse, discard). Prune early, prune cheaply: the earlier a doomed branch dies, the more exponential growth never happens.
What if...?
What if the input has duplicates and subsets must be unique? Sort first, then at each decision level skip a value equal to the one just tried at the same level. Sorting makes duplicates adjacent so the skip is O(1) — the standard follow-up to the subsets question.
What if the recursion is deeper than ~1000? Python's limit says RecursionError. Options: rewrite with an explicit stack (any recursion can be), or raise the limit knowingly. Long linked lists and deep grids hit this in practice — anticipate it aloud.
What if different branches keep asking the same question? That's the fib disease — memoise (cache by the arguments that determine the answer). But note: subsets does NOT have this disease — every path produces distinct output, so there's nothing to reuse. "Do different branches repeat a state?" is the question that separates backtracking problems from DP problems.
What if I'm asked for ONE solution, not all? Return early: propagate a found-flag (or return True) up the recursion the moment a leaf succeeds — pruning's cousin, stopping the whole search rather than one branch.
Common mistakes
- No base case, or "progress" that doesn't shrink the problem — RecursionError.
- Appending the live
pathinstead of a snapshotpath[:]. - Forgetting the un-choose — branches contaminate each other.
- Ignoring recursion's O(depth) stack when asked about space.
- Backtracking where plain iteration works — if choices don't interact, a loop (or itertools) is simpler.
- Missing repeated subproblems — staying exponential when a cache would collapse the tree.
How do I recognise these problems?
- "all subsets / combinations / permutations / arrangements" → backtracking, with the counting check (2ⁿ? n!?) for feasibility.
- "place things under constraints" (N-Queens, sudoku, word search in a grid) → backtracking with pruning; the is-valid check IS the algorithm.
- "predict the output" of a function calling itself → trace with the down/up discipline: code before the call runs on the way down, code after on the way back.
- Small n (≤ 20) with "try everything" flavour → the setter intends exponential search; go confidently.
Quick revision
| Concept | One-liner |
|---|---|
| The contract | base case + guaranteed progress toward it |
| The machinery | call stack: pause, push a frame, resume in reverse |
| Thinking method | trust the smaller call; verify base + one-step assembly |
| Backtracking | choose → explore → un-choose, on one shared path |
| Counting | subsets 2ⁿ, permutations n! — the feasibility check |
| Costs | time = nodes explored (prune!); space = O(depth) |
One thing to remember
Recursion is a stack of unfinished work; backtracking is recursion that restores the world after every guess. Save the undo and you save the algorithm.
Practice Zone — PYQs from real selection rounds
Six MCQs, then three drills: the call stack drawn by hand, subsets with both classic bugs examined, and grid-path counting with precise base cases.
Every correct recursive function must have:
Asked in
What does fun(3) print?
def fun(n): if n == 0: return; print(n); fun(n - 1); print(n)
Asked in
Naive recursive fib(n) — fib(n-1) + fib(n-2) with no memoisation — has time complexity:
Asked in
The backtracking template is choose → explore → un-choose. The un-choose step exists because:
Asked in
Generating all subsets of a set of n elements produces how many subsets, and why?
Asked in
In N-Queens, pruning means:
Asked in
Hands-on tasks:
For factorial(4), draw the call stack at its deepest moment, then show the returns unwinding.
Asked in
Print all subsets of [1, 2, 3] with choose-explore-unchoose. What happens if you forget path.pop()?
Asked in
Count all paths from the top-left to bottom-right of a 3×3 grid moving only right or down, recursively. Then state the base cases precisely.
Asked in
FAQ
Is recursion slower than loops?
Per call, slightly — frames cost more than loop iterations, and Python doesn't optimise tail calls. The real differences are structural: recursion pays O(depth) memory and risks the stack limit; loops don't. Use recursion where the problem is tree-shaped and bounded; convert to a loop when it's linear (factorial converts trivially).
Backtracking vs brute force — same thing?
Backtracking IS exhaustive search, organised: incremental construction + undo + pruning. Pruning is the practical difference — validity checks kill subtrees early, which is why N-Queens finishes in milliseconds while blind enumeration of all placements would not finish at all.
When should I memoise a backtracking solution?
When the same state — the arguments that determine the result — recurs across branches with the same answer. Fibonacci and path-counting repeat states constantly (→ memoise); subsets never does (each path is unique output). Ask "do different branches ask the same question?" — if yes, DP is calling.
How do I keep track of state — parameters or shared variables?
Both work; the trade is explicitness vs efficiency. Passing fresh copies (path + [x]) needs no undo but copies at every level (O(n) per call). The shared-path-with-undo style is O(1) per choice and interview-standard — as long as the undo discipline is perfect. Pick one style per problem and be consistent.
Choices explored and cleaned up. Next, recursion's most disciplined form — split, solve, combine — Lesson 5: Divide & Conquer →