PYTHON 3 Β· CCC JUNIOR Β· LESSON 8

Recursion & Backtracking πŸ”

One idea powers this whole lesson: a function that calls itself on a smaller problem β€” and trusts the smaller answer.

Every example starts with the question. Then we watch the calls happen: down the stack, across the tree, and back again.

The whole lesson on one line: state what the function returns, find the base case that answers directly, and make every call smaller. If one of those three is missing, the recursion is broken before it starts.

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:

countdown(3) prints 3β†’ countdown(2) prints 2β†’ countdown(1) prints 1β†’ countdown(0) ⭐ BASE: prints Blast off!β†’ back up: every caller is done
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)
1 Β· BASE CASE
n == 0 β€” no counting left. Print Blast off! and stop. No self-call.
2 Β· MAKE IT SMALLER
n - 1 β€” the next call counts one less: 3 β†’ 2 β†’ 1 β†’ 0.
3 Β· CALL ITSELF + COMBINE
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:

going down: add_up(4) needs add_up(3) Β· add_up(3) needs add_up(2) Β· add_up(2) needs add_up(1) Β· add_up(1) needs add_up(0)
⭐ 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
1 Β· BASE CASE
n == 0 β†’ return 0. Adding nothing changes nothing β€” the perfect base answer for a sum.
2 Β· MAKE IT SMALLER
n - 1 β€” add up a shorter list of numbers.
3 Β· CALL ITSELF + COMBINE
Call add_up(n - 1), trust its answer, combine: n + that answer β€” and return it up the chain.
Chain first, tree second. If these two feel easy, Β§1 and Β§2 are the same ideas with bigger clothes on: 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

  1. 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).
  2. 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.
  3. 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.
One variation, for searching / generating (backtracking): there is often nothing to 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.
The trust rule: when you write 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.

❓ THE QUESTION FIRST

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
Why this section: if you can watch these four calls stack up and unwind, you understand every recursion in this lesson. The tree, the search, the grid β€” all are this, with more branches.
1 Β· BASE CASE
if n == 0: return 0 β€” no digits left, nothing to add. (One digit alone also answers itself.)
2 Β· MAKE IT SMALLER
n // 10 chops off one digit every call: 507 β†’ 50 β†’ 5 β†’ 0. The base case must be reached.
3 Β· CALL ITSELF + COMBINE
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 β‰  print. 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.

❓ THE QUESTION FIRST

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
Why this section: the routes are 111, 12, 21. Counting without listing them is the CCC J5 move β€” and the repeated-subtree waste you are about to see is exactly what Pi Day (2015 J5) punishes.
Why is routes(0) = 1? Standing at the top with 0 steps left, there is exactly one way to finish: choose nothing more. Returning 0 here would silently erase every route that ends exactly. And routes(βˆ’1) = 0: an overshoot is not a route at all. Getting these two base cases right is most of counting recursion.
1 Β· BASE CASE
Two base cases: left == 0 β†’ return 1 (arrived β€” one finished route) and left < 0 β†’ return 0 (overshot β€” no route).
2 Β· MAKE IT SMALLER
Take 1 step, left - 1 remains; or take 2 steps, left - 2 remains. Both are closer to 0.
3 Β· CALL ITSELF + COMBINE
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.

What you just did, in Recipe words: the leaves of your tree are the BASE CASE β€” every split is MAKE IT SMALLER (βˆ’1 and βˆ’2) β€” and the answers bubbling up and adding are CALL ITSELF + COMBINE. Every recursion tree you ever meet is built exactly like this: down the left side first, answers back up.

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)
Memoization is not free. The cached 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.

❓ THE QUESTION FIRST

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
Why this section: this exact choose–explore–undo skeleton is the engine inside three of this lesson's CCC problems: Word Hunt, Rule of Three, and every subset search. Learn it once here, where the output fits on one screen.
What goes in, what comes out β€” plainly: Input is just two things: an empty starting path [] 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.
β–Ά How to read the walkthrough β€” three views, moving together: left, the code, with the line that is running right now lit up. Right, the call tree: every 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.
How to read the pop πŸ‘€: the boxes are the list itself. Append = a new green box lands at the end. Pop = the last box turns red, lifts up and out, and leaves a dashed empty slot β€” next step it is gone and the list is one box shorter. Pop always takes the last box, never one from the middle β€” that is why the undo exactly cancels the append that came just before it.
1 Β· BASE CASE
if len(path) == n: the string is complete β€” print it and return. Nothing smaller remains to build.
2 Β· MAKE IT SMALLER
Each call appends one character, so len(path) grows by 1 towards n every level.
3 Β· CHOOSE Β· EXPLORE Β· UNDO
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.

