preface

Don’t know what time is your friend contact by recursion, remember when I was first learning recursion is learning through examples of Hanoi, the “Hanoi” although no lines of code, but also a headache for me for a long time, the brain is so stupid, not to be able to turn ๐Ÿ˜‚), after a long period of time is to understand the logic, Today, I will talk about recursion with you in a simple way, and share some of my experience and experience in learning recursion.

Hanoi

Hannota (also known as Hanoi Tower) originated from an ancient legend in India: When The Great Brahma created the world, he made three diamond pillars, on one of which were stacked 64 gold disks in order of size from bottom to top. Mahama ordered the Brahmin to rearrange the disks on another pillar, starting from below, in order of size. It is also stipulated that the disk cannot be enlarged on the small disk and that only one disk can be moved at a time between the three columns.

Later this legend evolved into the current Hannota game, the rules of the game is also very simple ๐Ÿ‘‡

  1. There are three rods A, B and C, and on rod A there are several disks
  2. You can only move one disk at a time, and the smaller disks can only be stacked on top of the larger ones
  3. Moving all disks from pillar A to pillar C counts as success

Now that we know the rules of the game, let’s think about how to complete the final task of the game. I have the strength ๐Ÿ’ช, directly put the disc all picked up on the C pillar is done, just a few small disc or can take move ๐Ÿ˜‚ this method is really enough “obscene”, is also simple enough rough, but only with everyone to open a small joke, we still get down to business below, serious analysis of the mystery of the game ๐Ÿ‘‡

When there is only one disk on pillar A, move the disk directly from pillar A to pillar C.

When there are two disks on pillar A, the disks on pillar A are arranged as nos. 1 and 2 in the order of size from top to bottom. Then, to move all disks from pillar A to pillar C, the first disk needs to be moved to pillar B, then the second disk needs to be moved from pillar A to pillar C, and finally the first disk needs to be moved from pillar B to pillar C.

When there are three disks on pillar A, and the disks are still numbered 1, 2, and 3 in order of magnitude from the top down, we find that the problem becomes A little more complicated, so we can treat disks 1 and 2 as A whole (i.e., “1-2” disks). At this point, we need to solve the problem of moving the “1-2” disk and the “3” disk to pillar C, that is, first move the “1-2” disk to pillar B, then move the “3” disk to pillar C, and finally move “1-2” disk to pillar C.

Similarly, if there are N disks on pillar A, we still use the “view as A whole” method to solve the problem, and we still order the disks on pillar A from the top down into numbers 1, 2, 3… N, at this time, we need to view disks 1 to N-1 as a whole (denoted as “1โ†’ n-1” disk). At this time, we need to first move disks “1โ†’ n-1” to B pillar, then move disks “N” to C pillar, and finally move disks “1โ†’ n-1″ on B pillar to C pillar. We can find that when disk N moves to pillar C, it does not need to move again, that is to say, no matter how other disks move, disk N does not need to participate in the movement, which represents that the whole (” 1โ†’ n-1 “disk) and individual (disk N) are independent and do not affect each other. So we can continue to split the “1โ†’ n-1” disk according to the above logic, and finally move all the disks from pillar A to pillar C.

We can conclude the above analysis ๐Ÿ‘‡

  1. The first case is when we only have one disk, we just have to do one step, move the disk directly from pillar A to pillar C
  2. When there are N disks, our operation process is divided into three steps: โ‘  move the front N-1 disk from pillar A to pillar B โ‘ก Move the N disk from pillar A to pillar C โ‘ข Move the front N-1 disk from pillar B to pillar C

With this summary, we can write a code to move hannott tower ๐Ÿ‘‡

/** * Hanover Tower *@description: HanoiDemo
 * @author: Zhuang Ba. Liziye *@create: the 2022-01-11 10:18 * * /
public class HanoiDemo {
    public void hanoi(int n, String A, String B, String C) {
        if (n == 1) {
            // Move the disk directly from pillar A to pillar C
            move(n, A, C);
        } else {
            // Move the first n-1 disk from pillar A to pillar B with the help of pillar C
            hanoi(n - 1, A, C, B);
            // Move disk N from pillar A to pillar C
            move(n, A, C);
            // Move the first n-1 disk from B to C with the help of A column
            hanoi(n - 1, B, A, C); }}/** * move N disk **/
    private void move(int n, String A, String C) {
        System.out.println("Will"+ n +"No. Disk from" + A + "Move to" + C);
    }

    public static void main(String[] args) {
        HanoiDemo hanoiDemo = new HanoiDemo();
        System.out.println("Steps to move when there are 3 disks on pillar A:");
        hanoiDemo.hanoi(3."A pillar"."B pillar"."C pillar"); }}Copy the code

recursive

As you can see from the code, we’ve successfully solved hannotta’s problem using the recursive idea, which is actually very simple, and we just need to pay attention to two things: the end condition and making the problem smaller. In the Hannotta case, moving all the disks from pillar A to pillar C was the closing condition, and the way we used to “look at the whole” was to make the problem smaller. Maybe a lot of people think that in the process of learning to do “know what it is, know what it is”, but when learning recursion, it is the opposite, we just need to do “not understand”. The “obscene” way to learn recursion is to give up. Specifically, to give up the idea of understanding and tracking the whole process of recursion, otherwise you will let yourself fall into a loop, not only unable to understand recursion, but also make yourself confused.

Going back to the Hannott tower example, what if someone asked us to move the “1โ†’ n-1” disk? We may have a headache, there are n-1 disks to move, it will not exhaust us ๐Ÿ˜ญ, in fact, the solution to the problem is very simple, we can also learn to assign tasks to the person, outsourcing the work, that is to say, we only n-1 disk, the other “1โ†’N-2” disks are outsourced to others, This we became a contractor, this time we are not a lot easier ๐Ÿ˜„.

This is the time to stop worrying about the guy who gets the outsourcing job and leave it to him. Don’t torture yourself. The person who gets the outsourcing job can do whatever he or she wants to do. It’s none of our business. We just need to focus on our own disk. Maybe the person who received our outsourcing job also wanted to save himself some trouble, so he outsourced the “1โ†’N-3” disk and kept the N-2 disk.

This eventually became a task chain: large contractor โ†’ contractor โ†’ small contractor โ†’ small contractor โ†’ small contractor…. โœŒ last contractors finish their missions, then all contractors above them can easily finish their share of tasks. With the joint efforts of all contractors, the mission can be completed in a perfect โœŒ (do we like the saying: big lazy stay small lazy ๐Ÿคญ).

summary

My experience is limited, some places may not be particularly in place, if you think of any questions when reading, welcome to leave a message in the comments section, we will discuss one by one ๐Ÿ™‡

Please take a thumbs up and a follow (โœฟโ—กโ€ฟโ—ก) for this article ~ a crab (โ—’โ—ก’โ—)

If there are mistakes in the article, welcome to comment correction; If you have a better, more unique understanding, you are welcome to leave your valuable ideas in the comments area.

Love what you love, do what you do, listen to your heart and ask nothing