Apps Games Sync Setup Docs About Help

Hanoi Example

Hanoi is a good example of "recursion" (even though the actual underlying algorithm is implemented iteratively for better process control).

With the situation of 3 disks starting on left stack: If you knew how to move the top 2 disks somewhere else, e.g., to the middle stack, [steps 1-3 below], all you would have to do then is move the bottom disk to the right [step 4]; and since you already know how to move 2 disks, just move those from middle to right [steps 5-7].

Here are step-by-step directions for 3 disks (#1 refers to smallest disk) and 3 stacks (left,middle,right):

  1. move disk(#1) from left to right
  2. move disk(#2) from left to middle
  3. move disk(#1) from right to middle
  4. move disk(#3) from left to right
  5. move disk(#1) from middle to left
  6. move disk(#2) from middle to right
  7. move disk(#1) from left to right

You can watch the program do this by setting method to Move.

toc

next