Recursion (maze problem, Queen 8 problem)

recursive

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 concise

Rules to follow

• When executing a method , Just create one New protected independent space ( Stack space )
• The local variables of the method are independent , Will not affect each other . If a reference type variable is used in the method ( For example, array ), Will share data of this reference type
• Recursion must be directed to Conditional approximation of exit recursion , Otherwise, infinite recursion , To die （ appear StackOverflowError Stack overflow exception ）
• 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 .

solve the problem

• Various mathematical problems such as : 8 queens problem , Hanoi , Factorial problem , Maze problem , The ball and basket problem (google Programming Contest )
• Recursion is also used in various algorithms , Like fast row. , Merge sort , Two points search , Divide and conquer algorithm, etc
• Problems to be solved with stacks –> Recursive code is simpler

The illustration

• According to the following code
• Deep understanding of recursion to open up stack space , And pay attention to the direction of the program （ First look at the red arrow , Look at the black arrow ）

Code

package com.atguigu.recursion;

//author qij
public class RecursionTest {
    

	public static void main(String[] args) {
    
		// TODO Auto-generated method stub
		// By printing questions , Review the recursive invocation mechanism 
		//test(4);
		
		int res = factorial(3);
		//System.out.println("res=" + res);
	}
	// recursive ： Printing problems 
	// The focus is on two kinds of output ：
	//  Yes else Judge output 2
	//  nothing else Output 2,3,4（ Look at the diagram ）
	public static void test(int n) {
    
		if (n > 2) {
    
			test(n - 1);
		}
		// Output ：
		//n=2
// else{
    
// System.out.println("n=" + n);
// }

		// Output ：
		//n=2
		//n=3
		//n=4
		System.out.println("n=" + n);
	}

	// Factorial problem 
	// The key is factorial(n - 1) Call to 
	public static int factorial(int n) {
    
		if (n == 1) {
     
			return 1;
		} else {
    
			return factorial(n - 1) * n; // 1 * 2 * 3
		}
	}


}

Maze problem

Code

package com.atguigu.recursion;

//author qij
public class MiGong {
    

   public static void main(String[] args) {
    
      //  First, create a two-dimensional array , Simulated maze 
      //  Map 
      int[][] map = new int[8][7];
      //  Use 1  Represents a wall 
      //  Set all up and down to 1
      for (int i = 0; i < 7; i++) {
    
         map[0][i] = 1;
         map[7][i] = 1;
      }

      //  Left and right are all set to 1
      for (int i = 0; i < 8; i++) {
    
         map[i][0] = 1;
         map[i][6] = 1;
      }
      // Set the baffle , 1  Express 
      map[3][1] = 1;
      map[3][2] = 1;
// map[1][2] = 1;
// map[2][2] = 1;
      
      //  Output map 
      System.out.println(" The situation of the map ");
      for (int i = 0; i < 8; i++) {
    
         for (int j = 0; j < 7; j++) {
    
            System.out.print(map[i][j] + " ");
         }
         System.out.println();
      }
      
      // Using recursive backtracking to find the way for the ball 
      setWay(map, 1, 1);
// setWay2(map, 1, 1);
      
      // Output a new map ,  The ball goes by , And marked recursion 
      System.out.println(" The ball goes by , And marked   The situation of the map ");
      for (int i = 0; i < 8; i++) {
    
         for (int j = 0; j < 7; j++) {
    
            System.out.print(map[i][j] + " ");
         }
         System.out.println();
      }
      
   }
   
   // Using recursive backtracking to find the way for the ball 
   // explain 
   //1. map  Represents a map 
   //2. i,j  Start from where on the map  (1,1)
   //3.  If the ball can reach  map[6][5]  Location , It means that the path has been found .
   //4.  Appointment ：  When map[i][j]  by  0  It means that the point has not been passed   When it comes to  1  Represents a wall  ; 2  It means the passage can go  ; 3  Indicates that the point has passed , But it doesn't work 
   //5.  In the maze , There needs to be a strategy ( Method )  Next -> Right -> On -> Left  ,  If that doesn't work , Backtracking 
   /** * * @param map  Represents a map  * @param i  Where to start looking for  * @param j * @return  If you find access , Just go back to true,  Otherwise return to false */
   public static boolean setWay(int[][] map, int i, int j) {
    
      if(map[6][5] == 2) {
     //  Access has been found ok
         return true;
      } else {
    
         if(map[i][j] == 0) {
     // If the current point has not been passed 
            // According to the strategy   Next -> Right -> On -> Left   go 
            map[i][j] = 2; //  Suppose that the point is accessible .
            if(setWay(map, i+1, j)) {
    // Go down 
               return true;
            } else if (setWay(map, i, j+1)) {
     // turn right 
               return true;
            } else if (setWay(map, i-1, j)) {
     // Up 
               return true;
            } else if (setWay(map, i, j-1)){
     //  turn left 
               return true;
            } else {
    
               // It shows that this point is not feasible , It's a dead end 
               map[i][j] = 3;
               return false;
            }
         } else {
     //  If map[i][j] != 0 ,  May be  1, 2, 3
            return false;
         }
      }
   }
   
