Data structure and algorithm (XI) -- algorithm recursion

Craftsman-L 2021-09-15 07:46:02

One 、 Introduce

1、 Introduce

recursive : Recursion is a method that calls itself , Different variables are passed in each call . Recursion helps programmers solve complex problems , At the same time, it can make the code concise .
The difference between iteration and recursion : Iterations use the loop structure , Selection structure used recursively . Using recursion can make the structure of the program clearer 、 More concise 、 It's easier to understand , This reduces the time to read the code . Its time complexity is the number of recursions .
But a lot of recursive calls create copies of functions , It will consume a lot of time and memory , Iteration does not require this effort .
Recursive functions are divided into call and fallback stages , The fallback order of recursion is the reverse order of its call order .

Divide and conquer : When a problem is large and difficult to solve , You can consider dividing the problem into several small modules , One by one .

2、 Case study

  • The problem of rabbit reproduction .( Fibonacci sequence ).
  • Calculation n! .
  • Reverse output of any length string .
  • Recursive implementation of half search algorithm .
  • The hanotta problem
  • Eight queens question

Two 、 Maze problem

problem : Find an effective path from the beginning to the end .

Code example : maze

 1 public class MiGong {
 2
 3 /**
 4  * 0: This point has not been passed , 1: Represents a wall , 2: You can go , 3: This point has passed , But it doesn't work \
 5  * Strategy : Next -> Right -> On -> Left , If that doesn't work , Backtracking
 6 */
 7 private int[][] map;
 8 private int desX;
 9 private int desY;
 10
 11 /**
 12  * structure row*col The maze of
 13  *
 14  * @param row That's ok
 15  * @param col Column
 16 */
 17 public MiGong(int row, int col) {
 18 if (row <= 0 || col <= 0) {
 19 return;
 20  }
 21
 22 map = new int[row][col];
 23
 24 // Default The up and down or so All walls 
 25 for (int i = 0; i < col; i++) {
 26 map[0][i] = 1;
 27 map[row - 1][i] = 1;
 28  }
 29
 30 for (int i = 0; i < row; i++) {
 31 map[i][0] = 1;
 32 map[i][col - 1] = 1;
 33  }
 34
 35  }
 36
 37 /**
 38  * Add a baffle inside the maze
 39  *
 40  * @param i Abscissa
 41  * @param j Ordinate
 42 */
 43 public void addBaffle(int i, int j) {
 44 if (map == null) {
 45 return;
 46  }
 47
 48 // There are walls all week 
 49 if (i > 0 && i < map.length - 1 && j > 0 && j < map[0].length - 1) {
 50 map[i][j] = 1;
 51  }
 52  }
 53
 54 /**
 55  * Set the end position of the maze
 56  *
 57  * @param desX Abscissa
 58  * @param desY Ordinate
 59 */
 60 public void setDes(int desX, int desY) {
 61 this.desX = desX;
 62 this.desY = desY;
 63  }
 64
 65 public boolean setWay(int i, int j) {
 66 // Access has been found 
 67 if (map[desX][desY] == 2) {
 68 return true;
 69 } else {
 70 if (map[i][j] != 0) {
 71 return false;
 72  }
 73
 74 // map[i][j] == 0 According to the strategy Next -> Right -> On -> Left recursive
 75 // Suppose that the point is accessible .
 76 map[i][j] = 2;
 77 if (setWay(i + 1, j)) {
 78 return true;
 79 } else if (setWay(i, j + 1)) {
 80 return true;
 81 } else if (setWay(i - 1, j)) {
 82 return true;
 83 } else if (setWay(i, j - 1)) {
 84 return true;
 85 } else {
 86 // It shows that this point is not feasible , It's a dead end 
 87 map[i][j] = 3;
 88 return false;
 89  }
 90  }
 91  }
 92
 93 // Show map 
 94 public void show() {
 95 for (int i = 0; i < map.length; i++) {
 96 for (int j = 0; j < map[0].length; j++) {
 97 System.out.print(map[i][j] + " ");
 98  }
 99  System.out.println();
100  }
101  }
102 }

