A brief analysis of python recursive function and Hanoi tower problem

About recursive functions:

A function calls its own function internally.

Take n factorial for example:

f (n) = n! = 1 x 2 x 3 x 4 x... x(n-1)x(n) = n x (n-1)!

def factorial(n):
   if n==1:
     return 1
   return n * f(n-1)

// the call process is as follows:

>>f(5)
>>5 * f(4)
>>5 * 4 * f(3)
>>5 * 4 * 3 * f(2)
>>5 * 4 * 3 * 2 * f(1)
>>5 * 4 * 3 * 2 * 1
>>120

From the above example, you can see the recursive function calling its own function until n==1(function exit).

About the Hanoi tower:

Rules:

1. 3 pillars, A, B, C

2. The plates on the A pillar are arranged from small to large, with the smallest at the top and the largest at the bottom.

3. Move the plate on A to C and keep the largest one on the bottom and the smallest one on top.

If there is a plate on the A pillar, it can be moved directly from A to C:

A - > C

Suppose there are two plates on the A pillar, which need to be moved to C by means of B:

A -- > B

A -- > C

B -- > C

Move the top disk (2-1) of A to B, then move the remaining disk in A to C, and finally move the disk in B to C

Suppose there are three plates on the A pillar. You need to move the two plates on A by B, then move the largest remaining plate on A to C, and finally move the plates in B to C.

A -- > C

A -- > B

C -- > B // these three steps move the first two plates of A to B

A -- > C // this step moves the largest plate on A to C

B -- > A

B -- > C

A -- > C // the next 3 steps move the plates on B to C

The principle is to move the block disk on A (n-1) to B, then the remaining and largest block disk in A to C, and finally the block disk on B (n-1) to C.

def Hanoi(n , a, b, c):
  if n==1:
    print (" Hanoi Tower move", a, "-->", c)
    return
  Hanoi(n-1, a, c, b)
  Hanoi(1, a, b, c)
  Hanoi(n-1, b, a, c)
print (" When there is 1 ring on A")
Hanoi(1, 'A', 'B', 'C')
print (" When there are 2 rings on A")
Hanoi(2, 'A', 'B', 'C')
print (" When there are 3 rings on A")
Hanoi(3, 'A', 'B', 'C')
print(" When there are 4 rings on A")
Hanoi(4, 'A', 'B', 'C')