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

  1. binary(13) = binary(6) + "1"; binary(6) = binary(3) + "0"; binary(3) = binary(1) + "1".
  2. binary(1) = "1": a single digit, the base case.
  3. 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.

binary(n):
if n < 2: return n as text(one digit already)
return binary(n ÷ 2, rounded down) + (n mod 2)
every call gets a smaller n, so it reaches the base case

See it run

The worked example, step by step, beside the Python. The highlighted line is the one running.

Step-by-step

n = 13

n = 13n // 2 = 6n % 2 = 1

call stack

binary(13)◀ top

Solution · Pythonline 4

def binary(n):
if n < 2: # 0 or 1: already one binary digit
return str(n)
return binary(n // 2) + str(n % 2) # half the number, then the last bit
def total(nums):
if not nums:
return 0
return nums[0] + total(nums[1:]) # one shorter each call
print(binary(13), binary(0)) # 1101 0
print(total([4, 1, 5])) # 10

Step 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.

Practise it · before the Recursion problems

Write a number in binary

Return n (n ≥ 0) written in binary, with no leading zeros ("0" for 0). Use .

Input n = 13

Output "1101"

Input n = 0

Output "0"

Pass every test and this concept is marked as known on the roadmap and on every problem that needs it.

Your code

Tab / Shift+Tab indent · ⌘/Ctrl+/ comments · ⌘/Ctrl+Enter runs · Esc leaves the editor

Stuck?