[PYTHON] [For beginners] Recursive function (Tower of Hanoi is easy to understand!)

1. 1. Introduction

Recursive functions may be the first barrier to programming. Master recursive functions while solving the Tower of Hanoi in Python.

Recursive functions, like Matryoshka, have a nested program structure. Please read the following explanation while imagining Matryoshka.

2. Tower of Hanoi

See below for the Tower of Hanoi. Tower of Hanoi

Briefly, there are three sticks that can be pierced by a board. There are several boards on the left. The size of the board is the largest at the bottom and becomes smaller toward the top. I want to move the boards one by one and finally move all the boards from the left to the middle bar. However, a large plate cannot be placed on a small plate.

In programming learning, it is a problem to be solved using a recursive function.

3. 3. Way of thinking

One is super easy. Move from the left to the center and you're done. The point is the case of two sheets. Suddenly, don't move the small board on the left bar to the center. (1) First, the small plate is once transferred to the work rod on the right side. (2) Then, move the large board left on the left to the center. (3) After that, move the small board from the right to the center, and it's OK.

In other words, n boards (2 boards in this case), in order to move everything from the left to the center, (1) n-1 boards (1 board in this case) excluding the largest board at the bottom. , It is necessary to move from left to right once to the work rod. (2) Then, after moving the largest plate at the bottom from the left to the center, (3) all the n-1 plates (1 plate in this case) on the right work rod, If you move it to the center, it's OK.

In the following description, the above (1) to (3) will be repeatedly described. (1) to (3) that appear in the following explanation basically have the same meaning as (1) to (3) above. However, "where to where" changes depending on the case in "left, middle, right".

4. Recursive function solution

The following is the solution program for the Tower of Hanoi. I will execute it later, but when using it, substitute the number of boards for N.

start=list(range(N,0,-1));end=[];tmp=[];i=0  #1
def print_hanoi(): #2
    print(start,end,tmp)
def hanoi(n,start,end,tmp): #3
    if n<=0:        return  #4
    hanoi(n-1,start,tmp,end)  #5
    end.append(start.pop())   #6
    print_hanoi()              #7
    global i; i+=1             #8
    print('The above is',i,'State after the second operation')   #9
    hanoi(n-1,tmp,end,start)   #10
print_hanoi()                  #11
print('The above is the initial state')       #12
hanoi(N,start,end,tmp)         #13

I will explain briefly. The numbers correspond to the parts marked with # in the program.

1. 1. start is a list that represents the board that is stuck in the left bar first. In the initial state, the bottom is the largest, the list is smaller by 1, and the last is 1.

end is a list showing the board stuck in the middle bar where you want to finally move the board. Nothing is stuck at first, so an empty list.

tmp is a list showing the board stuck in the stick for the work on the right. This is also an empty list because nothing is stuck at first.

i is set to indicate the number of operations.

2. Represents a state. List the boards stuck in the "left, middle, right" sticks in order.

3. 3. This is the function that solves the Tower of Hanoi. However, since it uses a recursive function as a function, it is nested like Matryoshka. Please pay attention to the argument. The first n is the number of boards. Next is start and I want to move it to the next end. The last is tmp.

4. This is the base termination condition. When the number of boards to move becomes 0, the process ends. If you forget the base termination condition, you will end up in an infinite loop, so be careful.

The function of 5.3 is used recursively. However, the function of 3 is defined to move all n sheets of the first argument from the start of the second argument to the end of the third argument. (The fourth argument is tmp for work.)

Here, ** (1) All the remaining n-1 sheets (first argument) except the bottom n are temporarily moved from start (second argument) to tmp (third argument). ** (The fourth argument is the remaining argument end.)

** By doing this, n-1 sheets from the top move to tmp, so you can move n at the bottom. ** **

