Recursive application scenario
Look at a practical application scenario, maze problem (backtracking), recursion
The concept of recursion
In short: recursion is that the method calls itself and passes in different variables each time. Recursion helps programmers solve complex problems and make the code concise.
Recursive call mechanism

Print problem

Factorial problem

The recursive call mechanism is illustrated graphically
 Code demonstration
public class recursion { public static void main(String[] args) { //print(4); System.out.println(factorial(3)); } public static void print(int n) { if (n > 2) { print(n1); } // else cannot be added here System.out.println(n); } public static int factorial(int n) { if(n > 1) { return n*factorial(n1); } else { return 1; } } }
What kind of problems can recursion solve
What kind of problem is recursion used to solve

Various mathematical problems, such as:
 8 Queen Problem
 Hanoi
 Factorial problem
 Maze problem
 Ball and basket problem (google programming contest)

Recursion is also used in various algorithms, such as:
 Quick row
 Merge sort
 Binary search
 Divide and conquer algorithm, etc

Problems to be solved with stack – > recursive code is relatively concise
Important rules for recursion
Important rules for recursion

When a method is executed, a new protected independent space (stack space) is created

The local variables of the method are independent and will not affect each other, such as n variables

If a reference type variable (such as an array) is used in the method, the data of the reference type will be shared

Recursion must approach the condition of exiting recursion, otherwise it is infinite recursion. StackOverflowError appears and the turtle is dead:)

When a method is executed or returns, it will return. The result will be returned to the person who calls it. At the same time, when the method is executed or returned, the method will also be executed
 Recursive basis, exit condition
 Approximation to recursive basis
Recursive maze problem
Maze problem
Code implementation:
public class MiGong { public static void main(String[] args) { // First create a twodimensional array to simulate the maze // Map int[][] map = new int[8][7]; // Use 1 for walls // Set up and down to 1 for (int i = 0; i < 7; i++) { map[0][i] = 1; map[7][i] = 1; } // All left and right are set to 1 for (int i = 0; i < 8; i++) { map[i][0] = 1; map[i][6] = 1; } //Set baffle, 1 indicates map[3][1] = 1; map[3][2] = 1; // map[1][2] = 1; // map[2][2] = 1; // Output map System.out.println("Map situation"); for (int i = 0; i < 8; i++) { for (int j = 0; j < 7; j++) { System.out.print(map[i][j] + " "); } System.out.println(); } //Use recursive backtracking to find the way for the ball //setWay(map, 1, 1); setWay(map, 1, 1); //Output a new map, the ball passes, and identifies the recursion System.out.println("The ball walked past and marked 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(); } } /** * Use the pass back to find the way for the ball * @param map Represent map * @param i Where do you start * @param j * @return If it can go through, it returns true; otherwise, it returns false * * explain * 1. map Represent map * 2. 0 Indicates the road that has not been taken, 1 indicates the wall, 2 indicates the road that can be taken, and 3 indicates that it cannot be taken * 3. When map[6][5] == 2, it means walking out of the maze * 4. Set the route strategy: down, right, up and left. If the point fails, go back */ public static boolean setWay(int[][] map, int i, int j ){ // Recursive basis if (map[6][5] == 2) { return true; } else { // Approximation to recursive basis if (map[i][j] == 0) { // It shows that this point is still a walk, try to walk map[i][j] = 2; // Go down and return true // If else guarantees backtracking if (setWay(map, i+1, j)) { // This statement is after the recursive statement. You can go deep from this recursive statement until you find the one that returns true in turn // If it goes well, then it recurses down this statement to get out of the maze, and the route is a straight line // If there is a false in the middle, return to the next layer, go right to the previous layer, and then go down recursively after entering the right layer return true; } else if (setWay(map, i, j+1)) { return true; } else if (setWay(map, i1, j)) { return true; } else if (setWay(map, i, j1)) { return true; } else { map[i][j] = 3; return false; } } else { // That is, when map[i][j] is 1, 2 and 3, it doesn't work // Exit condition return false; } } } }
Discussion on maze problem

The path obtained by the ball is related to the path finding strategy set by the programmer, that is, the order of up, down, left and right

When getting the ball path again, you can first use (lower right, upper left), and then change it to (upper right, lower left) to see if the path has changed

Test backtracking phenomenon

Thinking: how to find the shortest path? Ideas  code implementation
Recursive eight queens problem (backtracking algorithm)
Problem introduction
The eight queens problem is an ancient and famous problem and a typical case of backtracking algorithm. The problem was put forward by international chess player Max Bethel in 1848: in August × Eight queens are placed on the 8grid chess so that they can't attack each other, that is, any two Queens can't be in the same row, the same column or the same slash. Ask how many kinds of placement * * (92) * *.
Train of thought analysis

The first queen puts the first row and the first column first

The second queen is placed in the first column of the second row, and then judge whether it is OK. If it is not OK, continue to put it in the second column and the third column, and put all the columns in turn to find a suitable one

Continue the third queen, or the first and second columns... Until the eighth queen can also be placed in a non conflict position, it can be regarded as finding a correct solution

When a correct solution is obtained, when the stack returns to the previous stack, it will start backtracking, that is, the first queen will get all the correct solutions put in the first column

Then go back and continue to put the first queen in the second column, and then continue to cycle through steps 1, 2, 3 and 4

Sketch Map:
explain:
Theoretically, a twodimensional array should be created to represent the chessboard, but in fact, the problem can be solved by using a onedimensional array through the algorithm. Arr [8] = {0, 4, 7, 5, 2, 6, 1, 3}. The corresponding arr subscript indicates the row, that is, the queen, arr [i] = Val, Val indicates the I + 1st queen, which is placed in column val+1 of row i+1
code implementation
public class Queen { //Define a max to indicate how many queens there are int max = 8; //Define the array array to save the results of the Queen's placement position, 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 whether the 8 Queen is correct Queen queen = new Queen(); queen.check(0); System.out.printf("Altogether%d solution", count); System.out.printf("Total number of conflicts judged%d second", judgeCount); // 1.5w } /** * Place queen * @param n Represents the nth queen */ public void check(int n){ if (n == max) { // Because the array starts from 0, when n == 8, it means that the 8th queen has been put print(); return; } // Because of this for loop, the algorithm will start backtracking from the last layer // for (int i = 0; i < max; i++) { // First, put the queen first array[n] = i; // Because array[n] has been copied, after n is passed in, judge calls array[n] to get this value // Then compare with the previous lines in turn if (!judge(n)) { // If there is no conflict, put down one check(n+1); } // In case of conflict, change to the next column // When the last line, line 8, is also successful, that is, n = 8, it will return layer by layer // The return of each layer will continue to execute the for loop to generate backtracking and obtain the total number of solutions of each layer } } /** * Judge whether this point conflicts with other points * @param n Represents the nth queen * @return true Indicates conflict, false indicates no conflict */ public boolean judge(int n) { judgeCount++; for (int i = 0; i < n; i++) { // Determine whether they are in the same column // It is no longer necessary to judge whether it is on the same line // Use the slope to judge whether it is on the same slash if (array[i] == array[n]  Math.abs(in) == Math.abs(array[i]  array[n]) ) { return true; } } return false; } /** * Print out the successful scheme array */ public void print() { count++; for (int i = 0; i < array.length; i++) { System.out.print(array[i]+" "); } System.out.println(); } }