對于那些不知道遞歸是什么的人（并且像個笑聲一樣），請單擊以下鏈接：Google搜索：遞歸，然后單擊“您的意思是……”項。

希望您終于弄清楚了遞歸是指其自身的任何內容（如果不是，那么您可能會永遠瀏覽Google并試圖找出遞歸是什么！）。 遞歸的一個相當常見的例子是斐波那契數。 斐波納契數的模式是將前兩個項與下一個項相加，從一個和一個開始。

以下是斐波那契數的遞歸關系：

F（1）= F（2）= 1
F（n）= F（n-1）+ F（n-2）

遞歸關系是原始函數引用自身的任何關系。 那么我們如何找到F（5）？

F（5）= F（4）+ F（3）
F（5）= [F（3）+ F（2）] + [F（2）+ F（1）] F（5）= [F（2）+ F（1）] +1 +1 +1
F（5）= 1 + 1 + 1 + 1 + 1 F（5）= 5

似乎需要很多工作？ 好吧，對于計算機來說，大多數時候都相當快。 稍后，我將向您介紹動態編程，因此當您要計算較大的斐波那契數時，我們可以加快速度。

那么遞歸函數的所有部分是什么？ 首先，什么是遞歸函數？ 遞歸函數是任何直接（間接或間接）調用自身的函數。 這是Java中的一個簡單示例：

public static void doIt()
{doIt();
}

當然，這最終會導致堆棧溢出錯誤，因此不建議您嘗試使用此代碼。

所有有用的遞歸函數都具有以下一般屬性：減少問題，直到計算機可以輕松解決為止。 為此，遞歸函數必須具有：

1. 定義了基本案例（解決方案顯而易見且無法進一步簡化的案例）
2. 減少步驟（簡化給定問題的地方）
3. 遞歸調用自身（基本上解決了更簡單的情況）

在上面的Fibonacci遞歸函數中，您可以看到它一直在遞歸，直到只加1。 這是因為在斐波那契數列中1是基本情況，因此我們僅需將1加幾次才能得到F（n）。

從理論上講，所有遞歸函數都可以迭代編寫，并且所有迭代函數都可以遞歸編寫。 但是，在實踐中，您會發現根據情況的不同，其中一種或兩種理念會更好地發揮作用。

讓我們遞歸地查看階乘函數，并將其與它的迭代親戚進行比較。

階乘（N）= 1 * 2 * 3 * ... * N
基本上，將1到N的所有整數相乘即可得到N的階乘。

迭代實現，您的代碼將如下所示：

public static int iterativeFactorial(int n)
{int answer = 1;for (int i = 1; i < n; i++){answer *= i;}return answer;
}

我們還可以編寫此函數的遞歸等效項：F（1）= 1 F（N）= F（N-1）* N您能看到這如何產生與迭代階乘相同的結果嗎？ 這是遞歸計算階乘的代碼：

public static int recursiveFactorial(int n)
{if (n == 1){return 1;}else{return n * recursiveFactorial(n-1);}
}

那么，就性能而言，遞歸如何與此處的迭代解決方案相提并論？ 可悲的是，答案很差。 此處的遞歸函數需要大量內存來存儲方法堆棧并跟蹤每個遞歸調用中的所有變量，而迭代解決方案僅需跟蹤當前狀態。 那么，為什么還要煩惱遞歸呢？ 因為很多時候正確使用遞歸，其性能可能會超過迭代解決方案的性能，并且遞歸函數也可能更易于編寫（有時）。

動態編程

動態編程是遞歸的一種形式，但是它是迭代實現的。 還記得我們上面的斐波那契計算機嗎？ F（5）= F（2）+ F（1）+ F（2）+ F（2）+ F（1）F（5）= 3 * F（2）+ 2 * F（1）我們有這里有一些“過度計算”。 只需計算一次F（2）和一次F（1）。 在這種情況下，計算這幾個項并不需要太多的計算工作，但是在某些情況下，幾乎不可能數百次重新計算解決方案。 因此，我們無需重新計算，而是將答案存儲了下來。

public static int dynamicFibonacci(int n)
{int[] prevSolutions = new int[n];if (n == 1 || n == 2){return 1;}prevSolutions[0] = 1;prevSolutions[1] = 1;for (int i = 2; i < prevSolutions.length; i++){prevSolutions[i] = prevSolutions[i-1] + prevSolutions[i-2];}return prevSolutions[n-1];
}

因此，再次取F（5）。 如果我們以遞歸的方式進行操作，那么將有8次調用recursiveFibonacci。 但是，這里我們只計算一次F（1），F（2），F（3），F（4）和F（5）。 減少3個電話獲得的收益似乎并不多，但是如果我們嘗試計算F（50）怎么辦？ dynamicFibonacci僅會計算50個數字，但遞歸Fibonacci可能會超過1000個（當然，我還沒有計算，所以我不知道它是否超過1000個）。

關于動態編程的最后一點是，它僅在有大量重疊的情況下才有用。 還記得recursiveFactorial函數嗎？ 如果我們調用recursiveFactorial（50）和dynamicFactorial（50），則它們將花費大致相同的時間，因為我們要進行相同數量的計算。 這是因為從來沒有重疊。 這也是為什么排序算法不是通過動態編程實現的較差選擇的原因：如果您分析大多數排序算法，則它們幾乎沒有重疊的解決方案，因此對于動態編程來說是一個較差的選擇。

這是有關遞歸和動態編程的一些問題：

1. 實現recursiveFactorial方法（您以為我忘了把它放在那里）
2. 對于給定的遞歸關系，編寫一個遞歸方法，將找到F（N）
3. 這種遞歸關系在迭代方面意味著什么？ 為此問題寫一個迭代的解決方案。
4. 這種遞歸關系是否適合動態編程？ 為什么/為什么不呢？
5. 有比迭代或遞歸解決方案更好的方法來解決此問題嗎？ 這是什么（如果有）？ 提示：想想卡爾高斯

對于問題2-5，請使用以下遞歸關系：
F（1）= 1
F（N）= F（N-1）+ N

答案來了……

參考： Java編程論壇上 JCG合作伙伴的 遞歸

相關文章 ：

• Java Micro-Benchmarking：如何編寫正確的基準
• 首先記錄異常的根本原因
• 編程反模式
• 您不想錯過的十大Java書籍
• Java日志混亂
• 做短，但做對！