Since I moved n-1 sheets from the top to tmp in 6.5, only the bottom n remains on the left start bar. (2) Take out the bottom board and move it to start.pop () and the middle end bar ʻend.append ()` (add to list).

7. Print the state here.

8. Count up the number of times.

9. Print the number of operations after the operation for easy understanding.

10. ** The largest board in 6 has moved to the center. (3) Transfer all n-1 plates on the right work rod onto the largest plate. If you look at the arguments, you'll see what you're doing. ** **

11. Print the initial state here.

12. Print comments for easy understanding.

13. Actual execution. N is given when actually using it.

5. Let's actually try

1. 1. First of all, when there is one board. I don't think it's necessary to do it, but be careful about everything. N is specified at the beginning of the program.

N=1;start=list(range(N,0,-1));end=[];tmp=[];i=0  #1
def print_hanoi(): #2
    print(start,end,tmp)
def hanoi(n,start,end,tmp): #3
    if n<=0:        return  #4
    hanoi(n-1,start,tmp,end)  #5
    end.append(start.pop())   #6
    print_hanoi()              #7
    global i; i+=1             #8
    print('The above is',i,'State after the second operation')   #9
    hanoi(n-1,tmp,end,start)   #10
print_hanoi()                  #11
print('The above is the initial state')       #12
hanoi(N,start,end,tmp)         #13

The result is as follows. Move from the left to the center and you're done.

Here, only the part (2) described in the "idea" of 3 is executed. As you can see by looking at # 5 corresponding to (1) and # 10 corresponding to (2), n-1 becomes 0 and nothing is executed in # 4.

[1] [] []
The above is the initial state
[] [1] []
The above is the state after the first operation

2. Next are two cases. Unlike one case, the right work rod is used for the second and subsequent cases.

N=2;start=list(range(N,0,-1));end=[];tmp=[];i=0  #1
def print_hanoi(): #2
    print(start,end,tmp)
def hanoi(n,start,end,tmp): #3
    if n<=0:        return  #4
    hanoi(n-1,start,tmp,end)  #5
    end.append(start.pop())   #6
    print_hanoi()              #7
    global i; i+=1             #8
    print('The above is',i,'State after the second operation')   #9
    hanoi(n-1,tmp,end,start)   #10
print_hanoi()                  #11
print('The above is the initial state')       #12
hanoi(N,start,end,tmp)         #13  

The result is as follows. The numbers represent the size of the board. The numbers in the list are output in order from the one below. In other words, it is necessary for the rules of the Tower of Hanoi that the numbers in the list are arranged in descending order. In two cases, (1) ** First, move the small plate to the work rod from left to right. ** (First operation) (2) And ** By doing so, the large board on the left can be moved to the center. ** (Second operation) (3) ** Finally, move the small plate on the right onto the large plate in the middle, and it's OK. ** (3rd operation)

[2, 1] [] []
The above is the initial state
[2] [] [1]
The above is the state after the first operation
[] [2] [1]
The above is the state after the second operation
[] [2, 1] []
The above is the state after the third operation

The program is omitted after 3.3 sheets. It's OK if you change the number of sheets to be assigned to N. The result is as follows.

[3, 2, 1] [] []
The above is the initial state
[3, 2] [1] []
The above is the state after the first operation
[3] [1] [2]
The above is the state after the second operation
[3] [] [2, 1]
The above is the state after the third operation
[] [3] [2, 1]
The above is the state after the 4th operation
[1] [3] [2]
The above is the state after the 5th operation
[1] [3, 2] []
The above is the state after the 6th operation
[] [3, 2, 1] []
The above is the state after the 7th operation

(1) ** In the first to third operations, two sheets (that is, n-1 sheets) are transferred to the right work rod. The first to third times include (1) to (3) in the case of two sheets. ** Of course, the details of "where to where" are on a case-by-case basis.

(2) Then, in the ** 4th operation, the largest 3rd sheet (that is, the nth sheet) is moved from the left to the center. ** **

(3) After that, in the operations from ** 5th to 7th, move the 2 sheets (that is, n-1 sheets) on the right work onto the largest plate in the middle, and finish. The 5th to 7th times also include (1) to (3) in the case of two sheets. ** Of course, the details of "where to where" are on a case-by-case basis.

What I would like you to be careful about here is the method of transferring the two pieces to the right work rod in (1). ** In the case of moving the two pieces done in 2 from the left to the center, the right side became the work. However, in the case of moving two sheets from left to right with three sheets (1), the center is naturally for work. Therefore, the smallest board will be moved to the center in the first operation. ** **

** The same applies when moving two sheets from the right to the center in (3). Here, the left is the work, so in the fifth operation, the smallest plate is moved from right to left. ** **

4. Let's finish with 4 cases at the end.

[4, 3, 2, 1] [] []
The above is the initial state
[4, 3, 2] [] [1]
The above is the state after the first operation
[4, 3] [2] [1]
The above is the state after the second operation
[4, 3] [2, 1] []
The above is the state after the third operation
[4] [2, 1] [3]
The above is the state after the 4th operation
[4, 1] [2] [3]
The above is the state after the 5th operation
[4, 1] [] [3, 2]
The above is the state after the 6th operation
[4] [] [3, 2, 1]
The above is the state after the 7th operation
[] [4] [3, 2, 1]
The above is the state after the 8th operation
[] [4, 1] [3, 2]
The above is the state after the 9th operation
[2] [4, 1] [3]
The above is the state after the 10th operation
[2, 1] [4] [3]
The above is the state after the 11th operation
[2, 1] [4, 3] []
The above is the state after the 12th operation
[2] [4, 3] [1]
The above is the state after the 13th operation
[] [4, 3, 2] [1]
The above is the state after the 14th operation
[] [4, 3, 2, 1] []
The above is the state after the 15th operation

(1) ** In the operations from the 1st to the 7th, 3 sheets (that is, n-1 sheets) are transferred to the rod for the right work. The first to seventh times include (1) to (3) in the case of three sheets. Then, (1) in the case of 3 sheets includes (1) to (3) in the case of 2 sheets, and (1) in the case of 2 sheets is also included in (3) in the case of 3 sheets. ) To (3) are included. ** **

(2) Then, in the ** 8th operation, the largest 4th sheet (that is, the nth sheet) is moved from the left to the center. ** **

(3) ** After that, in the 9th to 15th operations, move the 3 sheets (that is, n-1 sheets) on the right work onto the largest plate in the middle, and you're done. The 9th to 15th times include (1) to (3) in the case of three sheets. Then, (1) in the case of 3 sheets includes (1) to (3) in the case of 2 sheets, and (1) in the case of 2 sheets is also included in (3) in the case of 3 sheets. ) To (3) are included. ** **

This time as well as the case of 3 sheets, the work use will change.

6. Summary

The role of work in the Tower of Hanoi changes depending on the number of boards. However, what I would like you to pay attention to is the parts (1), (2), and (3) described in 2, 3, and 4 of 5. (1) ** First, move n-1 sheets from the top for the work from left to right, ** (2) ** By doing so, the bottom large board can be moved from the left to the center, ** (3) ** Finally, if you move n-1 sheets from the top to the center from the work on the right, it's OK. ** **

Speaking of the program of 4, (1) corresponds to 5, (2) corresponds to 6, and (3) corresponds to 10. It is the recursive function used to solve the Tower of Hanoi that repeats this operation, like Matryoshka. (To be precise, the pure recursion parts are (1) and (3).)

7. Reference site

The following sites are written in c ++, but they are very helpful sites. The author is the one I personally respect.

What kind of world will expand when you learn recursive functions