Lessons and the learning game

Recursion and backtracking

Functions that call themselves, from a countdown to a Sudoku solver, on a Raspberry Pi 4, with the engine's real depth limit taught honestly.

The course

Recursion and backtracking is an intermediate Coding course in seven lessons, after Python from zero and Fix the bug. Most of it runs on the gallery's two-LED Pi build (red on GPIO17, yellow on GPIO27), and the boss uses the traffic light module. Every step is checked against what the Pi prints or what its pins do, and every number in the lessons is one the program really prints.

  1. Calls that call themselves: a countdown with no loop, the call stack drawn as indentation as it winds and unwinds, factorial with exact big integers (25! in full), a Sierpinski triangle printed as text, and an LED blinked five times by recursion.
  2. Base cases: a cave dive with no floor that overflows the stack, a base case that stops it, the measured depth limit (a little under 1,000 calls for a small function), exponentiation by squaring (2^100 in 8 calls) and why a straight line of work belongs in a loop.
  3. Tree walks: a cave of tunnels stored as nested tuples, printed as an outline, its 9 rooms counted, its deepest point found, a route to the glow worm grotto by depth-first search, then the Pi's own folders walked with the same pattern.
  4. Permutations: every order of a crew, n! counted up to 720, a scrambled alien signal decoded against a word set, rover loads packed with the include-or-skip pattern, and the result checked against itertools.permutations.
  5. Backtracking: N queens with choose, explore, unchoose; every solution counted from 4 to 8 (92 for the chessboard); 15,720 squares checked instead of 16 million boards; the yellow LED flashing on every backtrack; and a sea cave maze escaped.
  6. Memoization: naive Fibonacci's 21,891 calls for fib(20), a dictionary that cuts it to 39, functools.lru_cache with its hit and miss counts, 601,080,390 rover routes across a grid, and the 242 ways to make a dollar.
  7. Boss: a Sudoku solver: the finale.

The finale

The boss builds a complete Sudoku solver in about twenty lines. It loads a real puzzle, writes the rules as a function and tests it on one cell, then solves the grid by backtracking: find the first empty cell, try each digit that fits, solve the rest, and take the digit back if that fails. An independent check proves every row, column and box holds 1 to 9 (4,208 placements for this puzzle), the traffic lights show amber while it thinks and green when it is solved, and a guard turns the light red for a puzzle that breaks the rules before the solver wastes a moment on it.

What the Pi engine does differently

The Pi runs MicroPython 1.29, not CPython, and recursion is where that shows most:

  • Too deep a recursion raises RuntimeError: maximum recursion depth exceeded, or RuntimeError: pystack exhausted for a function with many locals. RecursionError, CPython's name, is not defined here. The lessons catch RuntimeError, which works on both, because CPython's RecursionError is a kind of RuntimeError.
  • The limit is stack memory, not a fixed count: about 980 calls for a tiny function, fewer for a bigger one. There is no sys.setrecursionlimit.
  • Dicts do not keep the order keys went in, so trees are stored as lists and tuples, and os.listdir and sets are sorted before printing.
  • str.ljust and str.rjust are missing, so padding is built with " " * count. Integers have no size limit, as in CPython.

Everything else in the course, functools.lru_cache, itertools and os, runs as it does on a real Pi.