輕輕松松學遞歸

概念

程序調用自身的編程技巧稱為遞歸(Recursion)。遞歸做為一種算法在程序設計語言中廣泛應用。 一個過程或函數在其定義或說明中有直接或間接調用自身的一種方法，它通常把一個大型復雜的問題層層轉化為一個與原問題相似的規模較小的問題來求解，遞歸策略只需少量的程序就可描述出解題過程所需要的多次重復計算，大大地減少了程序的代碼量。遞歸的能力在于用有限的語句來定義對象的無限集合。一般來說，遞歸需要有邊界條件、遞歸前進段和遞歸返回段。當邊界條件不滿足時，遞歸前進；當邊界條件滿足時，遞歸返回。

遞歸調用機制

我們來看一個案例：

public class RecursionTest { public static void main(String[] args) { test(5); } public static void test(int num) { if (num > 2) { test(num - 1); } System.out.println("num = " + num); } }

1

2

3

4

5

6

7

8

9

10

11

12

13

若是你能在考慮片刻后得到結果，說明遞歸的基本思想你還沒有忘記。

遞歸的調用規則：當程序執行到一個方法時，就會在棧中開辟一個獨立的空間。

運行過程如果所示，需要注意的是，在每次遞歸調用的過程中，都回去棧中開辟獨立的空間，而每個空間中的變量是獨立的，互不影響的。而我們知道，棧結構是先進后出的，所以此時會先從test(2)開始從上往下執行，最后的執行結果則為：

n = 2 n = 3 n = 4 n = 5

1

2

3

4

遞歸規則

通過遞歸能夠幫助我們解決實際開發中的很多問題。

You have several identical balls that you wish to place in several baskets. Each basket has the same maximum capacity. You are given an int baskets, the number of baskets you have. You are given an int capacity, the maximum capacity of each basket. Finally you are given an int balls, the number of balls to sort into baskets. Return the number of ways you can divide the balls into baskets. If this cannot be done without exceeding the capacity of the baskets, return 0.

Each basket is distinct, but all balls are identical. Thus, if you have two balls to place into two baskets, you could have (0, 2), (1, 1), or (2, 0), so there would be three ways to do this.

這是一道Google的編程大賽題目，題目意思是：

你有幾個相同的球，你希望放在幾個籃子里。每個籃子都有相同的最大容量。給出一個int型的baskets，代表籃子的數量。給出一個int型的capacity，代表每個籃子的最大容量。最后，給出int型的balls，表示歸類到籃子里的球的數量。返回值是把球歸類到籃子里的方式的數量。如果這不能在不超過籃子容量的情況下完成，返回0。

每個籃子是不同的，但所有的球是相同的。因此，如果你有兩個球要放到兩個籃子里，你可以有(0,2)(1,1)或(2,0)三種方法。

這道題就能通過遞歸來完美地解決，但在這里不對該題作專門講解。

從上面來看，我們需要知道遞歸必須遵守的規則：

執行一個方法時，就會在棧中創建一個新的受保護的獨立空間

方法的局部變量是獨立的，互不影響的

如果方法中使用的是引用類型變量(比如數組)，就會共享該引用類型的數據

遞歸必須向退出退出遞歸的條件逼近，否則就是無限遞歸

當一個方法執行完畢，或者遇到return時，就會返回，遵守誰調用，就將結果返回誰的規則。同時，當方法執行完畢或返回時，該方法也就執行完畢

迷宮回溯問題

對于遞歸有了一個簡單的復習了解之后，我們用遞歸來解決一些編程中的經典問題，我們先看一個迷宮回溯問題。

迷宮回溯問題說的是：

在這樣的一個迷宮中，紅色代表墻壁，現在有一個紅色的小球，要求從開始位置出發，解出到出口位置的最短路徑。

要想解決這樣一個問題，我們首先得制定一個策略，決定小球的行走順序，我們規定：

