In depth understanding of recursive method calls (including instance maze problem, tower of Hanoi, monkey eating peach, fiboracci, factorial))

= = = = Method recursively calls = = = =

Preface ： It is difficult to learn recursion at first , Just use your brain to think , It's really painful to be arbitraged by infinite … This module took a long time , Through searching some information, I finally have some understanding and experience .

One 、 Basic introduction
1、 To put it simply : Recursion is a method that calls itself , Different variables are passed in each call . Recursion helps programmers solve complex problems , At the same time, it can make the code Be concise .

Two 、 Recursive call mechanism （ Illustrate with examples ）
The following two problems can refer to the important rules of recursion , Only know its rules 、 Principle can better understand it .
1． When executing a method , Just create a new protected independent space ( Stack space )
2. The local variables of the method are independent , Will not affect each other , such as n Variable
3． If a reference type variable is used in the method ( For example, array , object ), Will share data of this reference type .
4. Recursion must approach the condition of exit recursion , Otherwise, infinite recursion , appear
StackOverflowError, Dead tortoise :)
5. When a method is executed , Or meet return, It will return , Follow who calls , Return the result to , At the same time, when the method is executed or returned , The method is executed .

example ：
① Printing problems
Although the printing problem is simple , But it's also easy to make mistakes when you first come into contact , Even if it's right, its call execution mechanism is vague .

