Source: https://mokxi.com/learn/path/recursion-and-backtracking
Updated: 2026-11-20

All paths

# Recursion and backtracking

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.

Raspberry Pi 4 Model B Free 7 lessons 5 h 4 chapters 2,187 XP Coding · Intermediate +150 XP

0 of 7 done

Start the course free Calls that call themselves Lesson plan for teachers

What you will build

## 3 projects, built step by step

7 lessons in 4 chapters, about 5 hours on a simulated Raspberry Pi 4 Model B. Free, in your browser, every step checked by the simulator.

Chapter 1 project

### 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.
Open it in the simulator

Chapter 2 project

### 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.
Open it in the simulator

Chapter 3 project

### 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.
Open it in the simulator

The map

## Chapter by chapter

Each lesson opens when the one before it is done, and each chapter ends in a project.

Chapter 1

## Calls that call themselves

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

Open 205 XP

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

0 of 5 steps

Start What is in it

Project Locked 410 XP

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

0 of 5 steps

5 questions, graded as you go.

Chapter 2

## Trees and orders

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

Locked 205 XP

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

0 of 5 steps

Project Locked 410 XP

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

0 of 5 steps

4 questions, graded as you go.

Chapter 3

## Search smart

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

Locked 236 XP

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

0 of 6 steps

Project Locked 472 XP

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

0 of 6 steps

5 questions, graded as you go.

Chapter 4

## Boss

A Sudoku solver with traffic lights.

Locked 249 XP

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

0 of 7 steps

3 questions, graded as you go.

Syllabus

## Every lesson in the course

All 7 lessons, in order, each with what it covers. Any of them opens in the editor right away.

Chapter 1

### Calls that call themselves

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

Chapter 2

### Trees and orders

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

Chapter 3

### Search smart

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

Chapter 4

### Boss

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

Kits

## Build it on your bench too

Every lesson runs in the simulator with nothing to buy. When you want the real thing, these kits have the parts.

Have a kit already?

### Find your kit

Pick the starter kit you own and run every lesson in its manual with the same parts on the same pins.
See every kit

Questions

## About Recursion and backtracking

Is Recursion and backtracking free?

Yes. All 7 lessons of Recursion and backtracking are free and run in your browser, with nothing to install and no parts to buy before you start.

Do I need a real Raspberry Pi 4 Model B?

No. Every lesson runs on a simulated Raspberry Pi 4 Model B with its parts on the canvas, and the simulator checks each step as you go. When you want to build it for real, the same wiring and code work on a real board.

How long does Recursion and backtracking take?

About 5 hours: 7 lessons in 4 chapters, each one a few short steps. Your progress is kept, so you can stop after any lesson and pick up where you left off.

What will I build?

Each chapter ends in a project that puts it together: Base cases, Permutations and Memoization.

Where do I start?

With "Calls that call themselves", and each lesson builds on the one before it. New to circuits? Electronics basics is the course that starts from zero.
