Know this before you start: “Make the input smaller every call”
Make the input smaller every call
Each call must work on a strictly smaller input: n − 1, n // 2, the rest of the list, a child . That's what guarantees the is reached.
The idea
Ask: what's the smaller version of this question, and how does its answer build this one? Writing 13 in binary is writing 13 // 2 = 6 in binary, then adding the last bit, 13 % 2 = 1.
How fast the input shrinks sets the cost. Taking one off (n − 1) gives n calls; halving (n // 2) gives about log₂ n calls.
Trust the smaller call to be right. Don't trace every level in your head: check the base case, check one step, and the rest follows (it's induction).
Worked example
13 in binary
- binary(13) = binary(6) + "1"; binary(6) = binary(3) + "0"; binary(3) = binary(1) + "1".
- binary(1) = "1": a single digit, the base case.
- Back up: "1" + "1" = "11", + "0" = "110", + "1" = "1101". Four calls for a number around 2⁴.
Pseudocode
The steps in plain words. ← means “set to”; indentation shows what's inside what.
See it run
The worked example, step by step, beside the Python. The highlighted line is the one running.
Step-by-step
n = 13
call stack
Solution · Pythonline 4
def binary(n):if n < 2: # 0 or 1: already one binary digitreturn str(n)return binary(n // 2) + str(n % 2) # half the number, then the last bit def total(nums):if not nums:return 0return nums[0] + total(nums[1:]) # one shorter each call print(binary(13), binary(0)) # 1101 0print(total([4, 1, 5])) # 10Step 1 of 8· line 4
binary(13) = binary(6) + "1": half the number (smaller), then its last bit.
- just added
Halving: calls. Removing one item: calls (and nums[1:] copies, O(n) each).
When you'll use it
- Numbers digit by digit or bit by bit, lists from the front, trees child by child, ranges split in half.
In the wild · Folders and JSON: Finding every file in a folder means listing the folder and doing the same for each folder inside it. Code that reads nested JSON walks it the same way.
Common mistakes
- A call that doesn't shrink, like f(n) calling f(n) or binary(n // 1).
- Slicing (nums[1:]) inside deep recursion: pass an index instead to avoid copying.