The reference trap: if you store finished paths instead of printing them, 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.

❓ THE QUESTION FIRST

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
Why this section: subset counting with pruning is the Junior–Senior bridge pattern. The state is just (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.
β–Ά How to read the walkthrough β€” three views, moving together: left, the code, lit line = running now. Right, the call tree: every 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.
1 Β· BASE CASE
i == n (no packs left): return 1 if total == target, else 0. Plus the prune: total > target β†’ return 0 immediately.
2 Β· MAKE IT SMALLER
i + 1 β€” one more pack decided, on both branches. The pack index, not the total, is what guarantees progress.
3 Β· CALL ITSELF + COMBINE
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))
Prune only with a reason. β€œtotal > target” is safe because every price is positive. Allow negative prices and the same line becomes a bug. Other provable prunes: for exactly-K selections, stop if you already picked more than K, or if picked + remaining < K. Search size reminder: subsets have up to 2N leaves, permutations up to N! β€” small constraints are often the contest telling you exhaustive search is intended.

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.

❓ THE QUESTION FIRST

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
Why this section: this is the exact machinery of Word Hunt (2023 J5) β€” and its mirror image is Harvest Waterloo (2024 J5), where visited must never be undone. Knowing which of the two you are writing is half the problem.
β–Ά How to read the walkthrough β€” three views, moving together: left, the code, lit line = running now. Right, the call tree: every 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
1 Β· BASE CASE
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).
2 Β· MAKE IT SMALLER
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.
3 Β· CHOOSE Β· EXPLORE Β· UNDO
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

Taskvisited means…Undo?
Count all non-repeating paths (Β§5)used in this pathYes β€” unmark on exit
Reachability / flood fill (Harvest)already processed, everNever
Do not memoize this counter on (r, c). Two calls at the same cell can have different visited sets, hence different futures β€” the state is not just the position. The β€œcache only when the full state determines the answer” test from Β§2 fails here. (And if you need the shortest path, that is normally a BFS job, not backtracking.)

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.

❓ THE QUESTION FIRST

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.

Why this section: no stack, no counting β€” just decomposition. If a student can say β€œa level-L fractal is five smaller level-(Lβˆ’1) pieces”, they can write the recursion. Use the buttons and watch the bump grow bumps.

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.

  1. Define the state in words, and exactly what the function returns.
  2. Base cases: success and failure β€” including empty inputs where allowed.
  3. Legal next choices: list them; check every choice changes the state (progress!).
  4. Ownership: what belongs to one call, and what shared data needs an undo.
  5. Uniqueness: convince yourself every valid answer is produced exactly once. Prune only with a proof.
  6. Size check: estimate the search (2N? N!? depth?) and test the smallest, impossible, and repeated-value cases.

Common mistakes β€” the wall of shame

🚫 Missing return. Calling a helper is not returning its value. count_sets(...) on its own line computes β€” and throws away.
πŸ” No progress. Passing the same state again = infinite recursion = a stack overflow with extra steps.
0️⃣ Wrong base count. A completed valid choice usually contributes 1, not 0 (routes(0), the goal cell, the finished string).
πŸ”€ Counting the wrong thing. Subsets ignore order; permutations count it. Decide which problem you are in.
🧹 Shared-state leak. Forgetting to pop the path, unmark the cell, or free the used flag poisons every later branch.
πŸ—„οΈ Caching a lie. Memoize only when the full state determines the answer β€” the grid path counter (Β§5) is the classic counterexample.
Ready for the real problems? The practice page walks six past CCC problems with this exact machinery: Word Hunt (2023 J5), Pi Day (2015 J5), Rule of Three (2019 J5), Fractals (2004 J5), Harvest Waterloo (2024 J5), and Escape Room (2020 J5/S2).