Skip to content

Algorithm

The Tower of Hanoi Algorithm

One short function, and the clearest example of recursion in computer science. Run it below and watch every call it makes.

On this page
  1. The idea
  2. The algorithm
  3. A worked run, move by move
  4. Run it
  5. What to watch for
  6. The recursion tree
  7. Why it is correct
  8. The recurrence, solved properly
  9. Time and space complexity
  10. Without recursion
  11. From a position that is not the start
  12. Check yourself
  13. The algorithm in your language
  14. The words on this page
  15. Frequently asked questions

The Tower of Hanoi algorithm moves a stack of n disks from one tower to another in 2ⁿ − 1 moves, which is the fewest possible. It is almost always written recursively, because the puzzle is recursive: the problem of moving n disks contains two copies of the problem of moving n − 1, with a single move in between.

The idea

The largest disk is the only one that cannot go on top of anything, so start with it. It can only move when nothing is on top of it and nothing is on the tower it is going to — which means every other disk has to be stacked on the third tower. So the whole solution is three steps:

  1. Move the n − 1 smaller disks from the source to the spare tower.
  2. Move the largest disk from the source to the target.
  3. Move the n − 1 smaller disks from the spare onto the target.

Steps 1 and 3 are the same puzzle with one fewer disk, and a different tower playing the spare. Solve those the same way, and those inside them, until the stack to move is empty. If recursion itself is new to you, recursion, explained with Tower of Hanoi starts from the beginning.

Those three steps are a divide-and-conquer algorithm, which is where most courses file this puzzle. It divides the problem into two subproblems, conquers each by recursion, and combines them with the cheapest combine step there is — a single move. What it is not is a balanced divide: merge sort halves its input, and this takes one disk off. That single difference is why the Master Theorem cannot be used on it, which is the trap further down the page is about.

The algorithm

Written out, that is one function with two halves. The base case is the version it answers without calling itself — here n == 0, no disks to move, nothing to do — and the recursive case is everything else: the three lines that take the puzzle apart and hand the pieces back to the same function. Some versions stop at n == 1 instead and move the disk there; the moves are identical, and the version below keeps the move on a single line.

In the numbered form, with the towers named for the job each is doing in the call rather than by letter:

ALGORITHM TOH(n, source, target, spare)

  1. If n = 0, return. There is nothing to move.
  2. TOH(n − 1, source, spare, target) — move the top n − 1 disks out of the way. They are going to the spare, so the spare is this call's target, and the tower the largest disk is heading for is the one it has to keep clear.
  3. Move disk n from source to target. This is the only line that moves anything.
  4. TOH(n − 1, spare, target, source) — bring those n − 1 disks onto the target. They start from the tower that was the spare, and the tower every disk began on is now the one to keep clear.

A worked run, move by move

Here is that algorithm's answer for three disks, before running anything. Seven moves, seven boards, and the reason each move had to come when it did.

  1. Phase 1 · clear the way

    Disk 1, A to C. Disk 3 cannot move until the two disks on it are on B, and disk 2 cannot go to B while disk 1 is on top of it. So the smallest disk moves first, to C.

  2. Phase 1 · clear the way

    Disk 2, A to B. Disk 2 is uncovered now and B is empty, so it takes its place on the spare tower.

  3. Phase 1 · clear the way

    Disk 1, C to B. Disk 1 comes back down onto disk 2. Both small disks are stacked on B and disk 3 is free — which is the whole point of the first three moves.

  4. Phase 2 · the big disk crosses

    Disk 3, A to C. Nothing is on disk 3 and nothing is on C, so the largest disk crosses in a single move. It is the only one of the seven the outermost call makes itself.

  5. Phase 3 · rebuild on top

    Disk 1, B to A. The same three-move dance again, the other way round: B is the source now and A, where every disk started, is the spare. Disk 1 gets out of disk 2's way first.

  6. Phase 3 · rebuild on top

    Disk 2, B to C. Disk 2 crosses onto disk 3. It is legal because disk 3 is larger, which is the only condition that ever matters.

  7. Phase 3 · rebuild on top

    Disk 1, A to C. Disk 1 lands on the stack and the puzzle is solved in 7 moves — 2³ − 1, and the fewest possible.

