BeginnerRecursion
Recursion: a base case and a smaller problem
A function handles one step and hands the rest to a smaller copy of itself, until a answers directly.
The idea
Every recursive function needs two parts: a base case that answers without calling itself, and a step that makes the input smaller and calls itself on what's left.
Trust the call. Assume total(rest) already returns the right answer, and only work out how to combine it with the current item. Each call waits on the until the one below it returns.
Worked example
total([2, 5, 1])
- total([2, 5, 1]) = 2 + total([5, 1])
- total([5, 1]) = 5 + total([1])
- total([1]) = 1 + total([]), and total([]) = 0 is the base case
- Unwinding: 1 + 0 = 1, then 5 + 1 = 6, then 2 + 6 = 8
In code (Python)
def total(nums, i=0):
if i == len(nums): # base case: nothing left
return 0
return nums[i] + total(nums, i + 1)
def power(x, n): # halve n each call: O(log n)
if n == 0:
return 1
half = power(x, n // 2)
return half * half if n % 2 == 0 else half * half * xtotal: time and O(n) call stack. power: , since each call halves n.
How to spot it
- The answer is defined by a smaller copy of the same problem: n − 1, n / 2, the rest of a list, a .
- Nested structures: brackets inside brackets, folders inside folders.
Common mistakes
- A missing base case, or one the input never reaches: the calls never stop and the overflows.
- Python stops at about 1,000 nested calls by default: for long inputs, use a loop instead.
Practise it
Go further
Up next for you · Beginner
“Have I seen this?” is a set →