原文鏈接:傳送門

遞歸

迷宮問題(回溯)

概念

簡單吶的說: 遞歸就是方法自己調用自己,每次調用時傳入不同的變量,遞歸有助于編程者解決復雜的問題,同時讓代碼變得簡潔.

案例-遞歸調用機制

打印問題

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

遞歸調用規則:

1. 當程序執行到一個方法時,就會開辟一個獨立的空間(棧)

   

階乘問題

//階乘問題
public static int factorial(int n) {if (n == 1) {return 1;} else {return factorial(n - 1) * n; // 1 * 2 * 3}
}

斐波那契數列

這個也是可以用這個 遞歸實現的

經典案例

遞歸用于解決什么樣的問題

1. 各種數學問題如: 8皇后問題 , 漢諾塔, 階乘問題, 迷宮問題, 球和籃子的問題(google編程大賽)
2. 各種算法中也會使用到遞歸，比如快排，歸并排序，二分查找，分治算法等.
3. 將用棧解決的問題–>第歸代碼比較簡潔

遞歸需要遵守的重要規則

1. 執行一個方法時，就創建一個新的受保護的獨立空間(棧空間)
2. 方法的局部變量是獨立的，不會相互影響, 比如n變量
3. 如果方法中使用的是引用類型變量(比如數組)，就會共享該引用類型的數據.
4. 遞歸必須向退出遞歸的條件逼近，否則就是無限遞歸,出現StackOverflowError，死龜了:)
5. 當一個方法執行完畢，或者遇到return，就會返回，遵守誰調用，就將結果返回給誰，同時當方法執行完畢或者返回時，該方法也就執行完畢。

案例

球和籃子問題

你有幾個同樣的球，你希望把它放到幾個籃子里。每個籃子有相同的容量。給出int 型的baskets,代表籃子的數量。給出int型的 capacity，代表每個籃子的最大容量。給出int型的balls,表示歸類到籃子里的球的數量。返回值是把球歸類到籃子里的方式的數量。如果不能完全存放到籃子中，無法劃分，返回0。 籃子互不同，所有的球相同。因此，如果2個球放到2個籃子里，你可以采用3種方式，即(0, 2), (1, 1), 或 (2, 0)

原文鏈接:傳送門