The whole three-disk puzzle, one board per move, each shown as it stands once that move has been made — the shaded disk is the one that just landed. The seven moves fall into three groups: moves 1 to 3 carry the two small disks to B, move 4 is the largest disk crossing, and moves 5 to 7 bring the small disks back on top of it. Groups one and three are the same two-disk puzzle, which is exactly what the recursive function is doing when it calls itself twice.

Notice what moves 1 to 3 and moves 5 to 7 have in common: both are the two-disk puzzle, played between a different pair of towers. That is the recursion, visible in the output before the program is even running — and it is why the function below needs only one line that moves a disk.

Run it

The same seven moves again, this time with the program that produces them. Each step executes one line, and the call stack lists every call that has started and not yet finished. Try four or five disks: the number of calls doubles each time, and the stack grows by one.

hanoi(3, A, C, B)

Move 3 disks from A to C.

Nothing is running yet. The first step makes this call.

Step 0 of 43

Call stack

Depth 0 of 4 max

  1. Empty. Nothing has been called yet.

Pseudocode

procedure hanoi(n, source, target, spare)
    if n == 0 then
        return
    hanoi(n - 1, source, spare, target)
    move disk n from source to target
    hanoi(n - 1, spare, target, source)
end procedure

Moves

7 in all

Choose a row to jump the program to that move.

Every move the program makes for 3 disks
MoveDiskFromTo
11AC
22AB
31CB
43AC
51BA
62BC
71AC
All 15 calls, in the order the program makes them
  1. hanoi(3, A, C, B)depth 1 · makes move 4
  2. hanoi(2, A, B, C)depth 2 · makes move 2
  3. hanoi(1, A, C, B)depth 3 · makes move 1
  4. hanoi(0, A, B, C)depth 4 · n is 0 — returns at once
  5. hanoi(0, B, C, A)depth 4 · n is 0 — returns at once
  6. hanoi(1, C, B, A)depth 3 · makes move 3
  7. hanoi(0, C, A, B)depth 4 · n is 0 — returns at once
  8. hanoi(0, A, B, C)depth 4 · n is 0 — returns at once
  9. hanoi(2, B, C, A)depth 2 · makes move 6
  10. hanoi(1, B, A, C)depth 3 · makes move 5
  11. hanoi(0, B, C, A)depth 4 · n is 0 — returns at once
  12. hanoi(0, C, A, B)depth 4 · n is 0 — returns at once
  13. hanoi(1, A, C, B)depth 3 · makes move 7
  14. hanoi(0, A, B, C)depth 4 · n is 0 — returns at once
  15. hanoi(0, B, C, A)depth 4 · n is 0 — returns at once

What to watch for

  • The roles rotate. Tower B is the spare for the first call and the target for the one it makes. Every level of recursion relabels the three towers, and that relabelling is the whole trick.
  • The stack never gets deep. Three disks never have more than four calls running at once — one per disk count from 3 down to 0 — even though the program makes 15 calls in all.
  • Half the calls do nothing. Of those 15 calls, 8 are for zero disks and return at once. They are the price of the simplest possible base case.
  • The move line runs exactly 2ⁿ − 1 times. Seven, for three disks, across the 43 steps of the run.

The first of those is the hardest to catch while the program runs, because nothing on the board moves when it happens — only the names under the towers change. Here it is held still: the first call, the two beneath it on the way to move 1, and the call that brings the stack back.

  1. hanoi(3, A, C, B)

    The first call: move all 3 disks from A to C. That leaves B as the spare. Source A, target C, spare B.

  2. hanoi(2, A, B, C)

    Its first call. Disk 3 cannot move with disks 1 and 2 on it, and they cannot go to C, where disk 3 is heading. So B, the spare a moment ago, is the target, and C is the spare. Source A, target B, spare C.

  3. hanoi(1, A, C, B)

    One level down, the same swap again. To uncover disk 2, disk 1 goes to C, and B is the spare once more. Source A, target C, spare B.

  4. hanoi(2, B, C, A)

    Disk 3 has crossed. The root's second call brings disks 1 and 2 back from B on top of it, so B is the source now, and A, where every disk started, is the spare. Source B, target C, spare A.

hanoi(3, A, C, B) and three of the calls under it, in the order they run, each on the board as that call finds it. The shaded disks are the ones the call has to move. The towers stay where they are; only their names change. Every call hands its three towers down with two of them swapped — target and spare to the first call it makes, source and spare to the second — and that is all the relabelling there is.

