According to legend, in ancient Indian temples, there was a game called Hanoi Tower. The game is on a copper device with three sticks (numbered A, B and C). On the A-pole, 64 gold plates are placed in turn from bottom to top.

The goal of the game: move all the gold plates on the A pole to the C pole and fold them in the original order. Operating rules: only one plate can be moved at a time. During the movement, the big plate is always kept under the three poles, and the small plate is on it. During operation, the plate can be placed on any electrode of A, B and C..

If a has only one (a->; C) carry out the test.

If a has two (a->; b)、(A->； c)，(B->； C) carry out the test.

If a has three (a->; c)，(A->； b)、(C->； b)、(A->； c)，(B->； a)、(B->； c)，(A->； C) carry out the test.

Any more and it will explode.

Recursion: The function calls itself. The subproblem must be the same thing as the original problem, or simpler; Recursion can usually deal with subproblems simply, but it is not necessarily the best.

In fact, recursion is inefficient in some cases. Especially Fibonacci. As can be seen from the figure, a simple operation has been repeated many times. Because it recursively calls two selves. Then its recursive expansion rate is exponential, and a lot of the same calculations are repeated.

Origin:

The problem of Hanoi Tower is an educational toy that originated from ancient Indian legends. When Brahma created the world, he made three diamond pillars, and 64 gold disks were stacked on one pillar in order of size from bottom to top.

Brahma ordered Brahma to rearrange the disks on another pillar in order of size from bottom to top. It is also stipulated that small plates cannot be put on large plates, and only one plate can be moved between three pillars at a time.