Code example : Test class

 1 // Test class 
 2 public class Main {
 3
 4 public static void main(String[] args) {
 5 MiGong miGong = new MiGong(8, 7);
 6 miGong.addBaffle(3, 1);
 7 miGong.addBaffle(3, 2);
 8 miGong.setDes(6, 5); // Set the destination 
 9
10 System.out.println(" The initial map ");
11  miGong.show();
12 miGong.setWay(1, 1); // Set start position 
13
14 System.out.println(" The path of the ball , The situation of the map ");
15  miGong.show();
16  }
17 }
18
19 // result 
20  The initial map
21 1 1 1 1 1 1 1
22 1 0 0 0 0 0 1
23 1 0 0 0 0 0 1
24 1 1 1 0 0 0 1
25 1 0 0 0 0 0 1
26 1 0 0 0 0 0 1
27 1 0 0 0 0 0 1
28 1 1 1 1 1 1 1
29  The path of the ball , The situation of the map
30 1 1 1 1 1 1 1
31 1 2 0 0 0 0 1
32 1 2 2 2 0 0 1
33 1 1 1 2 0 0 1
34 1 0 0 2 0 0 1
35 1 0 0 2 0 0 1
36 1 0 0 2 2 2 1
37 1 1 1 1 1 1 1

3、 ... and 、 Eight queens question

problem : stay 8×8 GE's chess set eight queens , Make it impossible to attack each other , namely : No two Queens can be in the same line 、 On the same column or slash , Ask how many kinds of pendulum .

Code example : Eight queens

 1 public class Queue8 {
 2
 3 private static final int MAX = 8;
 4 // Save where the queen is placed , such as arr = {0, 4, 7, 5, 2, 6, 1, 3}
 5 private final int[] array = new int[MAX];
 6
 7 public static int count = 0;
 8 public static int judgeCount = 0;
 9
10 public void check() {
11 this.check(0);
12  }
13
14 // check It's every recursion , Enter into check There are for(int i = 0; i < max; i++), So there will be backtracking 
15 private void check(int n) {
16 // n = 8, Express 8 The queen has put it away 
17 if (n == MAX) {
18  print();
19 return;
20  }
21
22 for (int i = 0; i < MAX; i++) {
23 array[n] = i;
24
25 // Judge when placing the n A queen to i Column time , Conflict or not
26 // No conflict 
27 if (!judge(n)) {
28 // Go on n+1 A queen , It starts recursion 
29 check(n + 1);
30  }
31  }
32  }
33
34 private boolean judge(int n) {
35 judgeCount++;
36 for (int i = 0; i < n; i++) {
37 // The same column or The same slash 
38 if (array[i] == array[n] || Math.abs(n - i) == Math.abs(array[n] - array[i])) {
39 return true;
40  }
41  }
42 return false;
43  }
44
45 private void print() {
46 count++;
47 for (int i = 0; i < array.length; i++) {
48 System.out.print(array[i] + " ");
49  }
50  System.out.println();
51  }
52
53 }

Code example : Test class

 1 // Test class 
 2 public class Main {
 3
 4 public static void main(String[] args) {
 5 Queue8 queue8 = new Queue8();
 6  queue8.check();
 7
 8 System.out.printf(" Altogether %d solution ", Queue8.count);
 9 System.out.printf(" Judge the number of conflicts %d Time ", Queue8.judgeCount); // 1.5w
10  }
11 }

Four 、 The hanotta problem

1、 problem

2、 thought

If n = 1,A -> C
If n >= 2, It's always seen as two plates ,① The bottom plate .② All the disks above . be , step :
(1) First put all the plates on it A->B
(2) Put the bottom plate A->C
(3) hold B All the trays of the tower from B->C

3、 Code

Code example : The hanotta problem

 1 // Hanoi 
 2 public class Hanoitower {
 3
 4 // Using divide and conquer algorithm 
 5 public static void move(int num, char a, char b, char c) {
 6 // If there's only one dish 
 7 if (num == 1) {
 8 System.out.println(" The first 1 A dish from " + a + "->" + c);
 9 } else {
10 // n >= 2, It's always seen as two plates ,① The bottom plate .② All the disks above . be , step :
11
12 // 1. First put all the plates on it A->B. The movement process will use c
13 move(num - 1, a, c, b);
14 // 2. Put the bottom plate A->C
15 System.out.println(" The first " + num + " A dish from " + a + "->" + c);
16 // 3. hold B All the trays of the tower from B->C. The movement process will use a
17 move(num - 1, b, a, c);
18  }
19  }
20 }

Code example : Test class

 1 // Test class 
 2 public class Main {
 3 public static void main(String[] args) {
 4 Hanoitower.move(3, 'A', 'B', 'C');
 5  }
 6 }
 7
 8 // result 
 9 The first 1 A dish from A->C
10 The first 2 A dish from A->B
11 The first 1 A dish from C->B
12 The first 3 A dish from A->C
13 The first 1 A dish from B->A
14 The first 2 A dish from B->C
15 The first 1 A dish from A->C

 

Please bring the original link to reprint ,thank
Similar articles

2021-09-15

2021-09-15

2021-09-15