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 .

©2019-2020 Toolsou All rights reserved,
Solve in servlet The Chinese output in is a question mark C String function and character function in language MySQL management 35 A small coup optimization Java performance —— Concise article Seven sorting algorithms (java code ) use Ansible Batch deployment SSH Password free login to remote host according to excel generate create Build table SQL sentence Spring Source code series ( sixteen )Spring merge BeanDefinition Principle of Virtual machine installation Linux course What are the common exception classes ?