Recursion Practice
Sum, power and digits.
The secret to writing recursion is to trust it. Ask two questions. What's the smallest version, that I can answer directly? And how can I solve a big version, if someone solved a slightly smaller one for me? Let's practise with three small problems.

- Trust the recursion
- What's the smallest case?
- How does smaller help?
Three recursive functions
The sum of a list is the first item, plus the sum of the rest. An empty list sums to zero. Power of a number is the number, times the power one smaller. Anything to the power zero is one. And the sum of digits is the last digit, plus the sum of the digits that are left. Run it.
def total(nums):
if not nums:
return 0
return nums[0] + total(nums[1:])
def power(x, n):
if n == 0:
return 1
return x * power(x, n - 1)
def digit_sum(n):
if n < 10:
return n
return n % 10 + digit_sum(n // 10)
print(total([4, 2, 7]), power(2, 10), digit_sum(2026))13 1024 10
The recipe
Every recursive function follows the same recipe. First, handle the base case, and return the answer directly. Second, make the problem smaller. Third, call yourself on the smaller problem. Fourth, combine that result into your answer. If you can describe those four steps, the code almost writes itself.
| key | value |
|---|---|
| 1. Base case | answer directly |
| 2. Shrink | make it smaller |
| 3. Recurse | call yourself |
| 4. Combine | build your answer |
Summary
Base case, shrink, recurse, combine. With that recipe, recursion becomes much less mysterious. Next, a way to make slow recursion incredibly fast. Memoization.
Key takeaways- Trust it
- Base case, shrink, recurse, combine
- Practise small problems