Recursion and problem solving
Solve problems that contain smaller versions of themselves, trace the call stack, and know when iteration is safer.
By the end, you’ll be able to…
- Identify a base case and a smaller subproblem before writing recursive code.
- Trace recursive calls through the call stack and trust the smaller result.
- Use memoization for repeated subproblems and recognize depth limits.
01A problem can contain a smaller copy of itself
Recursion is a function calling itself on a smaller version of the same problem. Every recursive function needs at least one base case that can return without another call. The recursive case must make progress toward that base case; otherwise the call stack grows until Python raises a RecursionError. Start by writing the smallest case you can answer directly.
The factorial function demonstrates the shape. factorial(0) returns 1 without calling itself. For a positive n, the function multiplies n by factorial(n - 1). You do not need to trace every multiplication to trust the result; you need to verify the base case and the step that reduces the problem.
def factorial(n): if n < 0: raise ValueError("n must be nonnegative") if n == 0: return 1 return n * factorial(n - 1)print(factorial(5))print(factorial(0))120 1
02Trust the recursive call
When writing a recursive function, assume the call on the smaller input already works. Your job is to combine that result correctly. This is the same reasoning as using a helper function: you rely on its contract rather than simulating its entire implementation. For nested lists, the recursive call can total one child while the outer call adds the children together.
The call stack is the sequence of suspended function frames. A trace is useful for a small input, but do not let a trace become the only explanation. State the invariant: total(values) returns the sum of every number in this nested structure. The base case returns a number; the recursive case sums the results for each child.
def total(values): if isinstance(values, list): return sum(total(value) for value in values) return valuesprint(total([1, [2, 3], [4, [5]]]))15
03Trees and backtracking
Trees, nested JSON, file directories, and expressions are naturally recursive because each node contains smaller nodes. A tree walk is often just a base case for a leaf and a recursive combination for an internal node. This structure is also the foundation of backtracking: explore one choice, recurse, then undo the choice before trying the next one.
A small tree class makes the shape visible. tree_sum(node) adds the node's own value to the sums of its children. If a node has no children, sum over an empty tuple is zero, so the same function handles leaves and internal nodes without a separate branch. Recursion can be a clear way to express a structural rule.
from dataclasses import dataclass@dataclassclass Node: value: int children: tuple = ()def tree_sum(node): return node.value + sum(tree_sum(child) for child in node.children)root = Node(1, (Node(2), Node(3, (Node(4),))))print(tree_sum(root))10
04Know when to stop
Recursive Fibonacci calls fib(n - 1) and fib(n - 2) repeatedly, so the number of calls grows quickly. Memoization stores results that have already been computed. functools.cache is the shortest way to add it when the function is pure and its arguments are hashable. The cached function still recurses, but each subproblem is solved once.
Memoization does not remove the depth limit. Python's call stack is finite, and very deep recursion can fail even when the algorithm is correct. Use an explicit loop or a stack when the input may be large. Also avoid recursion when a simple loop is easier to read; recursion should clarify the shape of the problem, not merely replace a for statement.
from functools import cache@cachedef fib(n): if n < 2: return n return fib(n - 1) + fib(n - 2)print([fib(n) for n in range(10)])print(fib(30))[0, 1, 1, 2, 3, 5, 8, 13, 21, 34] 832040
The ideas worth keeping.
- Write the base case first, then make every recursive call solve a strictly smaller problem.
- Recursion is a good fit when the data itself is nested or tree-shaped.
- Memoization trades memory for repeated work; it does not remove stack-depth limits.
Make it yours.
Type and test your code right here in the interactive workspace. Run your solution, check the output, and compare with the worked guide when ready.
Sum the digits
Write digit_sum(n) recursively. The base case is a single digit; the recursive case adds n % 10 to the sum of the remaining digits.
Explore a worked solution
def digit_sum(n): if n < 0: raise ValueError("n must be nonnegative") if n < 10: return n return n % 10 + digit_sum(n // 10)print(digit_sum(4729))print(digit_sum(8))n // 10 removes the last digit, so every call moves toward the base case. The remainder is the digit discarded by that division.
Flatten a nested list
Write flatten(values) that returns a new flat list from arbitrarily nested lists. Keep the original values unchanged.
Explore a worked solution
def flatten(values): result = [] for value in values: if isinstance(value, list): result.extend(flatten(value)) else: result.append(value) return resultprint(flatten([1, [2, [3]], 4]))The recursive call handles one nested branch, and extend appends its results to the current level. isinstance is the base-case boundary for this particular structure.
What stayed with you?
Check the ideas while they’re fresh. Your answers stay in this page and feedback appears as you go.
Sum the digits
Write digit_sum(n) recursively. The base case is a single digit; the recursive case adds n % 10 to the sum of the remaining digits.
digit_sum(4729) digit_sum(8)
Keep exploring.
The official references behind this chapter, when you want a second angle or the full details.
One chapter closer.
Reading is a start. Trying it yourself makes the connection.