Recursion and Backtracking
Recursion Fundamentals
A recursive function calls itself with a smaller version of the problem until it hits a base case that stops the chain.
Every recursion needs two things:
- Base case - the simplest input where you return directly.
- Recursive case - break the problem down and call yourself.
def factorial(n):
if n <= 1: # base case
return 1
return n * factorial(n - 1) # recursive case
The Call Stack - Visualised
Each recursive call pushes a frame onto the call stack. When the base case returns, frames pop in reverse order.
factorial(4)
โ factorial(3)
โ factorial(2)
โ factorial(1) โ returns 1
โ returns 2
โ returns 6
โ returns 24
If there's no base case, the stack overflows. Python's default recursion limit is 1,000 frames.
Fibonacci - The Classic Trap
The naรฏve recursive Fibonacci is O(2โฟ) because it recomputes the same sub-problems. Memoisation fixes this in O(n) time and space.
from functools import lru_cache
@lru_cache(maxsize=None)
def fib(n):
if n < 2:
return n
return fib(n - 1) + fib(n - 2)
Backtracking - Try Everything, Then Undo
Backtracking is recursion with a twist: you make a choice, recurse, then undo the choice before trying the next option. Think of it as exploring a maze - walk forward, hit a dead end, walk back, try the next path.
The Backtracking Template
def backtrack(state, choices):
if is_solution(state):
result.append(state.copy())
return
for choice in choices:
if is_valid(choice):
state.add(choice) # choose
backtrack(state, ...) # explore
state.remove(choice) # un-choose
This three-step pattern - choose, explore, un-choose - is the backbone of nearly every backtracking problem.
In the backtracking template, why do we undo the choice after the recursive call?
Discussion
Sign in to join the discussion