   // Modify the pathfinding strategy , Change to   On -> Right -> Next -> Left 
   public static boolean setWay2(int[][] map, int i, int j) {
    
      if(map[6][5] == 2) {
     //  Access has been found ok
         return true;
      } else {
    
         if(map[i][j] == 0) {
     // If the current point has not been passed 
            // According to the strategy   On -> Right -> Next -> Left 
            map[i][j] = 2; //  Suppose that the point is accessible .
            if(setWay2(map, i-1, j)) {
    // Go up 
               return true;
            } else if (setWay2(map, i, j+1)) {
     // turn right 
               return true;
            } else if (setWay2(map, i+1, j)) {
     // Down 
               return true;
            } else if (setWay2(map, i, j-1)){
     //  turn left 
               return true;
            } else {
    
               // It shows that this point is not feasible , It's a dead end 
               map[i][j] = 3;
               return false;
            }
         } else {
     //  If map[i][j] != 0 ,  May be  1, 2, 3
            return false;
         }
      }
   }

}

Eight queens question

Ideas

1. The first queen put the first row first column

2. The second queen is in the second row, the first column 、 And decide whether or not OK[ That is, judgment is conflict ], If you don't OK, Keep it in the second column 、 The third column 、 Put all the columns in order , Find a fit

3. Continue with the third queen , Or the first column 、 Second column …… Until the first 8 A queen can also be placed in a non conflict position , A correct solution has been found

4. When we get a correct solution , When the stack goes back to the previous stack , It's going to start going back , About to be the first queen , Put all the correct solutions in the first column , Get it all .

5. Then go back to the first queen and put in the second column , Continue the loop later 1,2,3,4 Steps for

Code

package com.atguigu.recursion;

//author qij
public class Queue8 {
    

   // Define a max How many queens are there 
   int max = 8;
   // Define an array array,  Save the result of the Queen's placement , such as  arr = {0 , 4, 7, 5, 2, 6, 1, 3} 
   int[] array = new int[max];
   static int count = 0;
   static int judgeCount = 0;
   public static void main(String[] args) {
    
      // Test one  , 8 Is the queen right 
      Queue8 queue8 = new Queue8();
      queue8.check(0);
      System.out.printf(" Altogether %d solution ", count);
      System.out.printf(" Judge the number of conflicts %d Time ", judgeCount); // 1.5w
      
   }
   
   
   
   // Write a method , Place the second n A queen 
   // Particular attention ： check  yes   Every time you recurs , Enter into check There are  for(int i = 0; i < max; i++), So there will be backtracking 
   private void check(int n) {
    
      if(n == max) {
    
         //n = 8 ,  Actually 8 A queen is put away （n The value range is 0-7）, At this point, the output is ok 
         print();
         return;
      }
      
      // Put the queen in turn , And determine if there is a conflict 
      for(int i = 0; i < max; i++) {
    
         // First of all, the current queen  n ,  Put it at the end of the line 1 Column 
         array[n] = i;
         // Judge when placing the n A queen to i Column time , Conflict or not 
         if(judge(n)) {
     //  No conflict 
            // Go on n+1 A queen , It starts recursion 
            check(n+1); // 
         }
         // If conflict , Continue to implement  array[n] = i, It's going to be n A queen , Place in a backward position of the line 
      }
   }
   
   // See when we put the second n A queen ,  Check whether the queen conflicts with the queen placed in front of it 
   /** * * @param n  It means the first one n A queen  * @return */
   private boolean judge(int n) {
    
      judgeCount++;
      for(int i = 0; i < n; i++) {
    
         //  explain 
         //1. array[i] == array[n]  Said judgment   The first n Whether the queen and the front n-1 The queens are in the same line 
         //2. Math.abs(n-i) == Math.abs(array[n] - array[i])  Means to judge the n Whether a queen and the second i Is the queen on the same slash 
         //abs It's absolute value ; If slash , Line subtraction  =  Column subtraction 
         //3.  Judge if it's on the same line ,  There is no need to ,n  It's increasing every time 
         if(array[i] == array[n] || Math.abs(n-i) == Math.abs(array[n] - array[i]) ) {
    
            return false;
         }
      }
      return true;
   }
   
   // Write a method , You can output the position of the queen 
   private void print() {
    
      count++;
      for (int i = 0; i < array.length; i++) {
    
         System.out.print(array[i] + " ");
      }
      System.out.println();
   }

}