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
©2019-2020 Toolsou All rights reserved,
Faster RCNN Explanation of series algorithm principle ( note ) Huawei certification HCIA-AI artificial intelligence Free download of documents : To introduce you to a few useful free download URL CSS architecture design MySQL An interview is a must !TP6 Application examples of verifier and correct verification data China Lunar Rover “ Moon rabbit No.2 ” A strange rock was found on the moon Programmer Tanabata Valentine's Day confession code A single key controls multiple water lamp states Jsp+Ajax+Servlet+Mysql Add, delete, modify and query ( one )