public class Recursion01 {
 // Write a  main  Method  
 public static void main(String[] args) {
  T t1 = new T();
   t1.test(4);    // What output ？ n=2 n=3 n=4 
   int res = t1.factorial(5);
    System.out.println("5  The factorial  res =" + res）
    } 
    }
class T { 
 public void test(int n) {
  if (n > 2) {
   test(n - 1); 
   }
   System.out.println("n=" + n);
    }

② Factorial problem

//factorial  Factorial  
public int factorial(int n) {
 if (n == 1) {
  return 1; 
  } else { 
  return factorial(n - 1) * n;
   } 
   }

3、 ... and 、 Classic example （ Fiboracci 、 Monkeys eat peaches ）
1、 Please use recursive method to find Fibonacci number 1,1,2,3,5,8,13… Give you an integer n, Find out what its value is
Thought analysis ：
1） When n = 1 Fibonacci number yes 1
2） When n = 2 Fibonacci number yes 1
3） When n >= 3 Fibonacci number Is the sum of the first two numbers
4） Here is a recursive idea

class T {
public int fibonacci(int n) {
 if( n >= 1) {// The range is greater than 1 Number of numbers  
 		 if( n == 1 || n == 2) {// The first two numbers are 1
 		  return 1; 
 		  		} else {
 		  				return fibonacci(n-1) + fibonacci(n-2);// law ,（ Find it yourself ） 
 		  				} 
 		  			} else { 
 		  			System.out.println(" Required input  n>=1  The integer of ");
 		  			 return -1; 
 		  			 }
 		 }

2、 Monkeys eat peaches
problem : There is a pile of peaches , The monkey ate half of it on the first day , And one more , Later, every day monkeys eat half of them , And then one more . When it comes to the third 10 days , When you want to eat again ( I haven't eaten yet ), Only found 1 A peach . problem : How many peaches are there in the first place ?
Thought analysis ： Backstepping

1. day = 10 when Yes 1 A peach
2. day = 9 when Yes (day10 + 1) * 2 = 4
3. day = 8 when Yes (day9 + 1) * 2 = 10
4. Law is The peach of the previous day = ( Peaches the next day + 1) *2（ Finding rules is our ability ）
5. recursive

public class RecursionExercise01 { 
// Write a  main  Method  
			public static void main(String[] args) { 
				T t1 = new T(); 
				// Peach problem  
				int day = 0; 
				int peachNum = t1.peach(day);
				 if(peachNum != -1) { 
					 System.out.println(" The first  " + day + " There is " + peachNum + " A peach ");
  }
 				 public int peach(int day) { 
					  if(day == 10) { // The first  10  God , Only  1  Peach  
					  return 1; 
						  } else if ( day >= 1 && day <=9 ) {
							   return (peach(day + 1) + 1) * 2;// The rules , Think for yourself 
				    } else { 
							    System.out.println("day  stay  1-10"); return -1; } 
			    } 
    }

Through the above examples, we can summarize ：
1、 The most important thing of recursion is to find out the equivalent conditions that keep the problem shrinking .
2、 Then find out the conditions for terminating recursion .

Four 、 Call the application instance recursively （ Maze problem 、 Hanoi ）
1、 The mouse came out of the maze
From a certain starting point to the end , White means you can walk , Red is the barrier ; Set up a simple maze according to the map below . The path the mouse got , It has something to do with the way finding strategy set by the programmer , namely ： The order of finding the way is related to the top, bottom, left and right .

Thought analysis ：
1、 Use the recursive idea to solve the problem of mice coming out of the maze
2、findWay The way is to find the path of the maze
3、map It's a two-dimensional array , It means maze
4、i ,j That's where the mouse is , The initialization position is （1,1）
5、 Because we find the way recursively , So I'll rule first map The meaning of each value of the array ：
0 You can go 1 It means an obstacle 2 Indicates a path 3 Indicates walking , But it doesn't work
6、 When map[6][5] = 2 It means finding a way , That's the end of it , Otherwise, keep looking .（ The target point is map[6] [5] ）
7、 If you find it, go back ture Otherwise return to false
8、 First determine the mouse's way finding strategy Next -> Right -> On -> Left

public class MiGong{
	public static void main(String[] args) {
 // Set the position of labyrinth obstacles 
	int[][] map = new int[8][7];//8 That's ok 7 Column 
	for(int i = 0 ;i < 7;i++){// Set the first and last lines 
		map[0][i] = 1;
		map[7][i] = 1;
	}
	for(int j = 0 ;j < 8;j++){// Set the first and last columns 
		map[j][0] = 1;
		map[j][6] = 1;
	}
	map[3][1] = 1;// Set two walls separately 
	map[3][2] = 1;

// Output original array （ Map ）
	for (int i = 0; i < map.length  ; i++ ) {
		for (int j = 0; j < map[i].length ; j++ ) {
			System.out.print(map[i][j] + " ");
		}
		System.out.println();
	}

	T mouse = new T();
	boolean result = mouse.findWay(map,1,1);// from （1,1） Set out 

	System.out.println("====== The result is ：=====");// Find the map behind the road 

	for (int i = 0; i < map.length  ; i++ ) {
		for (int j = 0; j < map[i].length ; j++ ) {
			System.out.print(map[i][j] + " ");
		}
		System.out.println();
	}

	if(result){// Determine if it is found 
	System.out.println(" eureka ！");
		}else{
			System.out.println(" Did not find ！");
		}

	}

}

class T{
	public boolean findWay(int[][] map , int i , int j){
		//i,j Indicates the current location 
		//i = 1,j = 1;// The initial position is map[1][1]
		if(map[6][5] == 2){// Each time the method is called, check whether the current position is at the end 
			return true; // It means that 
		}
		if(map[i][j] == 0){
			map[i][j] = 2;// Suppose this position can go through 
			// The road finding strategy is ： Next  ->  Right  ->  On  ->  Left 
			if(findWay(map,i+1,j)){// Judge whether going down is the path 
			
				return true;
				
								 			
			}else if(findWay(map,i,j+1)){// Judge whether going right is a passage 
				return true;
				
			}else if(findWay(map,i,j)){// Judge whether going up is the path 
				return true;
				
			}else if(findWay(map,i,j-1)){// Judge whether going left is a passage 
				return true;
				
			}else{// It is assumed that this position is an access road 
				map[i][j] = 3;// Change it into a road that has been passed but is impassable 

			}

			
		}else{
			return false;// The current location is not 0
		return false ;
	}
}

2、 The hanotta problem

subject ： Count a plate Num , There are three pillars . All the dishes should be in the order from small to large from top to bottom at any time , That is, the disc cannot be enlarged on the small disc , Only one disc can be moved between the three pillars at a time . At first, all the dishes were placed on a pillar . ask : How the plate moves ？

Ideas ： How to make A All the plates of the tower move to C Tower go ？
1、 If there is only one plate , Then it can be explained directly A->C
== 2、 What if there are two plates ？ Then we should put A With the help of C Move to B, And take the rest A The tray of the tower is moved to C, And then B Move the plate in to C, complete .==
3、 If 3 individual 、 four 、n A? ？？
What is easily unexpected here is its law , as well as How to define a method , How to design the formal parameters of the method , That is, how to achieve . These two problems bothered me for several days （ Don't want to look directly at the code , Have been repeatedly understanding the use of methods and recursion , The result has been unable to think of , I really can't write it later. I'm impressed when I see the code ） After all, it is the lack of code implementation ability and problem-solving thinking ability … It needs to be strengthened slowly .
4、 First draw three plates on the paper by yourself , Four plates . After understanding its process, you can find a little rule of it .（ Here it is applied to a kind of mathematical thinking , Holistic approach , That is, take the top and bottom as a whole , No matter how many it is ）.
5、 Suppose there is N null , It can be regarded as two parts （ Because from 2 This rule can be used from the beginning of a plate ） The bottom plate and the rest on top n-1 null .
6、 Then we just need to n-1 Move a plate to B, Then move the bottom one to C, And then B Of n-1 Move to C.
7、 that n-1 individual B How to move the tray of the tower to C Well ？ Repeat the first 5 And the 6 Step …
8、 It is obvious that we can solve this problem with recursion .
9、 The next step is code implementation

public class HanoiTower{
	
		public static void main(String[] args){
		//a, b, c respectively A tower ,B tower ,C tower 
			char a = 'A';
			char b = 'B';
			char c = 'C';

			Tower t1 = new Tower();
			t1.move(5,a,b,c);//5 null ,A,B,C Three Pagodas 
		}
}

class Tower{
	//num Indicates the number to be moved , a, b, c respectively A tower ,B tower ,C tower 

	public void move(int num , char a ,char b ,char c){

		if(num == 1){// If there's only one dish 
			System.out.println(a+"->"+c);
			}else if(num >= 2){// Two or more plates 
				// If there are multiple disks , It can be regarded as two  ,  All the disks at the bottom and above (num-1)
				move(num - 1 ,a , c ,b);// hold num-1 A dish from A Move the tower to B Tower go , But with the help of C tower 
				System.out.println(a+"->"+c);// And then A The largest remaining tray of the tower is moved to C tower 
				move(num - 1 ,b , a ,c);// Finally, put B Of the tower num-1 Move a disk to C Tower go , complete .

				

				return ;
			}else
		System.out.println(" The number you entered is incorrect ");// The number of plates is not greater than 1 Error is reported in the range of 
		return ;
	}
}

The core code is actually just a few lines , But when I typed it out, I really felt that the original code could be so beautiful ~

These days, I can't calm down when I see the maze and the tower of Hanoi , I always want to escape when I encounter difficulties … Finally, it was solved , At least I can understand these codes . There will be all kinds of difficulties in the future , I hope you can stick to it ！！
Learning is like this , Life is also .
I have no him. , Only hand ripe .

above , Mutual encouragement .