The second is easier to doubt than to check, so here is the whole run with the stack's height at every step of it:

  • The run takes 44 steps and makes 15 calls in all.
  • The number of calls on the stack rises and falls between 0 and 4, and reaches 4 on 8 of those steps — every time a call with no disks to move starts and returns.
  • Depth 4 is n + 1 for n = 3, and no step of the run passes it.
Every step of the three-disk run, with the number of calls on the stack at that moment. The shape is wide because the work doubles with every disk added — 44 steps here, and 15 calls — and flat because the memory does not: the stack holds one call per disk count from 3 down to 0, so it touches 4 and stops. That gap between the width and the height is Θ(2ⁿ) time against Θ(n) space, drawn.

The recursion tree

Draw every call as a box under the call that made it and the program becomes a tree. Place each box above the number of the move it makes, and something else appears: reading the boxes from left to right gives the moves in order. With three disks, the first call's own move — the largest disk — is move 4, right in the middle, with the whole three-move solution for two disks on either side of it.

  1. Move 1: the call with n = 1, from A to C, moves disk 1.
  2. Move 2: the call with n = 2, from A to B, moves disk 2, between its two calls with n = 1.
  3. Move 3: the call with n = 1, from C to B, moves disk 1.
  4. Move 4: the call with n = 3, from A to C, moves disk 3, between its two calls with n = 2.
  5. Move 5: the call with n = 1, from B to A, moves disk 1.
  6. Move 6: the call with n = 2, from B to C, moves disk 2, between its two calls with n = 1.
  7. Move 7: the call with n = 1, from A to C, moves disk 1.
The seven calls of hanoi(3, A, C, B) that move a disk. Each call sits above the two it makes, and each is placed above the number of the move it makes — so the boxes, read left to right, are the solution in order. The eight calls with n = 0 are not drawn: one hangs under each side of every bottom box, and each returns without doing anything. Run the program above and this tree follows it: the running call is lit, the calls waiting on it are outlined, and each move number fills in as its move is made. Give the program four or five disks and the tree is redrawn at that size.

That symmetry holds at every size. Move 2ⁿ⁻¹ is always the largest disk crossing, and the moves before and after it are the (n − 1)-disk solution played twice, with the roles of two towers swapped. It is why a move list of any length is readable at a glance, and why the five-disk solution is the four-disk one, a single move, and the four-disk one again.

Why it is correct

The algorithm never breaks a rule and always finishes, and the proof is short enough to give in full. The claim, for every n, is:

If the top n disks of the source tower are disks 1 to n, and every disk anywhere else is larger than n, then hanoi(n, source, target, spare) moves those n disks onto the target, legally, and touches nothing else.

For n = 0 there is nothing to move and nothing is touched.

Suppose the claim holds for n − 1. Then each of the three steps is legal:

  1. The first call moves disks 1 to n − 1 onto the spare. It is entitled to: every other disk, disk n included, is larger than n − 1.
  2. Disk n moves to the target. Nothing is on top of it now, and the target holds only disks larger than n.
  3. The second call moves disks 1 to n − 1 from the spare onto the target. Entitled for the same reason — disk n, now under them, is larger.

All n disks are on the target and nothing else moved. By induction the claim holds for every n, and the full puzzle is the case where the source holds every disk.

  1. Assumedthe claim for n − 1

    The hypothesis says a call on n − 1 disks moves them wherever it is told, legally, and touches nothing else. Applied here, it carries disks 1 to n − 1 off the source and onto the spare. It is entitled to: every disk it could land on — disk n included — is larger than any it is carrying.

  2. Proved hereone legal move

    This is the only step the proof has to argue for itself, and it is a single move. Disk n is uncovered, because the step before cleared it. The target holds nothing but disks larger than n, because everything smaller is on the spare. So the move is legal.

  3. Assumedthe claim for n − 1, again

    The same hypothesis, used a second time, brings disks 1 to n − 1 from the spare onto the target. Legal for the same reason as before: disk n is now underneath them and is larger than all of them. All n disks are on the target and nothing else has moved — which is the claim for n.

The inductive step, and the reason the proof is four sentences long. Two of the three panels do no new work at all — they are the hypothesis for n − 1 being spent, once in each direction. Only the middle panel has to be argued, and it is one move. That is what induction buys: n disks cost exactly one new idea more than n − 1 did, and the base case n = 0 costs none, because there is nothing to move.

