谷歌瀏覽器告訴你什麼是遞迴

什麼是遞迴

遞迴是在方法的內部呼叫自己的方法，所有具有自己呼叫的方法都是遞迴的

如果你在谷歌上搜索遞迴，那麼你將會看到如下的資訊。

當你點選紅色框中的

遞迴

，然後看到的還是這個頁面，直到你明白

遞迴

。會不會是谷歌調皮了？這個問題有待研究。

遞迴

是一種神奇的演算法，是程式設計書籍中最笨拙的部分。 這些書通常會向您展示遞迴階乘實現，然後會警告您，儘管它可以工作，但它非常慢，並且可能溢位和崩潰。 雖然人們對此表示懷疑，但這並不影響遞迴是該演算法中最強大的想法。

第一次接觸遞迴

遞迴演算法在數學階乘的計算中敏銳而生動地體現，階乘是置換組合的結果，任何大於1的自然數n都可以表示為：n！ = 1 x 2 x 3 x 。。。x n。另外，0！=1；

現在來看這個問題，確實是太簡單了，因此我這裡就給大家找了一個求6的階乘圖，讓大家理解一下。

有興趣的朋友呢，可以嘗試手動編寫一下這個程式，絕大多數的程式語言都可以實現。我這裡給大家一個C++版本的。也是教科書上的原始碼程式給大家參考一下。

#include using namespace std；int Factorial（int n）{ int sum=0； //定義一個累乘的sum量 if（n==0）return 1； //遞迴結束出口，當遞迴到n=0時，返回1值 else{ sum=n*Factorial（n-1）； //遞迴呼叫 } return sum；}int main（）{ int n； int sum； cin>>n； sum=Factorial（n）； cout<

另外，在教科書中還有一個練習題就是，

斐波那契數列。

這個我在這裡就不給大家說了，大家有興趣的話呢，可以去了解一下。是一個非常有意思的數列。

那些演算法題中可以使用遞迴？

資料的定義是按遞迴定義的。如Fibonacci函式。

問題解法按遞迴演算法實現。如Hanoi問題。

資料的結構形式是按遞迴定義的。如二叉樹、廣義表等。

在常見的演算法面試題中，我們會經常使用遞迴來解決一些問題。一般來說，能用遞迴解決的問題，那麼使用動態規劃也可以解決。

動態規劃的三要素

一、最優子結構

二、邊界

三、狀態轉移方程

這三點在我的演算法面試詳解的影片中都有詳細描述。

總結

遞迴和動態規劃的區別是，遞迴是自頂向底解決問題，動態規劃是自底向頂解決問題。

遞迴在某些演算法題中需要進行剪枝。如果不進行剪枝，那麼遞迴就會進行很多重複的計算，因此使用遞迴需要進行剪枝最佳化，通常來說動態規劃比遞迴更優。

但是動態規劃的難點在於最優子結構的選擇以及尋找狀態轉移方程。這些都是需要平常的積累。

所以，只有當你做了大量的演算法練習題之後，你就能夠清楚的瞭解遞迴和動態規劃思想。