Tower of Hanoi Solver will soon be available as a
Google Workspace Marketplace Add-on.
For transparency and compliance:
For transparency and compliance:
When I first encountered recursion in my first-year Computer Science course at UC Berkeley, I remember feeling completely lost. The Tower of Hanoi felt like a trick: how could a solution even begin if every step depended on solving a smaller one first?
I took CS 3: Introduction to Symbolic Programming with Oliver Grillmeyer, who patiently helped us trace how pegs dynamically switch roles — source becomes helper, helper becomes target — and showed us that recursion isn’t magic. It’s structure. Still, it took me years to feel that structure rather than follow it blindly.
Understanding recursion, for me, was itself a recursive process: breaking the confusion into smaller, solvable questions. One insight led to another, and eventually something resembling clarity appeared.
🧱 From Idea to Interactive Simulation
Many years later — as an MYP Design teacher — I decided to revisit Tower of Hanoi, but this time through the lens of pedagogy. Could I help students not only solve the puzzle but see recursion as it unfolds?
Together with ChatGPT, I built a full Tower of Hanoi simulator inside Google Sheets, powered entirely by Apps Script. What made the project possible was not raw code, but a design-first conversation with AI:
What should students see? How should each move feel? How can the UI help build computational intuition? Once the experience was clearly mapped out, scripting followed naturally.
🛠️ From Merged Disks to Painted Pegs
At first, I used merged cells to represent disks: larger disks spanned more columns, smaller disks fewer, all centered on pegs. It looked great — until I tried to move them.
Each step required breaking and re-merging cells dynamically. It was slow, fragile, and unsustainable.
So I pivoted: instead of merged cells, I painted rectangular blocks of adjacent cells, styled with consistent spacing and color. This approach:
- Simplified disk creation and movement
- Improved performance
- Made animation smooth and glitch-free
✅ Core Features
Here’s what the final simulator includes:
- 📐 Tower rendered in a dynamic grid, adjustable from 1 to 10 disks
- 🎨 Branded disk colors (hex-coded palette)
- 🧱 “Create Tower” button builds the stack interactively
- 🔁 “Solve Tower” animates the recursive steps live
- 🛑 Kill Switch (Pause) checkbox to stop long simulations
- 🧭 Sidebar UI with dropdown, buttons, and color-coded disk count
- 📖 Instruction dialog, with zoom-out tips and clear guidance
- 🔧 Gridline toggle, to switch between aesthetic and structural views
- 📊 Logging, toast messages, and pegs that visually rebuild in real time
Watch recursion come to life, one move at a time.
🔁 Recursion, Visualized Step-by-Step
(Quick terminology: the source peg is the starting peg where all disks begin, the auxiliary peg is a temporary helper peg, and the target peg is where all disks should end up.)
Once the interface worked, I implemented recursion faithfully and visibly.
For those new to Tower of Hanoi: solving it recursively always follows the same structure:
- Move n−1 disks from source to auxiliary
- Move the nth (largest) disk to target
- Move n−1 disks from auxiliary to target
With every recursive call, the roles of the pegs rotate. This is the key to recursive thinking — the problem doesn’t just repeat, it reorganizes. In our code, I didn’t pre-generate moves. Each move happened only when its subproblem had been resolved. The simulation feels like how humans approach the problem — slowly, logically, recursively.
🧠 Recursive Move Breakdown for 1–11 Disks:
For 1 disk:
– Only 1 move: Source → Target
– T(1) = 1
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
For 2 disks:
– To move 2 disks:
- Move 1 disks from Source to Helper → T(1) moves
- Move disk 2 to Target → 1 move
- Move 1 disks from Helper to Target → T(1) moves
T(2) = T(1) + 1 + T(1) = 2×T(1) + 1
= 2×(2 – 1) + 1
= 2 + 1 = 3
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
For 3 disks:
– To move 3 disks:
- Move 2 disks from Source to Helper → T(2) moves
- Move disk 3 to Target → 1 move
- Move 2 disks from Helper to Target → T(2) moves
T(3) = T(2) + 1 + T(2) = 2×T(2) + 1
= 2×(4 – 1) + 1
= 6 + 1 = 7
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
For 4 disks:
– To move 4 disks:
- Move 3 disks from Source to Helper → T(3) moves
- Move disk 4 to Target → 1 move
- Move 3 disks from Helper to Target → T(3) moves
T(4) = T(3) + 1 + T(3) = 2×T(3) + 1
= 2×(8 – 1) + 1
= 14 + 1 = 15
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━For 5 disks:
– To move 5 disks:
- Move 4 disks from Source to Helper → T(4) moves
- Move disk 5 to Target → 1 move
- Move 4 disks from Helper to Target → T(4) moves
T(5) = T(4) + 1 + T(4) = 2×T(4) + 1
= 2×(16 – 1) + 1
= 30 + 1 = 31
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━For 6 disks:
– To move 6 disks:
- Move 5 disks from Source to Helper → T(5) moves
- Move disk 6 to Target → 1 move
- Move 5 disks from Helper to Target → T(5) moves
T(6) = T(5) + 1 + T(5) = 2×T(5) + 1
= 2×(32 – 1) + 1
= 62 + 1 = 63
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━For 7 disks:
– To move 7 disks:
- Move 6 disks from Source to Helper → T(6) moves
- Move disk 7 to Target → 1 move
- Move 6 disks from Helper to Target → T(6) moves
T(7) = T(6) + 1 + T(6) = 2×T(6) + 1
= 2×(64 – 1) + 1
= 126 + 1 = 127
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━For 8 disks:
– To move 8 disks:
- Move 7 disks from Source to Helper → T(7) moves
- Move disk 8 to Target → 1 move
- Move 7 disks from Helper to Target → T(7) moves
T(8) = T(7) + 1 + T(7) = 2×T(7) + 1
= 2×(128 – 1) + 1
= 254 + 1 = 255
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
For 9 disks:
– To move 9 disks:
- Move 8 disks from Source to Helper → T(8) moves
- Move disk 9 to Target → 1 move
- Move 8 disks from Helper to Target → T(8) moves
T(9) = T(8) + 1 + T(8) = 2×T(8) + 1
= 2×(256 – 1) + 1
= 510 + 1 = 511
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━For 10 disks:
– To move 10 disks:
- Move 9 disks from Source to Helper → T(9) moves
- Move disk 10 to Target → 1 move
- Move 9 disks from Helper to Target → T(9) moves
T(10) = T(9) + 1 + T(9) = 2×T(9) + 1
= 2×(512 – 1) + 1
= 1022 + 1 = 1023
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━For 11 disks:
– To move 11 disks:
- Move 10 disks from Source to Helper → T(10) moves
- Move disk 11 to Target → 1 move
- Move 10 disks from Helper to Target → T(10) moves
T(11) = T(10) + 1 + T(10) = 2×T(10) + 1
= 2×(1024 – 1) + 1
= 2046 + 1 = 2047
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
🧪 Proof by Induction: Why T(n−1) = 2ⁿ⁻¹ − 1
We want to prove:
T(n−1) = 2^(n−1) − 1
Which means: moving (n−1) disks takes that many moves.
✅ Base Case: n = 1
(n−1) = 0 disks → takes 0 moves
2^0 − 1 = 1 − 1 = 0 ✅
✅ Case n = 2
(n−1) = 1 disk → takes 1 move
2^1 − 1 = 2 − 1 = 1 ✅
So to move 2 disks:
– Move 1 to helper → 1 move
– Move largest to target → 1 move
– Move 1 to target again → 1 move
Total: 1 + 1 + 1 = 3 ✅
🔁 Inductive Step:
Assume T(n−2) = 2^(n−2) − 1 (true for smaller cases)
Then T(n−1) =
= 2 × T(n−2) + 1
= 2 × (2^(n−2) − 1) + 1
= 2^(n−1) − 2 + 1
= 2^(n−1) − 1 ✅
So we’ve shown that the number of moves for (n−1) disks is 2^(n−1) − 1, just as expected.
And once we’re confident that (n−1) disks require 2^(n−1) − 1 moves,
then moving n disks requires:
– 2 × (2^(n−1) − 1) [to move n−1 disks twice]
– + 1 move for disk n itself
Which gives:
2 × (2^(n−1) − 1) + 1 = 2^n − 2 + 1 = 2^n − 1 ✅
If you read this far, nice work!
💬 Final Reflection
Building this simulator with ChatGPT revealed something profound:
Recursion isn’t just a computer science trick. It’s a way of thinking. A way of trusting that if you solve the smallest pieces with care, the larger problem will resolve itself — naturally, and beautifully.
#DesignThinking #ComputationalThinking #GoogleAppsScript #EdTech #MYPDesign #TeachingInnovation #TowerOfHanoi #Recursion #AIinEducation