The recurrence, solved properly

Let T(n) be the number of moves the algorithm makes for n disks. The function makes two calls on n − 1 disks and one move of its own, and makes no moves at all when there are no disks:

T(n) = 2 · T(n − 1) + 1T(0) = 0

To solve it, substitute the recurrence into itself and look for the pattern. This is called unrolling, or telescoping:

T(n) = 2T(n − 1) + 1  = 2(2T(n − 2) + 1) + 1 = 4T(n − 2) + 3  = 4(2T(n − 3) + 1) + 3 = 8T(n − 3) + 7  = 2ᵏ · T(n − k) + (2ᵏ − 1)after k substitutions. Take k = n:T(n) = 2ⁿ · T(0) + 2ⁿ − 1 = 2ⁿ − 1

Spotting a pattern is not proving it, so confirm it by induction. T(0) = 0 = 2⁰ − 1. And if T(n − 1) = 2ⁿ⁻¹ − 1, then T(n) = 2(2ⁿ⁻¹ − 1) + 1 = 2ⁿ − 2 + 1 = 2ⁿ − 1. The closed form is exact for every n.

There is a third route, and it is a picture you have already seen. The recursion tree above is a full binary tree: the root moves n disks, the two calls under it move n − 1 each, the four under those move n − 2, and so on. Depth k therefore holds 2ᵏ calls, the last level is depth n − 1, and every one of those calls makes exactly one move. Add up the levels and the count falls out as a geometric series:

T(n) = 1 + 2 + 4 + ⋯ + 2ⁿ⁻¹n terms, each twice the one before:  = 2ⁿ − 1

Three methods — unrolling, induction and the tree — and one answer. Which is worth knowing, because there is a fourth that is offered constantly and is wrong.

This is not a Master Theorem recurrence

A common answer — including in some widely copied tutorials — solves this with the Master Theorem. It does not apply.

  • The Master Theorem is for T(n) = aT(n/b) + f(n) with b > 1: each subproblem is a fraction of the original, as in merge sort.
  • This recurrence is T(n) = 2T(n − 1) + 1: the subproblem is one disk smaller, not a fraction smaller, so there is no b to plug in.

Recurrences like this have their own subtract-and-conquer result: when T(n) = aT(n − b) + f(n) with a > 1 and f a polynomial, T(n) grows at most like aⁿᐟᵇ times that polynomial. It agrees with the answer above — but unrolling is shorter than remembering it.

The same arithmetic counts the calls. Every call on n > 0 disks makes two more, so there are C(n) = 2C(n − 1) + 1 calls with C(0) = 1, which unrolls to 2ⁿ⁺¹ − 1. That is 2ⁿ − 1 calls that move a disk, plus 2ⁿ that return straight away.

Time and space complexity

Each call does a constant amount of work besides its two recursive calls, so the running time is proportional to the number of calls: Θ(2ⁿ). No cleverer algorithm can beat that, because the output itself is 2ⁿ − 1 moves long — and 2ⁿ − 1 is a proven minimum, not just the best anyone has found. The proof that no solution is shorter is on its own page: why the minimum is 2ⁿ − 1.

Memory is a different story. The calls do not all exist at once: a call finishes before its sibling starts, so the stack only ever holds one call per level, from n down to 0. The space used is Θ(n) — sixty-five stack frames for the sixty-four disks of the legend, which any computer holds without noticing. Time is what runs out: 18,446,744,073,709,551,615 moves at a billion a second is still 584 years.

That number is the legend's, and the legend is younger than it sounds. A temple where priests move sixty-four golden disks, the world ending when they finish, first appears in print in 1884 — in an article advertising a puzzle that had gone on sale in Paris the year before, under the name of a professor who did not exist. At the monks' rate of one move a second the world has 585 billion years left, which is about forty times the present age of the universe. The mathematician behind both the puzzle and the story was Édouard Lucas, who proved 2¹²⁷ − 1 prime by hand and then died at 49 of an infected cut from a plate a waiter dropped at a banquet.

RecursiveIterative
Moves made2ⁿ − 12ⁿ − 1
Work done2ⁿ⁺¹ − 1 calls2ⁿ − 1 loop passes
TimeΘ(2ⁿ)Θ(2ⁿ)
Extra memoryΘ(n) call stackΘ(n) — the towers, or just an n-bit move counter

