0 Β· Start Simple β Two Tiny Questions First
Short words, small numbers. Recursion comes in two shapes: a chain (one call at a time β this section) and a tree (calls that split β Β§2, where you will build the tree yourself). Start with the chain.
Tiny Question A β Count down and blast off π
countdown(3) should print 3, 2, 1, then Blast off!. That is all. Follow the chain down β then the calls come back up and finish, one by one:
def countdown(n):
if n == 0: # BASE: nothing left to count
print("Blast off!")
return
print(n)
countdown(n - 1) # SMALLER: one less
countdown(3)
n == 0 β no counting left. Print Blast off! and stop. No self-call.n - 1 β the next call counts one less: 3 β 2 β 1 β 0.Call
countdown(n - 1). Nothing to combine here β the printing happens on the way down.Tiny Question B β Add up 1 to n β
add_up(4) should return 1 + 2 + 3 + 4 = 10. Same chain shape β but this time each call keeps its number and adds it on the way back up:
β BASE: add_up(0) = 0
coming back up: add_up(1) = 1 + 0 = 1 Β· add_up(2) = 2 + 1 = 3 Β· add_up(3) = 3 + 3 = 6 Β· add_up(4) = 4 + 6 = 10
def add_up(n):
if n == 0: # BASE: nothing to add
return 0
return n + add_up(n - 1)
print(add_up(4)) # 10
n == 0 β return 0. Adding nothing changes nothing β the perfect base answer for a sum.n - 1 β add up a shorter list of numbers.Call
add_up(n - 1), trust its answer, combine: n + that answer β and return it up the chain.digit_sum is Tiny B with digits, and routes is what happens when the chain splits into two. The practice page also opens with five tiny questions like these β do those before the CCC problems.β The Recursion Recipe β How to Write One, Every Time
Don't start by typing code. Start by filling in these three boxes. Every recursion in this lesson β and every CCC recursion you will meet β is this same skeleton with different words in the boxes.
def solve(state):
# 1. BASE CASE β the smallest problem.
# Answer it directly. NO self-call here.
if state is the smallest:
return direct_answer
# 2. MAKE IT SMALLER β one step closer to the base case.
smaller_state = state moved one step closer
# 3. CALL ITSELF + COMBINE β trust the smaller answer,
# then build your answer out of it. RETURN it, don't print it.
return combine( solve(smaller_state) )
Answer these 3 questions before you write a single line
- What is the state? What changes from call to call? A number getting smaller, a position moving, items running out⦠That is what goes in the brackets:
solve(state). - What is the smallest state β and what is its answer? That is your base case. Write this line first, before anything else. A completed thing usually counts as 1; an impossible one counts as 0.
- How does each call get strictly closer to the base case? If you can't say β in one sentence β how the problem shrinks (
n // 10,left - 1,i + 1), the recursion will never stop. No progress = infinite recursion.
return and combine. Part 3 becomes CHOOSE β EXPLORE (the self-call) β UNDO: try a choice, call yourself, then take the choice back so the next branch starts clean. That is Β§3, Β§4 and Β§5 β watch for the purple label.solve(smaller_state), do not trace the whole smaller call in your head. Trust that it returns the right answer for that smaller problem β your only job is to combine it correctly. Tracing every level is how recursion feels impossible; trusting the contract is how it becomes easy. Under each example below, the same three labels show you exactly where each part lives.1 Β· Think in Smaller Problems β the Call Stack
A recursive call does not run βlaterβ. It runs now, on top of the current call, which waits β remembering its own local variables.
Sum the digits of a number β without turning it into a string
Write digit_sum(n) that returns the sum of the digits of n. The last digit is easy (n % 10). The rest of the number is⦠the same problem, one digit smaller.
Sample call
digit_sum(507)
Returns
12
if n == 0: return 0 β no digits left, nothing to add. (One digit alone also answers itself.)n // 10 chops off one digit every call: 507 β 50 β 5 β 0. The base case must be reached.Call
digit_sum(n // 10), trust it, then combine: last digit (n % 10) + that answer β and return the sum.The code
def digit_sum(n):
if n == 0: # base case
return 0
last = n % 10
smaller = digit_sum(n // 10)
return last + smaller
print(digit_sum(507)) # 12
Read it like a contract
Contract: digit_sum(n) returns the digit sum of n (for n β₯ 0). The recursive line does not need to know how the smaller answer is produced β it trusts the contract.
n // 10 removes one digit every call, so the calls must reach 0. Progress toward the base case is not automatic β you design it.
return hands a value to the caller; print shows text to a human. A function that calculates must return its answer β print only the final result, once, outside.2 Β· Count Branches with Return Values β the Recursion Tree
When a call makes two smaller calls and adds their answers, the stack becomes a tree β and repeated subtrees are the price.
How many ways can a robot climb a staircase, moving 1 or 2 steps at a time?
Define routes(left) = the number of move sequences that climb exactly left more steps. The first move is either 1 step or 2 steps β after that, what remains is the same problem.
Sample input
3
Sample output
3
Two base cases:
left == 0 β return 1 (arrived β one finished route) and left < 0 β return 0 (overshot β no route).Take 1 step,
left - 1 remains; or take 2 steps, left - 2 remains. Both are closer to 0.Call itself twice and combine by adding:
routes(left - 1) + routes(left - 2). Two calls is what turns the stack into a tree.π³ Now YOU build the tree β routes(4), one step at a time
You just watched a tree for routes(3). Now build a bigger one yourself. Press Step slowly. When you see β YOUR TURN, stop β say the answer out loud (or write it down) β then press Step to check yourself. That guessing is not a trick: building the next step in your head is learning recursion.
Same code + a memory: memoization
The answer for a state depends only on that state, so we can store it. Python does it with one decorator:
from functools import lru_cache
@lru_cache(None)
def routes(left):
if left == 0:
return 1
if left < 0:
return 0
return routes(left - 1) + routes(left - 2)
routes is O(N) time and memory β but the call depth is still O(N). For very deep chains (tens of thousands), recursion hits Python's stack limit; raising the limit does not remove the risk. Deep and simple? Loop instead.3 Β· Generate Possibilities with Backtracking β Choose, Explore, Undo
Counting asked βhow many?β Generation asks βshow me all of them.β The engine is a path that grows, branches, and β critically β shrinks back.
Print every binary string of length 2
Build strings position by position. At each position, try '0', then '1'.
Call
build([], 2)
Output
00 01 10 11
[] and the target length n = 2 β there is no string to read in. Output is every string the building can produce: 00, 01, 10, 11, one per line. Nothing is counted and nothing is returned β each finished string is printed the moment it reaches full length.build(...) call is a box. Solid blue = running now; light blue = a caller paused, waiting for its child; green = finished, control back with its caller. Below, the shared list itself. Keep your eye on the tree when a box turns green β that is the moment a call returns.if len(path) == n: the string is complete β print it and return. Nothing smaller remains to build.Each call appends one character, so
len(path) grows by 1 towards n every level.Choose
'0' (append) β explore: call build(path, n) β undo (pop()). Then do the exact same three steps with '1'.The code (shared list version)
def build(path, n):
if len(path) == n:
print(''.join(path))
return
for bit in ['0', '1']:
path.append(bit) # choose
build(path, n) # explore
path.pop() # undo
build([], 2)
Two versions, one trap
With strings (build(prefix + '0', n)), each call gets a fresh value β no undo needed, because strings never change. With a shared list, the undo (pop()) is your job.
answers.append(path) saves the same list object every time β all entries mutate together. Store path.copy().4 Β· Subsets and Safe Pruning
Same skeleton, new question: at each item, skip or take. Pruning is how we refuse to explore branches that are already dead β but only with a proof.
How many subsets of the packs sum to exactly 5?
Four labelled packs cost [2, 3, 3, 5]. A subset may use each pack at most once, in any combination β order does not matter, but the two 3-cost packs are different packs.
Input
4 5 2 3 3 5
Output
3
(i, total) β small enough to memoize later, and the pruning rule teaches the habit: cut a branch only when you can prove it cannot recover.count_sets(i, total) call is a box labelled cs(i, total). Orange dashed boxes are the branches the running call is about to try; red boxes were pruned; when a call finishes, its box folds up green and keeps only what it returned β the sum of its two branches. The full tree has 27 calls, too wide to draw at once, so finished branches fold away and you always see the live path. Below, the decisions made so far.i == n (no packs left): return 1 if total == target, else 0. Plus the prune: total > target β return 0 immediately.i + 1 β one more pack decided, on both branches. The pack index, not the total, is what guarantees progress.Call itself twice and add:
count_sets(i + 1, total) (skip the pack) + count_sets(i + 1, total + prices[i]) (take it).n, target = map(int, input().split())
prices = list(map(int, input().split()))
def count_sets(i, total):
if total > target: # prune: positive prices can never come back down
return 0
if i == n:
return int(total == target)
skip = count_sets(i + 1, total)
take = count_sets(i + 1, total + prices[i])
return skip + take
print(count_sets(0, 0))
5 Β· Grid Paths and Visited Cells β Mark, Explore, Unmark
Backtracking on the Lesson 7 grid. Here visited means βused in this current pathβ β a temporary claim, not a permanent one.
How many paths cross a 3Γ3 grid without reusing a cell?
Move β β β β from (0, 0) to (2, 2). The centre cell is a wall. A path may not enter the same cell twice β but different paths may share cells freely.
Grid
. . . . # . . . .
Output
2
paths(r, c) call that actually enters a cell becomes a box; when it returns, the box turns green and keeps the number of paths that call found. Probes that hit the outside, the wall, or an already-visited cell return 0 on the spot β they never become boxes, and the captions report them. Below, the grid itself.def paths(r, c):
if not (0 <= r < rows and 0 <= c < cols):
return 0
if grid[r][c] == '#' or visited[r][c]:
return 0
if (r, c) == (rows - 1, cols - 1):
return 1
visited[r][c] = True # mark
total = 0
for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
total += paths(r + dr, c + dc) # explore
visited[r][c] = False # unmark
return total
Three base answers in one: off the grid or a wall / already-visited cell β
return 0; standing on the goal cell β return 1 (one complete path found).Step to a neighbouring cell β
(r Β± 1, c) or (r, c Β± 1). The path gets one cell longer; the cells left to use get fewer.Mark this cell visited β call
paths(...) on all 4 neighbours and add their counts β unmark before returning, so other paths may use this cell.Decide what βvisitedβ means β before you code
| Task | visited means⦠| Undo? |
|---|---|---|
| Count all non-repeating paths (Β§5) | used in this path | Yes β unmark on exit |
| Reachability / flood fill (Harvest) | already processed, ever | Never |
6 Β· Recursion You Can See β Fractals, Then the Exam Routine
One more shape of recursion: a drawing that contains smaller copies of itself. This is the heart of 2004 J5 β Fractals, waiting for you on the practice page.
What does the block fractal look like at level 3?
Start with one straight segment. Rule: split every segment into thirds; the middle third becomes three sides of a square bump. Apply the rule to every segment, again and again. Level 0 is the plain segment.
The routine for any search question
Steps 1β3 are the Recipe at the top of this page β state, base case, progress β said in exam language. Run all six, in order, before you write code.
- Define the state in words, and exactly what the function returns.
- Base cases: success and failure β including empty inputs where allowed.
- Legal next choices: list them; check every choice changes the state (progress!).
- Ownership: what belongs to one call, and what shared data needs an undo.
- Uniqueness: convince yourself every valid answer is produced exactly once. Prune only with a proof.
- Size check: estimate the search (2N? N!? depth?) and test the smallest, impossible, and repeated-value cases.
Common mistakes β the wall of shame
count_sets(...) on its own line computes β and throws away.