# Data structure and algorithm (XI) -- algorithm recursion

Craftsman-L 2021-09-15 07:46:02
data structure algorithm xi algorithm

## 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);
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

### 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```

https://javamana.com/2021/09/20210909132313688l.html