Source: https://mokxi.com/teachers/plans/recursion-and-backtracking
Updated: 2026-11-19

Lesson plan

# Recursion and backtracking lesson plan

Functions that call themselves, on a Raspberry Pi: the call stack, base cases and the real depth limit, tree walks, permutations, backtracking through N queens and a maze, memoization, and a Sudoku solver.

4 chapters, 7 lessons, about 5 hours, on the Raspberry Pi 4 Model B. Every lesson runs in the browser, with nothing to install.

Start a class from this course

The unit

## Objectives and materials

### By the end, students can

- The call stack, base cases and the limit every recursion lives under.
- Walk a cave and a folder tree, and list every order and every subset.
- Backtrack out of dead ends, and never answer the same question twice.
- A Sudoku solver with traffic lights.

### Materials for the whole unit

- Half breadboard
- LED x 2
- Pushbutton
- Raspberry Pi 4 Model B
- Resistor x 2
- Traffic light module

Every part is already on the simulator’s bench, so there is nothing to buy or hand out. The counts are the most any one lesson uses, if you build it on real breadboards too.

Chapter 1. About 1 h 20 min

## Calls that call themselves

The call stack, base cases and the limit every recursion lives under.

Lesson | Time | What students do

Calls that call themselves A function that calls itself: a countdown, the call stack drawn as indentation, factorial with big integers, a Sierpinski triangle printed as text, and an LED blinked by recursion. | 40 min

- A countdown that calls itself
- See the call stack
- Return a value: factorial
- A fractal printed as text
- Blink an LED by recursion

Base cases What happens with no base case (the engine's real depth limit and its RuntimeError), a cave with a floor, shrinking toward the base case fast, and when a loop beats recursion. | 40 min

- A cave with no floor
- Give it a floor
- Measure the limit
- Shrink fast
- When a loop wins

### Materials

- Half breadboard
- LED x 2
- Raspberry Pi 4 Model B
- Resistor x 2

### Check for understanding

Each student finishes "Base cases" on their own, without opening the hints. The simulator checks 5 of its 5 steps as they go.

Then ask each one to explain, in a sentence or two, the last thing it asked of them: "When a loop wins".

Chapter 2. About 1 h 20 min

## Trees and orders

Walk a cave and a folder tree, and list every order and every subset.

Lesson | Time | What students do

Tree walks A cave of tunnels as a tree: print it, count its rooms, find its deepest point and the route to a hidden grotto, then walk the Pi's own folders with the same five lines. | 40 min

- A cave is a tree
- Count the rooms
- Find the deepest point
- Find the route
- The Pi's folders are a tree too

Permutations Every order of a crew: permutations by recursion, why n! grows so fast, decoding a scrambled alien signal, packing a rover with the include-or-skip pattern, and checking your work against itertools. | 40 min

- Every order of three
- Count them: n factorial
- Decode the alien signal
- Include it or skip it
- Check against itertools

### Materials

- Half breadboard
- LED x 2
- Raspberry Pi 4 Model B
- Resistor x 2

### Check for understanding

Each student finishes "Permutations" on their own, without opening the hints. The simulator checks 5 of its 5 steps as they go.

Then ask each one to explain, in a sentence or two, the last thing it asked of them: "Check against itertools".

Chapter 3. About 1 h 30 min

## Search smart

Backtrack out of dead ends, and never answer the same question twice.

Lesson | Time | What students do

Backtracking Choose, explore, unchoose: N queens on a chessboard, counting every solution up to eight, measuring what pruning saves, flashing an LED on every backtrack, and escaping a sea cave maze. | 45 min

- Four queens
- Count every solution
- What pruning saves
- Eight queens
- See it backtrack
- Escape the sea cave

Memoization Why naive Fibonacci makes 21,891 calls for fib(20), a dictionary that cuts it to 39, functools.lru_cache, and two classic counting problems solved in a blink: rover routes on a grid and making change. | 45 min

- The slow way
- Watch it explode
- Remember the answers
- Let functools do it
- Rover routes
- Make change

### Materials

- Half breadboard
- LED x 2
- Raspberry Pi 4 Model B
- Resistor x 2

### Check for understanding

Each student finishes "Memoization" on their own, without opening the hints. The simulator checks 6 of its 6 steps as they go.

Then ask each one to explain, in a sentence or two, the last thing it asked of them: "Make change".

Chapter 4. About 55 min

## Boss

A Sudoku solver with traffic lights.

Lesson | Time | What students do

Boss: a Sudoku solver The boss: a complete Sudoku solver by backtracking, with a rule checker, a full validity proof, a count of the work done, traffic lights for thinking, solved and impossible, and a guard against broken puzzles. | 55 min

- Load the puzzle
- The rules as a function
- The solver
- Prove it
- Lights for the crowd
- A broken puzzle
- What you beat

### Materials

- Pushbutton
- Raspberry Pi 4 Model B
- Traffic light module

### Check for understanding

Each student finishes "Boss: a Sudoku solver" on their own, without opening the hints. The simulator checks 7 of its 7 steps as they go.

Then ask each one to explain, in a sentence or two, the last thing it asked of them: "What you beat".

Your class

## Teach this unit as a class

Start a class from this course and its 7 lessons are assigned in one go, in order. Students join with a six-character code or printed login cards, and each one’s work comes back to you.

The class tools are free for 30 days for one class of up to 20 students, with no card. The lessons themselves are free either way.

Start a class from this course See the demo class

More units

## Other lesson plans

Electronics basics 20 lessons, about 10 h. Embedded on the Arduino Uno 16 lessons, about 12 h. Embedded on the ESP32-C3 13 lessons, about 11 h. Embedded on the Raspberry Pi Pico 7 lessons, about 6 h. Build your own fight stick 5 lessons, about 4 h. Embedded on the STM32F411 6 lessons, about 6 h. C++ on a board 13 lessons, about 10 h. Digital logic and memory 4 lessons, about 4 h. Interactive devices on the Uno 9 lessons, about 8 h. From gates to a computer 23 lessons, about 16 h. Build a claw machine 8 lessons, about 6 h. Every unit All the courses as ready-made units, on the teachers page.
