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(n-1);
}
// else cannot be added here
System.out.println(n);
}
public static int factorial(int n) {
if(n > 1) {
return n*factorial(n-1);
} 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 two-dimensional 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, i-1, j)) {
return true;
} else if (setWay(map, i, j-1)) {
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 8-grid 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 two-dimensional array should be created to represent the chessboard, but in fact, the problem can be solved by using a one-dimensional 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(i-n) == 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();
}
}