Tower of Hanoi
A medium Recursion problem included in Apna College, Love Babbar 450. Below: the roles whose interviews prioritise this topic, and how to practise it.
- Topic
- Recursion
- Sheets
- 2
- Core for
- 11 roles
- Platform
- GeeksforGeeks
The problem
Given the number of disks, return the sequence of moves to solve the Tower of Hanoi puzzle, moving all disks from the source rod to the destination rod using an auxiliary rod.
Example 1
- Input
- n = 3
- Output
- ["A->C", "A->B", "C->B", "A->C", "B->A", "B->C", "A->C"]
- Why
- For 3 disks, the minimum number of moves is 2^3 - 1 = 7.
Example 2
- Input
- n = 1
- Output
- ["A->C"]
- Why
- For 1 disk, simply move it from source to destination.
Constraints
- 1 <= n <= 20
How to think about it
Updated 2026-09-09The largest disk cannot move until every disk above it is completely out of the way. This forces exactly one sequence of operations: move the top n - 1 disks to the spare rod, transfer the bottom disk to its target, and then move the n - 1 stack on top of it. The problem reduces directly to two calls of size n - 1.
Approaches, worst first
Three-step divide and conquer
time O(2^n) · space O(n)
Recurse to transfer n - 1 disks from source to auxiliary, record the direct move of the largest disk, then recurse to transfer the n - 1 disks from auxiliary to destination. Every single move made is necessary, achieving the provable minimum of 2^n - 1 moves.
Iterative peg cyclingWrite this one
time O(2^n) · space O(1)
Drop the recursion entirely: make 2^n - 1 passes, and on pass k move the smallest disk one step around a fixed cycle of pegs, then make the single legal move that does not involve it. Same move count, constant extra memory, and far harder to convince yourself is correct, which is why the recursion is the one to write.
Where people lose marks · 2
- Swapping the destination and auxiliary peg roles in the second recursive step. The first call parks the stack on the auxiliary peg; the second must pull from auxiliary to target.
- Generating strings in memory for high n. While n <= 20 fits well within limits, allocating 2^20 moves requires over a million array elements and can exhaust memory if accumulated naively.
The theory behind it
Recursion — the ground this problem stands on. All Recursion problems
What Recursion is
Recursion is a nesting doll that opens to reveal an identical smaller doll inside. In programming, a function solves a substantial problem by delegating smaller versions of the exact same question to fresh invocations of itself. Each invocation operates on shrunken input until hitting an irreducible foundation called a base case, which returns an immediate answer and permits the waiting cascade to resolve backwards.
When to reach for it
Reach for recursion when a problem possesses self-similar subproblems, such as traversing branched tree structures, exploring graph pathways, or generating combinations. Phrases asking for all permutations, subset generation, exhaustive maze navigation, or hierarchical file system traversals signal recursive decomposition. It is natural whenever the answer to a large instance depends on assembling identical solutions for smaller subsets.
How the pattern works
Structure every recursive method around two mandatory stages: the termination stop and the shrinking recurrence. Write the base condition first so the function exits before attempting further execution. Next, trust the recursive call to return valid answers for smaller inputs without mentally unwinding every level at once. Pass accumulation state forward through parameters, or combine child return values on the ascent phase once deeper calls return.
What each operation costs
| Operation | Time |
|---|---|
| call stack memory allocation per frame | O(d) |
| traversal of branching recursive call tree | O(b^d) |
| single branch linear recursive unwind | O(n) |
What usually goes wrong with Recursion
- Omitting a base case or writing a condition that input values leap over without triggering, triggering fatal call stack overflow crashes.
- Modifying shared mutable containers across sibling branches without undoing edits on backtracking steps, contaminating alternative search paths.
- Recomputing duplicate subproblems inside branching calls without memoizing past returns, causing execution times to explode exponentially.
Which roles need this problem
Recursion is a core topic for these 11 roles — if you're targeting one of them, this problem is early in your path, not optional.
Secondary for 5 more roles, including SDE / Backend Engineer, Full-Stack Developer, Security Engineer.
Companies that have asked it
Tags taken from the problem's own GeeksforGeeks page — not a copied list.
Track this in your role's order
Pick your target role and all 370 problems — including this one — resequence to what that interview actually asks. Free.
Start freeMore Recursion problems
Problem set and role mapping as of .