One , brief introduction
Recursion is when a method calls itself , Different parameters are passed in each call , Recursion helps programmers solve complex problems , At the same time, it can make the code concise .
<> Two , Introduce the concept of recursion with an example
public static void test(int n){ if(n>2){ test(n-1); }
System.out.println("n="+n); }
Take a look , very low, It's simple ,4,3,2 undoubtedly .
To test my intelligence , Output one
Three , Recursive call rule （ Very important ）
1, When executing a method , Create a new protected independent space （ Stack space ）;
2, The local variables of the method are independent , It won't affect each other , For example, variables n;
3, If a reference type variable is used in the method （ Like arrays ）, Data of that reference type is shared ;
4, Recursion must approach the condition of exit recursion , Otherwise it's infinite recursion ,StackOverflowError;
5, When a method is executed , Or encounter return, Will return , The result will be returned to whoever calls , At the same time, when the method is finished or return Time , The method is completed .
Four , What kind of problems can recursion solve
<>1, Various mathematical problems
For example, eight queens , Hanota , Factorial problem , Maze problem , The problem of the ball and basket （Google Programming Contest ）.
<>2, Recursion is also used in various algorithms
For example, fast line , Merge sort , Binary search , Divide and conquer algorithm .
<>3, Stack to solve the problem can use recursion
The code is more concise .
Five , Maze problem
1, code implementation
package dataStructure.recursion; public class Labyrinth { public static void
main(String[] args) { // Maze problem //0 It means that the point has not been passed should be 1 Represents a wall ; 2 It means the passage can go ; 3
Indicates that the point has passed , But it doesn't work int[][] map = new int[8][7]; for(int i=0;i<8;i++){ for (int j =
0; j < 7; j++) { map[0][j] = 1; map[7][j] = 1; map[i][0] = 1; map[i][6] = 1; }
} // Setting the baffle , 1 express map[3][1] = 1; map[3][2] = 1; for (int i = 0; i < 8; i++) { for
(int j = 0; j < 7; j++) { System.out.print(map[i][j]+" "); }
System.out.println(); } setWay(map,1,1); System.out.println(" Map after maze "); 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 Indicates where to start on the map (1,1) //3. If the ball gets there map[6][5]
position , The path is found . //4. appointment ： When map[i][j] by 0 It means that the point has not been passed should be 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 , A strategy needs to be identified ( method ) lower -> right -> upper -> Left , If that point doesn't work , Looking back private static
boolean setWay(int[][] map,int i,int j){ if(map[6][5] == 2){ return true;
}else{ if(map[i][j]==0){ map[i][j] = 2; if(setWay(map,i+1,j)){// lower return true;
}else if(setWay(map,i,j+1)){// right return true; }else if(setWay(map,i-1,j)){// upper
return true; }else if(setWay(map,i,j-1)){// Left return true; }else{ map[i][j] = 3;
return false; } }else { return false; } } } }
2, console output
notes ：1 Represents a wall ,2 It means the way you are going ,0 It means no way .
This is quite simple !
Every blog is an experience , The trace of programming career , Knowledge change destiny , You have to control your own destiny , May you travel half your life , Return is still young .
More haste, less speed. , To achieve is to speed !
Technology
Daily Recommendation