設(shè)一個未知函數(shù)f潦匈，用其自身構(gòu)成的已知函數(shù)g來定義：
f(n)=g(n ,f(n-1))??????n>0
f(0)=a?????????????????????n=0
???????為了定義f(n)无埃，必須先定義f(n-1)针贬，為了定義f(n-1)，又必須先定義f(n-2)··· ···俏让，上述這種用自身的簡單情況來定義自己的方式稱為遞歸定義。
???????一個遞歸定義必須是有確切含義的茬暇，也就是說首昔，必須一步比一步簡單，最后是有終結(jié)的而钞，決不能無限循環(huán)下去沙廉。在f(n)的定義中，當(dāng)n為0時定義一個已知數(shù)a臼节，是最簡單的情況撬陵，稱為遞歸邊界，它本身不再使用遞歸的定義网缝。
???????與遞推一樣巨税，每一個遞歸定義都有其邊界條件。但不同的是粉臊，遞推是由邊界條件出發(fā)草添，通過遞推式求f(n)的值，從邊界到求解的全過程十分清楚扼仲；而遞歸則是從函數(shù)自身出發(fā)來達到邊界條件远寸。在通往邊界條件的遞歸調(diào)用過程中，系統(tǒng)用堆棧把每次調(diào)用的中間結(jié)果（局部變量和返回地址值）保存起來屠凶，直至求出遞歸邊界值f(0)=a驰后。然后返回調(diào)用函數(shù)。返回過程中矗愧，中間結(jié)果相繼椩钪ィ恢復(fù)，f(1) = g(1 ,a) —> f(2) = g(2, f(1)) —> ··· —>直至求出f(n) = g(n , f(n - 1))。
遞歸按其調(diào)用方式分：
- 直接遞歸 — 遞歸過程P直接自己調(diào)用自己夜涕；
- 間接遞歸 — 即P包含另一過程D犯犁，而D又調(diào)用P；
遞歸算法適用的一般場合為：
- 數(shù)據(jù)的定義形式按遞歸定義女器。
如裴波那契數(shù)列的定義： fn=fn-1 + fn-2; f0=1; f1=2酸役。
對應(yīng)的遞歸程序?qū)崿F(xiàn)為：
public class FibonacciImpl {
public static void main(String[] args) {
final int n = 10;
for (int i = 0; i < n; i++ ){
System.out.print(fibonacci(i) + " ");
}
}
private static int fibonacci(int n) {
if (n == 0) {
return 1;
}
if (n == 1) {
return 2;
}
return (fibonacci(n - 2) + fibonacci(n - 1));
}
}
結(jié)果為：
1 2 3 5 8 13 21 34 55 89
- 數(shù)據(jù)之間的關(guān)系（即數(shù)據(jù)結(jié)構(gòu)）按遞歸定義。如樹的遍歷晓避，圖的搜索等簇捍。
- 問題解法按遞歸算法實現(xiàn)。例如回溯法等俏拱。
對于2暑塑，3，可利用堆棧結(jié)構(gòu)將其轉(zhuǎn)換為非遞歸算法锅必。