先走下面，倘若下面走不通，就走右面；倘若右面走不通，就走上面；倘若上面走不通，就走左面。

你們在具體實現的時候不需要和我的策略一樣，這只是一種解題方式。

代碼如下：

public class MazeBack { public static void main(String[] args) { // 創建一個二維數組，模擬迷宮 int[][] map = new int[8][7]; // 約定1為墻壁 // 上下置為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; System.out.println("原始地圖："); for (int[] temp : map) { for (Integer i : temp) { System.out.print(i + " "); } System.out.println(); } //遞歸尋找路徑 findWay(map, 1, 1); System.out.println("小球行走路徑："); for (int[] temp : map) { for (Integer i : temp) { System.out.print(i + " "); } System.out.println(); } } /** * 使用遞歸求出迷宮路徑 如果小球能夠到map[6][5]，則證明找到正確路徑 * 我們約定當map[i][j]為0表示墻，為1表示當前位置沒有走過，為2表示當前位置可以走通，為3表示當前位置已經走過，但走不通 * * @param map 地圖 * @param i 出發點 * @param j 出發點 * @return 如果找到正確路徑，返回true，否則返回false */ public static boolean findWay(int[][] map, int i, int j) { if (map[6][5] == 2) { // 此時說明路徑已經找到 return true; } else { if (map[i][j] == 0) { // 此時說明當前位置還沒有走過 // 按照策略走 map[i][j] = 2;// 假設這個位置是可以走通的 if (findWay(map, i + 1, j)) {// 在該點的基礎上向下走 return true; } else if (findWay(map, i, j + 1)) {// 在該點的基礎上向右走 return true; } else if (findWay(map, i - 1, j)) {// 在該點的基礎上向上走 return true; } else if (findWay(map, i, j - 1)) {// 在該點的基礎上向左走 return true; } else { // 此時說明map[i][j]是走不通的 map[i][j] = 3;// 將map[i][j]置為3 return false; } } else { // 如果map[i][j]不為0，它還有可能為1、2和3 return false; } } } }

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

運行結果：

原始地圖： 1 1 1 1 1 1 1 1 0 0 0 0 0 1 1 0 0 0 0 0 1 1 1 1 0 0 0 1 1 0 0 0 0 0 1 1 0 0 0 0 0 1 1 0 0 0 0 0 1 1 1 1 1 1 1 1 小球行走路徑： 1 1 1 1 1 1 1 1 2 0 0 0 0 1 1 2 2 2 0 0 1 1 1 1 2 0 0 1 1 0 0 2 0 0 1 1 0 0 2 0 0 1 1 0 0 2 2 2 1 1 1 1 1 1 1 1

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

數字2所表示的位置則形成了一條正確的行走路徑。

這個程序有一定的難度，需要一定的時間消化，我們一起來分析一下，幫助理解：

首先小球起點為[1][1]，那么就會進入else分支，那么首先我們就假設小球所在的位置是可以走通的，所以將其值置為2，然后我們在該位置的基礎上按照我們的策略，即：下→右→上→左的方式進行摸索，所以將i+1，j作為出發點調用其自身，作遞歸處理，步驟和前面相同。

此時在向下摸索的過程中發現，下面的位置是走不通的，因為是墻，所以它會向右繼續摸索，那么當然又是遞歸調用，將i，j+1作為出發點調用其自身。

小球在該位置繼續向下摸索，發現走不通，就向右摸索，發現能走通，就繼續走，然后又向下摸索，依次類推，直至走到出口，所以小球行走路徑為：

有細心的人可能就發現了，在這個程序中并沒有回溯啊，確實，因為這個迷宮相對簡單，在尋找的過程中并沒有出現回溯，而是能很順利地依次執行。

我們來看一個極端的情況：

假設是這樣的一個情況，我們把小球直接堵死，也就是讓

map[1][2] = 1; map[2][2] = 1;

1

2

我們再來運行剛才的程序，結果為：

原始地圖： 1 1 1 1 1 1 1 1 0 1 0 0 0 1 1 0 1 0 0 0 1 1 1 1 0 0 0 1 1 0 0 0 0 0 1 1 0 0 0 0 0 1 1 0 0 0 0 0 1 1 1 1 1 1 1 1 小球行走路徑： 1 1 1 1 1 1 1 1 3 1 0 0 0 1 1 3 1 0 0 0 1 1 1 1 0 0 0 1 1 0 0 0 0 0 1 1 0 0 0 0 0 1 1 0 0 0 0 0 1 1 1 1 1 1 1 1

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

可以看到，小球行走路徑中出現了數字3，這說明在這次的路徑尋找過程中是出現了回溯的。因為在小球起點往下走了之后，它發現下面走不通，右面走不通，上面走過了，左面也走不通，此時認為該位置已經走過但是走不通，所以將其值置為3。此時程序會返回，返回到上一次的位置(即起點)，也就是回溯了，然后繼續摸索，發現仍然走不通，所以將該位置也置為3。

上面只是簡單實現了迷宮的路徑尋找問題，接下來我們來看看如何尋找迷宮中的最短路徑。

尋找迷宮中的最短路徑思想非常簡單，即改變摸索策略，例如我們將摸索策略由下→右→上→左改為上→右→下→左，此時代碼修改為：

public static boolean findWay(int[][] map, int i, int j) { if (map[6][5] == 2) { return true; } else { if (map[i][j] == 0) { map[i][j] = 2; if (findWay(map, i - 1, j)) {// 在該點的基礎上向上走 return true; } else if (findWay(map, i, j + 1)) {// 在該點的基礎上向右走 return true; } else if (findWay(map, i + 1, j)) {// 在該點的基礎上向下走 return true; } else if (findWay(map, i, j - 1)) {// 在該點的基礎上向左走 return true; } else { map[i][j] = 3;// 將map[i][j]置為3 return false; } } else { return false; } } }

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

然后運行程序，結果為：

原始地圖： 1 1 1 1 1 1 1 1 0 0 0 0 0 1 1 0 0 0 0 0 1 1 1 1 0 0 0 1 1 0 0 0 0 0 1 1 0 0 0 0 0 1 1 0 0 0 0 0 1 1 1 1 1 1 1 1 小球行走路徑： 1 1 1 1 1 1 1 1 2 2 2 2 2 1 1 0 0 0 0 2 1 1 1 1 0 0 2 1 1 0 0 0 0 2 1 1 0 0 0 0 2 1 1 0 0 0 0 2 1 1 1 1 1 1 1 1

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

這樣小球的行走路徑也會相應的變化，我們只需要得出每個策略的行走路徑，并用數組將每個策略得到的數值2記錄下來，最后比較一下數組中哪個包含數值2最少，其對應的路徑即為最短路徑。

八皇后問題

看完迷宮回溯問題之后，可能有些人會有點懵，所以，這里我再講解一個比較經典的遞歸問題，希望大家能夠更快掌握遞歸。

八皇后問題是一個古老而著名的問題，是回溯算法的典型案例。該問題是國際西洋棋手馬克斯·貝瑟爾于1848年提出。說的是在8X8格的國際象棋棋盤上擺放八個皇后，使其不能相互攻擊，即：任意兩個皇后都不能處于同一行、同一列或同一斜線上，問有多少種擺法。

我們先來玩一個游戲，了解一下八皇后問題：

這是一個錯誤示范，即兩個皇后不允許處于同一行、同一列或同一斜線。

接下來我們看一個正確擺法：

通過這個游戲我們不難理解八皇后問題的規則，接下來我們分析一下八皇后問題的算法思路：

第一個皇后先放第一行或第一列

第二個皇后放在第二行第一列，然后能否放置，如果不能，就放在第二列，繼續判斷，若不能放置，則放在第三列，以此類推，直至找到合適的位置

第三個皇后也按第二步驟不斷尋找，第四個皇后也如此，直至第八個皇后也找到了一個與其它皇后不沖突的地方，此時找到了一個正確解

當得到一個正確解之后，在棧回退到上一個棧時，就會開始回溯，即：將第一個皇后，放到第一列的所有正確解全部得到

然后第一個皇后放到第二列，后面重復執行1、2、3、4步驟

需要知道的是，在回溯的時候，我們是從最后一個皇后開始，不斷地尋找不和其它皇后沖突的位置，當回溯完成后，即找到了第一個皇后放在第一列的所有解。

代碼如下：

public class EightQueue { //定義一個max表示共有多少個皇后 int max = 8; //定義數組array, 保存皇后放置位置的結果,比如 arr = {0 , 4, 7, 5, 2, 6, 1, 3} int[] array = new int[max]; static int count = 0; static int judgeCount = 0; public static void main(String[] args) { EightQueue queue8 = new EightQueue(); queue8.check(0); System.out.printf("一共有%d解法", count); System.out.printf("一共判斷沖突的次數%d次", judgeCount); // } //編寫一個方法，放置第n個皇后 //特別注意： check 是 每一次遞歸時，進入到check中都有 for(int i = 0; i < max; i++)，因此會有回溯 private void check(int n) { if(n == max) { //n = 8 , 八個皇后已放置完畢 print(); return; } //依次放入皇后，并判斷是否沖突 for(int i = 0; i < max; i++) { //先把當前這個皇后 n , 放到該行的第1列 array[n] = i; //判斷當放置第n個皇后到i列時，是否沖突 if(judge(n)) { // 不沖突 //接著放n+1個皇后,即開始遞歸 check(n+1); // } //如果沖突，就繼續執行 array[n] = i; 即將第n個皇后，放置在本行的后一個位置 } } //查看當我們放置第n個皇后, 就去檢測該皇后是否和前面已經擺放的皇后沖突 /** * * @param n 表示第n個皇后 * @return */ private boolean judge(int n) { judgeCount++; for(int i = 0; i < n; i++) { // 說明 //1. array[i] == array[n] 表示判斷 第n個皇后是否和前面的n-1個皇后在同一列 //2. Math.abs(n-i) == Math.abs(array[n] - array[i]) 表示判斷第n個皇后是否和第i皇后是否在同一斜線 // n = 1 放置第 2列 1 n = 1 array[1] = 1 // Math.abs(1-0) == 1 Math.abs(array[n] - array[i]) = Math.abs(1-0) = 1 //3. 判斷是否在同一行, 沒有必要，n 每次都在遞增 if(array[i] == array[n] || Math.abs(n-i) == Math.abs(array[n] - array[i]) ) { return false; } } return true; } //寫一個方法，可以將皇后擺放的位置輸出 private void print() { count++; for (int i = 0; i < array.length; i++) { System.out.print(array[i] + " "); } System.out.println(); } }

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

運行結果為：

0 4 7 5 2 6 1 3 0 5 7 2 6 3 1 4 0 6 3 5 7 1 4 2 0 6 4 7 1 3 5 2 1 3 5 7 2 0 6 4 1 4 6 0 2 7 5 3 1 4 6 3 0 7 5 2 1 5 0 6 3 7 2 4 1 5 7 2 0 3 6 4 1 6 2 5 7 4 0 3 1 6 4 7 0 3 5 2 1 7 5 0 2 4 6 3 2 0 6 4 7 1 3 5 2 4 1 7 0 6 3 5 2 4 1 7 5 3 6 0 2 4 6 0 3 1 7 5 2 4 7 3 0 6 1 5 2 5 1 4 7 0 6 3 2 5 1 6 0 3 7 4 2 5 1 6 4 0 7 3 2 5 3 0 7 4 6 1 2 5 3 1 7 4 6 0 2 5 7 0 3 6 4 1 2 5 7 0 4 6 1 3 2 5 7 1 3 0 6 4 2 6 1 7 4 0 3 5 2 6 1 7 5 3 0 4 2 7 3 6 0 5 1 4 3 0 4 7 1 6 2 5 3 0 4 7 5 2 6 1 3 1 4 7 5 0 2 6 3 1 6 2 5 7 0 4 3 1 6 2 5 7 4 0 3 1 6 4 0 7 5 2 3 1 7 4 6 0 2 5 3 1 7 5 0 2 4 6 3 5 0 4 1 7 2 6 3 5 7 1 6 0 2 4 3 5 7 2 0 6 4 1 3 6 0 7 4 1 5 2 3 6 2 7 1 4 0 5 3 6 4 1 5 0 2 7 3 6 4 2 0 5 7 1 3 7 0 2 5 1 6 4 3 7 0 4 6 1 5 2 3 7 4 2 0 6 1 5 4 0 3 5 7 1 6 2 4 0 7 3 1 6 2 5 4 0 7 5 2 6 1 3 4 1 3 5 7 2 0 6 4 1 3 6 2 7 5 0 4 1 5 0 6 3 7 2 4 1 7 0 3 6 2 5 4 2 0 5 7 1 3 6 4 2 0 6 1 7 5 3 4 2 7 3 6 0 5 1 4 6 0 2 7 5 3 1 4 6 0 3 1 7 5 2 4 6 1 3 7 0 2 5 4 6 1 5 2 0 3 7 4 6 1 5 2 0 7 3 4 6 3 0 2 7 5 1 4 7 3 0 2 5 1 6 4 7 3 0 6 1 5 2 5 0 4 1 7 2 6 3 5 1 6 0 2 4 7 3 5 1 6 0 3 7 4 2 5 2 0 6 4 7 1 3 5 2 0 7 3 1 6 4 5 2 0 7 4 1 3 6 5 2 4 6 0 3 1 7 5 2 4 7 0 3 1 6 5 2 6 1 3 7 0 4 5 2 6 1 7 4 0 3 5 2 6 3 0 7 1 4 5 3 0 4 7 1 6 2 5 3 1 7 4 6 0 2 5 3 6 0 2 4 1 7 5 3 6 0 7 1 4 2 5 7 1 3 0 6 4 2 6 0 2 7 5 3 1 4 6 1 3 0 7 4 2 5 6 1 5 2 0 3 7 4 6 2 0 5 7 4 1 3 6 2 7 1 4 0 5 3 6 3 1 4 7 0 2 5 6 3 1 7 5 0 2 4 6 4 2 0 5 7 1 3 7 1 3 0 6 4 2 5 7 1 4 2 0 6 3 5 7 2 0 5 1 4 6 3 7 3 0 2 5 1 6 4 一共有92解法一共判斷沖突的次數15720次

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

從運行結果也可以看出，它先將第一個皇后在第一列放置的所有解得到，然后獲得第二列，接著第三列，直至最后一列。

理論上應該創建一個二維數組表示棋盤，但是實際上也可以通過算法，用一個一維數組來表示。例如：arr[8] = {0，4，7，5，2，6，1，3}，其中arr[i] = value，value表示第i+1個皇后放在第i+1行的第value+1列。

這樣，關于八皇后問題的算法實現也就完成了，算法思想會有點繞，要理解確實有難度。

遞歸的缺點

從八皇后問題可以知道，一個8X8的棋盤，解決沖突的次數就高達一萬多次，所以遞歸也是有很大缺陷的，具體缺點如下：

遞歸由于是函數調用自身，而函數調用是有時間和空間的消耗的：每一次函數調用，都需要在棧中分配空間

遞歸中有很多重復進行的計算，由于其本質是把一個問題分解成兩個或者多個小問題，多個小問題存在相互重疊的部分

遞歸經常會出現棧溢出問題，因為每一次方法的調用都會在棧中分配空間，而每個進程的棧的容量是有限的，當調用的層次太多時，就會超出棧的容量，從而導致棧溢出

數據結構

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。