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 BFree7 lessons5 h4 chapters2,187 XPCoding · Intermediate+150 XP

0 of 7 done

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.

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

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

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

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

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

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

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

  1. Calls that call themselvesA 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.
  2. Base casesWhat 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

  1. Tree walksA 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.
  2. PermutationsEvery 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

  1. BacktrackingChoose, 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.
  2. MemoizationWhy 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

  1. Boss: a Sudoku solverThe 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.