Functions that call themselves: base cases, the call stack, recursion trees, memoization, divide & conquer — and the discipline that stops infinite loops.
0 of 8 lessons checked off
Introduction
What it is
Recursion solves a problem by solving smaller copies of itself: a recursive case that shrinks the input, and a base case that stops the shrinking.
Every recursive call pushes a frame onto the call stack; the deepest chain of unfinished calls determines the space cost.
Why it matters
Trees, graphs, backtracking, divide & conquer, and dynamic programming are all naturally recursive — mastering recursion first makes those four topics feel like variations instead of new subjects.
Interviewers use recursion to test whether you can define a problem in terms of itself — the core skill behind writing correct DP transitions.
How it works
Write the base case FIRST and make it airtight. Then write the recursive case assuming the function already works on smaller inputs — the 'leap of faith' that makes recursion writable.
Trust the contract: never trace five levels deep while writing. Trace only to verify, and only on tiny inputs.
When the same subproblem recurs (fib(3) computed twice), cache results — memoization — and exponential trees collapse to linear work.
All tree problems (height, LCA, path sums), permutations/subsets via backtracking, merge/quick sort, and the memoized recursions that become dynamic programming.
Analogy: Recursion is asking the person in front of you in a line 'what's your position?' — they ask the person ahead, until the front person answers '1' (base case), and answers flow back, each adding one.
Interactive diagram
Watch identical subproblems (f(2), f(1)) get recomputed — the overlap that memoization eliminates.
Naive fib(4) call tree
Each call spawns two more. Identical subproblems (same argument) are recomputed again and again — that overlap is what DP removes.
1 / 11
Lessons in this topic
Check off lessons as you go — your progress is saved in this browser.
Recursive thinking: base + recursive case
Shrink toward a guaranteed floor; the leap of faith.
Choose → explore → un-choose; full topic later in the roadmap.
20 min
Common recursion mistakes
Missing/wrong base case, non-shrinking input, shared mutable state.
15 min
Operations
Anatomy of a recursive function
Base case first, then recurse on strictly smaller input, then combine. Factorial shows all three in four lines.
Anatomy of a recursive function
1deffactorial(n:int)->int:2"""n! for n >= 0. O(n) time, O(n) stack."""3ifn<0:4raiseValueError("factorial is undefined for negatives")5ifn<=1:# base case: the guaranteed floor6return17returnn*factorial(n-1)# recursive case: smaller input8910deflist_sum(nums:list[int])->int:11"""Sum via structural recursion — the shape used on trees."""12ifnotnums:# base case: empty structure13return014returnnums[0]+list_sum(nums[1:])# note: slicing costs O(n)!
Time: factorial: O(n) — list_sum: O(n²) because each slice copiesSpace: O(n) call stack (plus slice copies in list_sum)
Edge cases
Validate inputs BEFORE recursing — one check at the top, not once per frame (or use an inner helper).
n = 0 and n = 1 both hit the base case here; check yours covers all floors.
Python's default recursion limit ≈ 1000 frames — deep inputs need iteration.
Common mistakes
Base case that can be stepped over (n == 1 when calls can reach 0).
Recursing on the same-size input — infinite recursion.
Hidden O(n) work per frame (slicing) silently squaring the complexity — pass indexes instead.
Memoization
Same recursion, plus a cache keyed by arguments. Each distinct subproblem is computed once; repeats are O(1) lookups.
fib(5) with memoization
Same recursion, but results are cached. Repeated subproblems become O(1) lookups, collapsing the tree to O(n) nodes.
1 / 11
1fromfunctoolsimportlru_cache234deffib(n:int,memo:dict[int,int]|None=None)->int:5"""Manual memoization: O(n) time, O(n) space."""6ifmemoisNone:7memo={}8ifn<=1:9returnn10ifninmemo:11returnmemo[n]# cache hit — no subtree grows12memo[n]=fib(n-1,memo)+fib(n-2,memo)13returnmemo[n]141516@lru_cache(maxsize=None)# the idiomatic version17deffib_cached(n:int)->int:18ifn<=1:19returnn20returnfib_cached(n-1)+fib_cached(n-2)
Base case + strictly shrinking input = termination proof. Be able to say both for any function you write.
Stack space counts: 'O(h) for recursion' on trees, 'O(n)' on linear recursions.
Recursion-tree complexity: branches^depth nodes × per-node work; memoization prunes to distinct states.
Python has no tail-call optimisation — deep linear recursion should become a loop.
Classic follow-ups
"Convert it to iteration" — explicit stack for tree shapes; running pair of variables for linear shapes.
"How many distinct subproblems?" — the question that converts your recursion into DP sizing.
"What's the recursion depth on this input?" — checking you know when 10⁵ depth will crash Python.
How to talk through recursion
State the function's CONTRACT in one sentence before coding: 'height(node) returns the height of the subtree rooted at node.' Every recursive call is then justified by the contract, not by tracing.
Verify with the smallest inputs only: empty, one element. If those are right and the input shrinks, induction does the rest.
Common mistakes
Missing or unreachable base case
fib(n)==fib(n-1)+fib(n-2) with only `n == 0` as base loops forever on n=1. Cover every floor the recursion can land on.
Input that doesn't shrink
search(node) that recurses on the same node, or ranges that never narrow, recurse infinitely. Point to what strictly decreases each call.
Shared mutable state across branches
Appending to one list in both branches without undoing (or copying) makes sibling calls see each other's leftovers — the classic backtracking bug.
Hidden per-frame O(n)
nums[1:] copies the list every call: an 'O(n)' recursion becomes O(n²). Pass indexes, not slices.
Recursing before validating
Input checks inside the recursive path run n times (or worse). Validate once in a public wrapper, recurse in a private helper.
Trusting Python with 10⁵ depth
RecursionError at ~1000 frames. For deep linear structures (long linked lists, path-shaped trees), write the loop.
Practice problems
Hand-picked from the 355-problem DSA Atlas. Reveal hints and solutions progressively; mark and bookmark as you solve.
Commonly associated with: Amazon, Meta, Google, Microsoft
O(n) time · O(n) space
Topic quiz
5 questions across concepts, code output, complexity, and scenarios. Answer all, then submit for explanations.
Frequently asked questions
How do I stop mentally tracing every call?
Use the contract discipline: write one sentence for what f(x) returns, make the base case honour it, then write the recursive case USING the contract on smaller inputs. Trace only n=0,1 to verify. This is how experienced engineers write recursion quickly.
Is recursion slower than iteration?
In Python, moderately — function-call overhead is real, and there's no tail-call optimisation. But interviews grade Big-O and clarity first. Choose recursion where structure demands it (trees, backtracking); convert to loops when depth threatens the stack.
What's the difference between memoization and dynamic programming?
Memoization is top-down DP: recursion + cache, computing only needed states. Tabulation is bottom-up DP: loops filling a table in dependency order. Same subproblem graph, different traversal — the DP topic builds directly on this page.
Summary & cheat sheet
Key takeaways
Base case first, airtight, covering every reachable floor; input must strictly shrink.
State the contract, take the leap of faith, verify only tiny cases.
Time = recursion-tree nodes × per-node work; space = deepest path + cache.
Overlapping subproblems + cache = memoization; it's the front door to DP.
Python: ~1000-frame limit, no TCO — deep linear recursion becomes a loop.