Put numbers into those formulas and the two kinds of cost part company. Each extra disk slightly more than doubles the moves and the calls, and adds a single frame to the deepest the stack gets:

DisksMovesCallsDeepest stackAt a billion moves a second
371547 nanoseconds
41531515 nanoseconds
53163631 nanoseconds
101,0232,047111 microsecond
201,048,5752,097,151211 millisecond
324,294,967,2958,589,934,591334 seconds
6418,446,744,073,709,551,61536,893,488,147,419,103,23165584 years

The minimum moves calculator works out the moves and the time for any number of disks, and the last row — the size of the legend — has a page of its own.

Without recursion

The same moves can be produced by a plain loop with two rules:

  • Odd-numbered moves: the smallest disk steps one tower along a fixed circuit — A → C → B for an odd number of disks, A → B → C for an even number.
  • Even-numbered moves: make the only legal move that does not involve the smallest disk. There is always exactly one.

Those two rules reproduce the recursive solution move for move; the iterative solution page shows why, and plays it on a board.

There is an even stranger version that stores no towers at all: the disk, the source and the destination of move m can each be read off the binary digits of m. That connection, and the Gray code hiding inside it, is in Tower of Hanoi, binary and Gray code.

From a position that is not the start

The textbook function assumes every disk begins on the source tower. Give it a half-finished puzzle and it has nothing to say. One more case fixes that. Look at the largest disk:

  • Already on the tower it needs to reach? It needs no moves. Solve the smaller disks, sending them to that same tower.
  • Anywhere else? Clear the smaller disks onto the tower that is neither where it is nor where it is going, move it, and carry on as before.

That version finds the shortest solution from any legal position, and it is what the Tower of Hanoi solver runs.

Check yourself

Three questions the page has already answered. Work them out before opening them — if one does not come, the section named with the answer is the one to read again.

  1. Three disks take seven moves. How many does 5 take, and how many of those move disk 5 itself?

    Show the answer

    31 moves, which is 2⁵ − 1 — and exactly one of them moves the largest disk. Every disk except the largest moves more than once, because each of the two halves of the solution has to move it. The recurrence, solved properly.

  2. hanoi(3, A, C, B) makes hanoi(2, A, B, C) as its first call. Why is B the target of that call rather than C?

    Show the answer

    Because disk 3 is going to C, and it can only land there if C is empty. So the two disks above it have to be parked somewhere else, and the only somewhere else is B. The tower this call is aiming at becomes the tower its first call has to keep clear — which is why two of the three arguments trade places on the way in. What to watch for.

  3. Solving 20 disks makes 2,097,151 calls. How many of them are on the stack at the same moment, at most?

    Show the answer

    21 — one for each disk count from 20 down to 0. A call finishes before its sibling starts, so the calls never all exist at once: the work is exponential and the memory is linear. Time and space complexity.

The algorithm in your language

The same function in six languages, each with a runnable program, a line-by-line walkthrough, the board running beside it, and the things that are specific to that language — which turn out to matter as soon as you try to count the moves for sixty-four disks.

  • Tower of Hanoi in PythonRecursive and iterative programs, why Python's recursion limit never bites here, and integers that simply do not overflow.
  • Tower of Hanoi in JavaScriptWhy 2 ** 64 − 1 prints the wrong number, BigInt, and a generator that hands out one move at a time.
  • Tower of Hanoi in JavaWhy (1L << 64) − 1 is zero, counting with BigInteger, and the same solution driven by an explicit stack.
  • Tower of Hanoi in CUndefined shifts, uint64_t, and a loop that reads every move straight off the bits of the move number.
  • Tower of Hanoi in C++Collecting the moves in a std::vector, the 64-disk count checked by the compiler, and three pairs of towers in a loop.
  • Tower of Hanoi in C#Top-level statements, an iterator whose moves LINQ can query, and ulong, checked arithmetic and UInt128 for the move count.

The words on this page

