Prashnikaप्रश्निका
Code
About

Tower of Hanoi visualiser

Move a tower of discs from peg A to peg C, using B, one disc at a time and never a bigger disc on a smaller one. Press Play and watch the discs move while the recursive calls build up on the call stack and in the tree. A tower of n discs always takes 2n − 1 moves.

How to use it

  1. 1Type the number of discs (1 to 5), or tap an example.
  2. 2Press Show me, then Play. The discs move between the pegs A, B and C one step at a time.
  3. 3Watch the recursive calls on the call stack and in the tree, and the list of moves growing.
Not sure what to type? Tap an example:
2 discs: 3 moves3 discs: 7 moves4 discs: 15 moves5 discs: 31 moves

The animation needs JavaScript. Every step is written out below.

Result

Result
15 moves (2^4 - 1 = 15)
Every step in words (60 steps)
  1. hanoi(4, A, C) is called: move 4 discs from A to C using B.
  2. n = 4, not 1. First move the top 3 discs out of the way (from A to B, using C).
  3. hanoi(4, A, C) calls hanoi(3, A, B): it will clear the way.
  4. n = 3, not 1. First move the top 2 discs out of the way (from A to C, using B).
  5. hanoi(3, A, B) calls hanoi(2, A, C): it will clear the way.
  6. n = 2, not 1. First move the top 1 disc out of the way (from A to B, using C).
  7. hanoi(2, A, C) calls hanoi(1, A, B): it will clear the way.
  8. n = 1: the base case. Just move the one disc.
  9. Move disc 1 from A to B (move 1).
  10. Return. The frame leaves the stack.
  11. Move disc 2 from A to C (move 2).
  12. hanoi(2, A, C) calls hanoi(1, B, C): it puts the smaller discs back on top.
  13. n = 1: the base case. Just move the one disc.
  14. Move disc 1 from B to C (move 3).
  15. Return. The frame leaves the stack.
  16. hanoi(2, A, C) has moved 2 discs from A to C. It returns.
  17. Move disc 3 from A to B (move 4).
  18. hanoi(3, A, B) calls hanoi(2, C, B): it puts the smaller discs back on top.
  19. n = 2, not 1. First move the top 1 disc out of the way (from C to A, using B).
  20. hanoi(2, C, B) calls hanoi(1, C, A): it will clear the way.
  21. n = 1: the base case. Just move the one disc.
  22. Move disc 1 from C to A (move 5).
  23. Return. The frame leaves the stack.
  24. Move disc 2 from C to B (move 6).
  25. hanoi(2, C, B) calls hanoi(1, A, B): it puts the smaller discs back on top.
  26. n = 1: the base case. Just move the one disc.
  27. Move disc 1 from A to B (move 7).
  28. Return. The frame leaves the stack.
  29. hanoi(2, C, B) has moved 2 discs from C to B. It returns.
  30. hanoi(3, A, B) has moved 3 discs from A to B. It returns.
  31. Move disc 4 from A to C (move 8).
  32. hanoi(4, A, C) calls hanoi(3, B, C): it puts the smaller discs back on top.
  33. n = 3, not 1. First move the top 2 discs out of the way (from B to A, using C).
  34. hanoi(3, B, C) calls hanoi(2, B, A): it will clear the way.
  35. n = 2, not 1. First move the top 1 disc out of the way (from B to C, using A).
  36. hanoi(2, B, A) calls hanoi(1, B, C): it will clear the way.
  37. n = 1: the base case. Just move the one disc.
  38. Move disc 1 from B to C (move 9).
  39. Return. The frame leaves the stack.
  40. Move disc 2 from B to A (move 10).
  41. hanoi(2, B, A) calls hanoi(1, C, A): it puts the smaller discs back on top.
  42. n = 1: the base case. Just move the one disc.
  43. Move disc 1 from C to A (move 11).
  44. Return. The frame leaves the stack.
  45. hanoi(2, B, A) has moved 2 discs from B to A. It returns.
  46. Move disc 3 from B to C (move 12).
  47. hanoi(3, B, C) calls hanoi(2, A, C): it puts the smaller discs back on top.
  48. n = 2, not 1. First move the top 1 disc out of the way (from A to B, using C).
  49. hanoi(2, A, C) calls hanoi(1, A, B): it will clear the way.
  50. n = 1: the base case. Just move the one disc.
  51. Move disc 1 from A to B (move 13).
  52. Return. The frame leaves the stack.
  53. Move disc 2 from A to C (move 14).
  54. hanoi(2, A, C) calls hanoi(1, B, C): it puts the smaller discs back on top.
  55. n = 1: the base case. Just move the one disc.
  56. Move disc 1 from B to C (move 15).
  57. Return. The frame leaves the stack.
  58. hanoi(2, A, C) has moved 2 discs from A to C. It returns.
  59. hanoi(3, B, C) has moved 3 discs from B to C. It returns.
  60. hanoi(4, A, C) has moved 4 discs from A to C. It returns.
Start again

About the Tower of Hanoi visualiser

What it does

Solves the Tower of Hanoi for the number of discs you give: all the discs start on peg A and must end on peg C, using peg B, moving one disc at a time and never putting a bigger disc on a smaller one. The recursive method does it in three parts: move the top n − 1 discs to the spare peg, move the biggest disc, then move the n − 1 discs on top of it. The page shows the discs, the call stack, the call tree and the Java code together.

The number of moves

n discs always take 2n − 1 moves: 1, 3, 7, 15 and 31 moves for 1 to 5 discs. The number of moves is written under the answer.

Common questions

How many moves does the Tower of Hanoi need?

2n − 1 for n discs, and no fewer: 3 moves for 2 discs, 7 for 3, 15 for 4 and 31 for 5.

What is the recursive idea behind the Tower of Hanoi?

To move n discs from A to C using B, first move n − 1 discs from A to B using C, then move the biggest disc from A to C, then move the n − 1 discs from B to C using A. The base case is a single disc, which is moved directly.

Why only up to 5 discs?

The number of moves doubles with every disc, so a larger tower would be too long to follow on a page. Five discs already make 31 moves and 31 calls.

Can I see the code in Python, JavaScript or C++?

Yes. Choose the language in the menu above the code. Only the listing changes: the steps are always worked out from the Java program that ISC uses, and the highlighted line moves to the matching line of the language you chose.

More Computer Science tools

All study tools →