1Understand
The idea
A recursive function solves a problem by trusting itself on a smaller instance: define the base case, then build the answer from the smaller answers. When the same subproblem is reached again and again (as in Fibonacci), cache it with @cache and the exponential tree collapses to one call per distinct state.
Intuition
Recursion solves a problem by trusting the same function on a smaller instance. You need a base case that stops, and a recursive case that makes real progress toward that base.
When the call tree recomputes the same subproblem (Fibonacci-style), memoisation collapses it: @cache or an explicit dict stores each distinct state once. Without that, branching recursion is often exponential.
Deep recursion can hit Python's recursion limit; some problems want an explicit stack or an iterative rewrite once the idea is clear.
What you will be able to do
- Identify base and recursive cases
- Trace the call stack
- Add memoisation with @cache when subproblems repeat
When to use it
- The problem is defined in terms of a smaller version of itself
- Nested or self-similar input
- The same subproblem is solved many times
2See it
Walkthrough
Fibonacci with a call stack
fib(4), each call waits on smaller n until the base case.
1 / 4
Call fib(4). Not a base case, so it needs fib(3) and fib(2).
Live template
Line 5 active
Complexity: time depends on branching, space O(depth) call stack
Time follows the number of distinct states times work per state; without memo it follows the size of the call tree. Space is O(depth) for the stack plus O(states) for the cache. If depth can be 10⁵, prefer iteration.
Read the walkthrough as text
Fibonacci with and without cache.
Naive:
In code:
def fib(n):if n <= 1: return nreturn fib(n - 1) + fib(n - 2)
fib(5) recomputes fib(3) twice, exponential.
Memoised:
In code:
from functools import cache@cachedef fib(n):if n <= 1: return nreturn fib(n - 1) + fib(n - 2)
- Base:
0and1. - Each
nis computed once and reused. - Time drops to O(n) distinct states; stack depth is still O(n).
3Recognise it
Kinds of problems (5)
Same pattern, different surfaces. Each row is a problem shape you should recognise, not only the first walkthrough example.
Linear recursion (sum, reverse)
Example. Sum a list or reverse a linked list recursively.
How. One recursive call per step: return combine(head, solve(tail)); base case is empty input.
Branching recursion (Fibonacci-style)
Example. Count ways with two choices at each step (stairs, decode).
How. Return sum (or max) of recursive results on each branch; memoise when the same state repeats.
Recursion on nested structures
Example. Max depth of a nested list or flatten one level.
How. Recurse into each child; combine child answers at the current node.
Memoisation with @cache
Example. Fibonacci or grid paths with overlapping subproblems.
How. Add `@cache` so each distinct argument is solved once; time becomes number of states × work per state.
Converting recursion to iteration
Example. Interviewer asks for O(1) extra space after a recursive draft.
How. Replace the call stack with an explicit stack or rolling variables (last two dp values).
Common mistakes
Failure modes the tutor watches for. Open the Common mistake tab in the walkthrough to watch one fail live.
Missing base case
Why it happens. The recursive case is written first; the stopping condition is vague or wrong.
How it fails. factorial(0) keeps calling factorial(-1) until Python raises RecursionError.
Fix. Write base cases that return without recursing; trace the smallest input on paper before coding.
No progress
Why it happens. The recursive call uses the same argument size as the parent.
How it fails. def f(n): return f(n), infinite recursion on any input.
Fix. Each call must move toward a base case: n−1, smaller slice, or strictly fewer items.
Exponential recomputation
Why it happens. Branching recursion without caching recomputes the same subproblem many times.
How it fails. fib(35) with plain recursion does millions of redundant fib(20) calls.
Fix. Add `@cache` / memo dict, or rewrite to bottom-up DP when states repeat.
Recursion depth
Why it happens. Problem size is large but the solution still deep-recurses.
How it fails. Summing a linked list of length 10⁶ via recursion exceeds the default recursion limit.
Fix. Use iteration, or bisect depth; for deep trees prefer explicit stacks.
4Check yourself
Concept check
A short quiz on this lesson before you practise. Optional, and it does not gate coding.
Ready to practise?
Mastery comes from solving. The lesson is optional context.