Base case
The version of the problem a recursive function answers outright, without calling itself. It is what stops the recursion. Here it is n = 0: no disks to move, so there is nothing to do and the call returns. Every chain of calls, however deep, ends at one of these.
Recursive case
Everything that is not the base case: the part of the function that solves a smaller version of the same problem and builds its answer out of that. Here it is the three lines that move n − 1 disks out of the way, move disk n, and bring the n − 1 back.
Call stack
The list of function calls that have started and not yet finished, most recent last. A call is added when it starts and removed when it returns, so the stack is how a program remembers where to go back to. It is what the panel above draws, and it is real memory — which is why its depth is the algorithm's space cost.
Stack frame
One entry on the call stack: the arguments and local variables belonging to a single call. Each row of the stack in the panel is a frame, holding this call's n and its own idea of which tower is the source, the target and the spare. Sixty-four disks need sixty-five frames, which is nothing; the moves are the problem.
Telescoping
Also called unrolling: solving a recurrence by substituting it into itself until the pattern is obvious, then setting the substitution count so that only the known starting value is left. It is called telescoping because the middle terms collapse the way the sections of a telescope do.
Θsaid “big theta”
A growth rate that is both an upper and a lower bound: Θ(2ⁿ) means the cost grows like 2ⁿ, not merely no faster than it. O(2ⁿ) would only promise the ceiling. Θ is the honest notation here, because this algorithm really does make 2ⁿ − 1 moves — it cannot get lucky and finish early.

Frequently asked questions

How does the recursive Tower of Hanoi algorithm work?

To move n disks from a source tower to a target tower, it first moves the top n − 1 disks to the spare tower, then moves the largest disk to the target, then moves the n − 1 disks from the spare onto the target. Each of those two smaller transfers is the same problem with one fewer disk, so the function calls itself for them, and a call with no disks to move simply returns.

Is Tower of Hanoi divide and conquer or dynamic programming?

It is divide and conquer. The problem is divided into two subproblems of n − 1 disks, each is conquered by recursion, and the combine step is a single move of the largest disk. It is not dynamic programming, and memoisation does not help — even though the subproblems genuinely do repeat. With three pegs there are only six ways to name a source, a target and a spare, so hanoi(1, A, C, B) really is called twice while solving three disks. Caching it buys nothing, because the answer to a subproblem is a list of 2ᵏ − 1 moves, and replaying a stored list of that length costs the same as producing it. The work here is the output, and no table makes the output shorter.

Does the Master Theorem apply to the Tower of Hanoi recurrence?

No. The Master Theorem covers recurrences of the form T(n) = aT(n/b) + f(n), where each subproblem is a fraction of the original. Tower of Hanoi's recurrence is T(n) = 2T(n − 1) + 1: the subproblem is one disk smaller, not a fraction of the size. Unrolling it gives T(n) = 2ⁿ − 1 directly, and induction confirms it.

How deep does the recursion go?

With a base case of n = 0, at most n + 1 calls are on the stack at once: one for each disk count from n down to 0. With a base case of n = 1 it is n. Either way the depth grows linearly, which is why the recursive solution needs only O(n) memory even though it makes an exponential number of moves.

How many function calls does the recursive solution make?

2ⁿ⁺¹ − 1 calls when the base case is n = 0: the 2ⁿ − 1 calls that move a disk, plus 2ⁿ calls that find nothing to move and return. Three disks make 15 calls. Written with a base case of n = 1 instead, the same program makes exactly 2ⁿ − 1 calls, one per move.

Is the iterative algorithm faster than the recursive one?

Not in any way that matters. Both must produce 2ⁿ − 1 moves, so both take time proportional to 2ⁿ. The iterative version avoids the cost of function calls and cannot run out of stack, but the recursion here is only n levels deep, so running out of stack is not a real risk for any number of disks you could wait for.

What does the Tower of Hanoi algorithm look like as a flowchart?

Not like much, and that is the honest answer. A flowchart shows control moving through boxes once, and this algorithm's second box is the whole flowchart again — three levels down, with two of the towers swapped and one fewer disk. A flowchart has no notation for that, so a flowchart of the recursive solution is either wrong, or it is a picture of one call with two boxes labelled “call hanoi”, which teaches nothing the four-line pseudocode does not. The diagram that does express it is the recursion tree: every call drawn under the call that made it, with each box sitting above the move it makes. That is on this page, and reading its boxes from left to right gives the moves in order.

Can the algorithm solve a puzzle that is already partly done?

The textbook version cannot: it assumes every disk starts on one tower. It generalises with one extra case — if the largest disk is already on its target, skip it and solve the disks above — and that version finds the shortest solution from any legal position. The Tower of Hanoi solver on this site runs exactly that.