Shulou(Shulou.com)06/01 Report--

This article mainly introduces the relevant knowledge of "how to use Java data structure and algorithm to achieve recursion and backtracking". The editor shows you the operation process through an actual case. The operation method is simple, fast and practical. I hope this article "how to use Java data structure and algorithm to achieve recursion and backtracking" can help you solve the problem.

1. What is recursion?

To put it simply: recursion means that the method calls itself, passing in a different variable each time. Recursion helps programmers solve complex problems while making the code concise.

Look at a practical application scenario, maze problem (backtracking), recursion (Recursion)

Let me give you two small cases to help you understand recursion. Here we will review the recursive invocation mechanism.

Printing problem

Factorial problem

Public static void test (int n) {if (n > 2) {test (n-1);} System.out.println ("n =" + n);} public static int factorial (int n) {if (n = = 1) {return 1;} else {return factorial (n-1) * n;}}

What kind of problem is solved by recursion?

Various mathematical problems such as: 8 Queen problem, Tower of Hanoi, factorial problem, Maze problem, Ball and basket problem (google programming contest).

Recursion is also used in various algorithms, such as fast sorting, merge sorting, binary search, divide-and-conquer algorithm and so on.

The problem that will be solved with the stack-> the regression code is relatively concise.

Important rules to be followed by recursion

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

The local variables of the method are independent and do 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 that reference type is shared.

Recursion must approach to the condition of exit recursion, otherwise it will be infinitely recursive and StackOverflowError will appear.

When a method finishes executing or encounters a return, it returns, and the result is returned to whoever calls it, and when the method finishes or returns, the method finishes executing.

two。 Code case one-- the maze problem

Description: the path obtained by the ball is related to the path finding strategy set by the programmer, that is, when you get the ball path in the order of finding the way up and down and then get the ball path, you can first use it (lower right, upper left), and then change it to (upper right, lower left). See if the path has changed. Test the backtracking phenomenon.

Package com.szh.recursion; / * Maze problem * / public class MiGong {/ / use recursive backtracking to find the way for the ball, note: / / 1. Map represents the map / / 2. IMagnej indicates where to start on the map (1p1) / / 3. If the ball can reach the map [6] [5] position, the path is found. / / 4. Convention: when map [I] [j] is 0, it means that the point has not passed; when it is 1, it means the wall; 2, it means that the path can be taken; / / 5. When walking the maze, you need to determine a strategy (method) below-> right-> up-> left. If the point fails, then go back to public static boolean setWay (int [] [] map, int I, int j) {/ / at this time to the end of the maze if (map [6] [5] = = 2) {return true } else {if (map [I] [j] = = 0) {/ / if the current point has not passed / / follow the strategy below-> right-> up-> left 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)) {/ / on return true;} else {/ / left return true }} else {/ / map [I] [j]! = 0, that is, only 1, 2. 1 indicates the wall (unable to walk), 2 indicates that it has been passed, so return to false return false directly at this time. } / / modify the pathfinding strategy to top-> right-> bottom-> left public static boolean setWay2 (int [] [] map, int I, int j) {if (map [6] [5] = = 2) {/ / path has been found ok return true } else {if (map [I] [j] = = 0) {/ / if the current point has not passed / / follow the strategy up-> right-> bottom-> left map [I] [j] = 2; if (setWay2 (map, I-1, j)) {/ / upper return true } else if (setWay2 (map, I, j + 1)) {/ / right return true;} else if (setWay2 (map, I + 1, j)) {/ / Lower return true;} else {/ / left return true }} else {return false;}} public static void main (String [] args) {/ / first create a two-dimensional array to simulate the maze (map) int [] [] map = new int [8] [7] / / use part of the grid in the maze to represent the wall (set 1) / / the first and last rows are set to 1 for (int I = 0; I)

< 7; i++) { map[0][i] = 1; map[7][i] = 1; } //第一列和最后一列置为1 for (int i = 0; i < 8; i++) { map[i][0] = 1; map[i][6] = 1; } //多添加两块墙体 map[3][1] = 1; map[3][2] = 1;// map[1][2] = 1;// map[2][2] = 1; //输出地图查看 System.out.println("原始迷宫地图为："); 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);// setWay2(map, 1, 1); System.out.println("小球走过，并标识过的地图的情况："); for (int i = 0; i < 8; i++) { for (int j = 0; j < 7; j++) { System.out.print(map[i][j] + " "); } System.out.println(); } }} 3.代码案例二——八皇后问题 八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即：任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。

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

The second queen is placed in the first column of the second row, and then determines whether it is OK or not. 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 to be the third queen, or the first column and the second column. Until the eighth queen can also be placed in a non-conflict position, it is considered to have found a correct solution.

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

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

Package com.szh.recursion; / * eight queens problem * / public class Queue8 {/ / define the number of queens private int max = 8; / / define an array to save the position results placed by the queens, such as arr = {0,4,7,5,2,6,1,3} int [] array = new int [max]; / / how many solutions are there private static int count = 0 / / how many conflicts private static int judgeCount = 0; / / write a method to place the nth queen / / pay special attention to: every time check is recursive, there is a for (int I = 0; I < max) in check. Private void check (int n) {if (n = = max) {/ / n = 8, indicating that the eight queens have all put print (); return;} / / into the queens in turn, and determine whether there is a conflict between for (int I = 0; I < max) Array +) {/ / first put the current queen n in the first column of the row, check [n] = I; / / determine whether there is a conflict between if (judge (n)) {/ / no conflict / / and then put a queen in column I, and then start recursive queen (n = 1) } / / if there is a conflict, continue to execute array [n] = I That is to say, the nth queen will be placed in the column behind column I of this line. / / when we place the nth queen, we will check whether the queen conflicts with the previous one, private boolean judge (int n) {/ / each queen is cycled to compare with the previous position of the queen. See if it conflicts with for (int I = 0) I < n; array +) {/ / 1. Array [I] = = array [n] means to judge whether the nth queen is in the same column / / 2. Math.abs (nMuthi) = = Math.abs (Array [n]-array [I]) means to judge whether the nth queen and the I queen are in the same slash / / 3. It is not necessary to judge whether it is on the same line. N represents the number of queens, and this value is increasing every time, so it must not be on the same line if (array [I] = = array [n] | Math.abs (n-I) = = Math.abs (array [n]-array [I]) {judgeCount++; return false;}} return true } / / print the exact location of the empress private void print () {count++; for (int I = 0; I < array.length; iTunes +) {System.out.print (array [I] + ");} System.out.println ();} public static void main (String [] args) {Queue8 queue8 = new Queue8 () Queue8.check (0); System.out.printf ("Total% d solution\ n", count); System.out.printf ("Total number of% d conflicts", judgeCount);}}

In fact, the process of backtracking can be seen by Debug the code here, so I won't say much about it.

This is the end of the introduction to "how to use Java data structures and algorithms to achieve recursion and backtracking". Thank you for reading. If you want to know more about the industry, you can follow the industry information channel. The editor will update different knowledge points for you every day.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.