The recursion notebook / Python 3
One line. One call.
A clearer picture.
Recursion is easier to follow when you can see what each call is doing. Step through three Python examples, watch values change, and follow the work down the stack and back up.
- 01Predict
What will the highlighted line do?
- 02Step
Execute it and watch the state change.
- 03Inspect
Select any stack frame to see its values.
A smaller version of the same problem
Move the tower. Keep the rules.
Move every disk from A to C, using B as a spare. Move one disk at a time, and never put a larger disk on a smaller one.
Base casen == 1: print one move and return.
Smaller problemMove n - 1 disks.
Then returnResume the caller where it paused.
Recursion & backtracking
Find a route from S to G.
Try right, down, left, and up. Mark each visited cell in the grid itself. Return True when you reach the end, or False when a branch fails.
Stop a branchA wall (1) or an already visited cell (3).
SuccessAt the goal, return True.
BacktrackReturn False; visited marks stay.
A choice can be legal and still lead nowhere
Solve Sudoku by trying and undoing.
Fill empty cells in row-major order. Try numbers 1–9, reject row, column, and box conflicts, then recurse. If the remaining puzzle fails, erase the trial number and try again.
Base caseEvery initially empty cell is filled.
ConstraintsNo repeated digit in a row, column, or 3×3 box.
UndoReset a trial cell to 0 after a failed child call.
Program state
Disk numbers show size. Peg lists run from bottom to top.
Printed coordinates: (y, x), or (row, column), starting at 0. Enable editing to toggle walls. Arrow keys move between cells; Enter or Space toggles a wall. Start and goal stay fixed.
Dark digits are fixed givens. Green cells are solver placements. The outlined cell belongs to the active call. A legal trial can still require backtracking later.
Preparing the example…
Python source
→ Highlighted line executes on the next step.
Call stack
Newest call at the top. Select a frame to inspect it.
Variables
Trace console
Most recent transitionsPython output
This is a line-by-line teaching simulation of the Python functions, not an editable Python interpreter. Back and the slider replay recorded states. The downloadable scripts run in Python 3 without extra packages.
The instructor’s recursive example
Three jobs, one function.
For n greater than 1, move n − 1 disks onto the auxiliary rod, print the move of disk n to the destination, then move the smaller tower onto it. At n == 1, print the move and return.
Each call has its own n, source, destination, and auxiliary. The Python function prints instructions; the rods and move log are visual aids added by this page.
For positive n, the number of moves is 2ⁿ − 1. Time is O(2ⁿ), and recursive stack space is O(n). The supplied function requires n ≥ 1.
Instructor’s iterative comparison (reference code)
This is the supplied iterative code, included in the download. Its src, aux, and des variables are not used by the fixed rod-pair logic, so swapping them has no effect. It finishes on B for odd disk counts and C for even counts. The recursive example above always targets C. Playback traces the recursive version.
Pause & predict
Follow the rod roles.
With 3 disks, what is the first move?
Disk 1 from A to C. Follow the calls until n == 1 and inspect source and destination.
Why is there no n == 0 call?
The n == 1 case prints and returns before either recursive call.
How many moves do 4 disks need?
15: seven moves, one largest-disk move, then seven more.
What does the function return?
None. The base case returns explicitly, while larger calls return implicitly after their last child finishes. The useful output is printed.
The instructor’s maze example
A return tells the parent what to try next.
mazeSearch(grid, x, y) accesses grid[y][x]. Values mean 0 open, 1 wall, 2 end, and 3 visited. An open cell is printed and marked 3 before searching right, down, left, then up.
The or expression short-circuits: once a child returns True, later directions are skipped. False lets the parent continue. Visited marks are never erased; they include unsuccessful branches and do not identify a saved solution path.
There is no separate visited collection, but the grid does remember visits. This matches the newly supplied code. The homework flood-fill solution is not included.
The supplied horizontal boundary uses len(grid), so this example and editor use a square 6×6 grid. For rectangular grids, the horizontal bound would need the row width. The search finds a route, not necessarily the shortest, in O(R × C) time and worst-case stack space.
Pause & predict
Follow a branch down and back up.
Why mark a cell before searching its neighbors?
Returning to that cell encounters 3 and returns False, preventing cycles.
What changes when all directions fail?
The function returns False. Its cell was already marked 3 and stays that way.
What happens at the end?
The end stays 2. The function prints its position and returns True, which travels back through the waiting calls.
What does the no-route layout return?
False. All reachable open cells are marked 3; the unreachable end remains 2.
Connect the code to the idea
Place. Recurse. Undo.
The list empty is prepared before the traced function starts. It contains every initially empty cell in row-major order. Each call gets its own index, row, col, and candidate number. All calls share board and empty.
A candidate must pass three checks: its row, its column, and its 3×3 box. list(zip(*board)) groups the board by columns. Integer division locates the box’s top-left corner.
Passing these checks only makes the choice locally legal. The recursive call tests whether the remaining cells can be filled. If it returns False, the parent clears its trial and continues the loop. Exhausting all nine numbers returns False again.
The example assumes a valid 9×9 board with non-conflicting givens. It finds the first solution, not all solutions, and does not establish uniqueness. With E empty cells, a loose upper bound is O(9ᴱ) search time and O(E) recursive stack space; constraint checks prune many branches. The browser uses small teaching puzzles to keep the complete trace manageable.
Pause & predict
Watch a choice travel down the stack.
Why does a locally legal number sometimes get erased?
It can prevent a later cell from accepting any number. When that deeper call returns False, its parent undoes the choice and tries the next candidate. Use “Watch it backtrack” to see three such reversals.
Why does each frame have a different index?
Each call works on a different entry in the same empty list. Passing index + 1 gives the child a new integer without changing the parent’s index.
What does resetting the cell to zero do?
Zero represents an empty cell. Resetting it restores the board to the state before that trial so the next candidate is tested fairly. The original givens are never changed.
Does a solved board prove the puzzle has one solution?
No. This algorithm stops at the first completed board. Establishing uniqueness requires continuing the search and checking for another solution.
Keep exploring
Take the Python with you.
Download an example, save it in a folder, and run it in your terminal. The script includes its sample input and prints the result. Change the disk count or the maze and predict the output before running it again.
The downloaded maze starts with the original “Instructor’s 6×6 example” layout. Your browser edits are exploratory and are not saved into that file. The Sudoku download uses the “Nine missing numbers” example.
python tower_of_hanoi.py
python maze.py
python sudoku.pyDownload HanoiDownload mazeDownload Sudoku