The application of function recursive algorithm has a classic example , That's the tower of Hanoi problem , Next, let's take a look at how to solve the tower of Hanoi problem with recursive function !
The origin of the tower of Hanoi problem ：
Hanoi （ Also known as Hanoi tower ） The problem is an old Indian legend . Brahma left three diamond sticks in a temple , The first one is covered with 64 A round piece of gold , The biggest one is at the bottom , The others are smaller than one , Fold them in turn , The monks in the temple tirelessly moved them one by one from one stick to another , It is stipulated that a bar in the middle can be used as a help , But only one at a time , And the big one can't be put on the small one . Facing huge numbers ( The number of times the wafer is moved )18446744073709551615, it seems , The monks exhausted their life energy and could not complete the movement of the gold . later , The legend evolved into the tower of Hanoi game .
Tower of Hanoi rule ：
In a nutshell , That's to say a On the post n A disc , adopt b The column is transported to the ground as an auxiliary c Go to the post . In the process of handling, only one disc can be carried at a time , And the big disk can't be put on the small disk .
What is recursion ?
We should solve this problem recursively , We need to know what recursion is first .
Recursion is when a function calls itself in its body . Executing a recursive function calls itself repeatedly , Each call goes to a new layer . A recursive function must have an end condition .
When the function is recursive all the time , Until you come back against the wall , This wall is the end condition .
So recursion has two elements , End condition and recurrence relation .
problem analysis ：
It's easy for us to know ：
When n=1 Time , We take the plate directly from the table a Column moved to c The column solved the problem .
When n=2 Time , We can put it first a The first plate on the column moves to b column （a The plate on the top of the column is numbered 1, Increase in descending order ）, And then a The second plate on the column moves to c column , And then b The plates on the column move to c Column is enough .
But when n The value of is 3 And then the problem becomes troublesome . So can we simplify the later complex problems into the first two simple cases ?
The answer is yes , This is also the purpose of function recursion ： Simplify complex problems .
code implementation ：
We just need to count the plates n There are two types of solutions ：
When n=1 Time , Remove the plate from the container a->c that will do .
When n>1 Time , take a On the post n-1 A plate moved to b On the pillar , And then a The one left on the post （ That's the second one n individual ） Move to c On the pillar , And then b On the post n-1 Move to ,c Just on the post .（ Remember that we are going to n-1 One plate as a whole ）
among void move(int n, char a, char b, char
c) It means that you want to n A plate from a Through the column b Column moved to c On the pillar .（ Through the number you pass in, that is, characters to achieve the corresponding operation ）
After programming, we can input a relatively easy to detect number to see if the program is correct .
Personal view ：
In my opinion, the tower of Hanoi problem, including most problems that can be solved by function recursion, requires us to have a kind of ability , That's to look at something as a whole . For example, in the case of the tower of Hanoi, we will n-1 As a whole , If you can't do it, have this understanding ability , Then it will be difficult to understand how to use function recursion to solve the tower of Hanoi problem .