Day 15 : Recursion Application - Tower of Hanoi

Chi-Tse Chiang
2022-09-30 23:59:01

Description

Now imagine there are 3 stakes on a plate. The leftmost stake has n plates stacked from small to large. Now you need to move these plates to the rightmost stake as they are, but there are 3 conditions:

1. The plates can be moved to any of the stakes.

2. On each stake, the large plate must be placed under the small plate.

3. Only one plate can be moved at a time, starting from the top.

(Source : Wikipedia)
This is the classic Hanoi Tower problem. In principle, the tower can be placed on any of the wooden stakes, but for the sake of a good program and explanation, the tower is placed on the far left and needs to be moved to the far right.

Example Code

First, the conclusion: moving n plates requires 2^n - 1 times.

In this example, the number of plates is set to 3, because it is easier to explain than the larger Tower of Hanoi, but the same concept is used.
We use A, B, and C to represent the stakes, and the plates are 1, 2, and 3 from top to bottom.

public class Hanoi {
        static void hanoitower(int n,char a,char b,char c){
            if(n==1){
                System.out.println("移動盤"+n+": " +"從" + a +"到"+ c);
            }
            else{
                hanoitower(n-1,a,c,b);
                System.out.println("移動盤"+n+": " +"從" + a +"到"+ c);
                hanoitower(n-1,b,a,c);
            }
        }
        public static void main(String[] args) {
            int plantNum = 3;
            hanoitower(plantNum,'A','B','C');
        }
}

Hanoi Tower uses a lot of recursion, so it is especially important to plan the algorithm in advance.
Our solution to this program should be:

1. Plates 1 and 2 move to column B (each handled separately)

2. Plate 3 moves to column C

3. Plate 1 moves to column A

4. Plates 2 and 1 move to column C (each handled separately)

Program analysis:

Step 1: We are entering a Hanoi Tower with a total of 3 plates. The recursive part will always appear inside else. When n = 1 at the end, it means that plate 1 is moved to column C, and then it will return to the original calling place (line 7), and then the second plate is moved to column B (line 8). Line 9 is passed in as an argument by hanoi(2,A,C,B), and finally the first plate is moved from C to B.

Step 2: At this point, because the third plate we started with has not yet been returned, it returns to line 8 and prints it. Then, from this point on, it continuously recurses from line 9 until it finally returns a void value and the function ends.

Online tools and tutorials

C++程式設計 [11.2]河內塔01版程式解析

(Source)
This video is one that I thought explained very clearly when I was teaching myself Hanoi Towers at the beginning!!! (The grammar part can be ignored, just listen to the analysis)

Python Tutor : Visualize code in Python,JavaScript,C,C++,and Java

This is an online visualization tool that supports different programming languages. You can copy the sample program provided above here, and you can understand how Hanoi Towers recursion works step by step in the space next to it.