深究遞歸和疊代的差別、聯系、優缺點及執行個體對比

1.概念區分

遞歸的基本概念:程式調用自身的程式設計技巧稱為遞歸,是函數自己調用自己.

一個函數在其定義中直接或間接調用自身的一種方法,它通常把一個大型的複雜的問題轉化為一個與原問題相似的規模較小的問題來解決,可以極大的減少代碼量.遞歸的能力在于用有限的語句來定義對象的無限集合.

使用遞歸要注意的有兩點:

1)遞歸就是在過程或函數裡面調用自身;

2)在使用遞歸時,必須有一個明确的遞歸結束條件,稱為遞歸出口.

遞歸分為兩個階段:

1)遞推:把複雜的問題的求解推到比原問題簡單一些的問題的求解;

2)回歸:當獲得最簡單的情況後,逐漸傳回,依次得到複雜的解.

利用遞歸可以解決很多問題:如背包問題,漢諾塔問題,...等.

斐波那契數列為:0,1,1,2,3,5...

由于遞歸引起一系列的函數調用,并且有可能會有一系列的重複計算,遞歸算法的執行效率相對較低.

疊代:利用變量的原值推算出變量的一個新值.如果遞歸是自己調用自己的話,疊代就是A不停的調用B.

2.辯證看遞歸和疊代

所謂遞歸，簡而言之就是應用程式自身調用自身，以實作層次資料結構的查詢和通路。遞歸的使用可以使代碼更簡潔清晰，可讀性更好（對于初學者到不見得），但由于遞歸需要系統堆棧，是以空間消耗要比非遞歸代碼要大很多，而且，如果遞歸深度太大，可能系統資源會不夠用。

往往有這樣的觀點：能不用遞歸就不用遞歸，遞歸都可以用疊代來代替。

誠然，在理論上，遞歸和疊代在時間複雜度方面是等價的（在不考慮函數調用開銷和函數調用産生的堆棧開銷），但實際上遞歸确實效率比疊代低，既然這樣，遞歸沒有任何優勢，那麼是不是就，沒有使用遞歸的必要了，那遞歸的存在有何意義呢？

萬物的存在是需要時間的檢驗的，遞歸沒有被曆史所埋沒，即有存在的理由。從理論上說，所有的遞歸函數都可以轉換為疊代函數，反之亦然，然而代價通常都是比較高的。但從算法結構來說，遞歸聲明的結構并不總能夠轉換為疊代結構，原因在于結構的引申本身屬于遞歸的概念，用疊代的方法在設計初期根本無法實作，這就像動多态的東西并不總是可以用靜多态的方法實作一樣。這也是為什麼在結構設計時，通常采用遞歸的方式而不是采用疊代的方式的原因，一個極典型的例子類似于連結清單，使用遞歸定義及其簡單，但對于記憶體定義(數組方式)其定義及調用處理說明就變得很晦澀，尤其是在遇到環鍊、圖、網格等問題時，使用疊代方式從描述到實作上都變得不現實。因而可以從實際上說，所有的疊代可以轉換為遞歸，但遞歸不一定可以轉換為疊代。

采用遞歸算法需要的前提條件是，當且僅當一個存在預期的收斂時，才可采用遞歸算法，否則，就不能使用遞歸算法。

遞歸其實是友善了程式員難為了機器，遞歸可以通過數學公式很友善的轉換為程式。其優點就是易了解，容易程式設計。但遞歸是用棧機制實作的，每深入一層，都要占去一塊棧資料區域，對嵌套層數深的一些算法，遞歸會力不從心，空間上會以記憶體崩潰而告終，而且遞歸也帶來了大量的函數調用，這也有許多額外的時間開銷。是以在深度大時，它的時空性就不好了。

而疊代雖然效率高，運作時間隻因循環次數增加而增加，沒什麼額外開銷，空間上也沒有什麼增加，但缺點就是不容易了解，編寫複雜問題時困難。

因而，“能不用遞歸就不用遞歸，遞歸都可以用疊代來代替”這樣的了解，還是辯證的來看待，不可一棍子打死。*/

1,2部分摘自網絡，略有改動，向原作者緻敬！

3.個人總結

dog	定義	優點	缺點
遞歸	程式調用自身的程式設計技巧稱為遞歸	1）大問題化為小問題,可以極大的減少代碼量；2）用有限的語句來定義對象的無限集合.；3）代碼更簡潔清晰，可讀性更好	1）遞歸調用函數,浪費空間；2）遞歸太深容易造成堆棧的溢出；
疊代	利用變量的原值推算出變量的一個新值，疊代就是A不停的調用B.	1）疊代效率高，運作時間隻因循環次數增加而增加；2）沒什麼額外開銷，空間上也沒有什麼增加，	1） 不容易了解；2） 代碼不如遞歸簡潔；3） 編寫複雜問題時困難。
二者關系	1） 遞歸中一定有疊代,但是疊代中不一定有遞歸,大部分可以互相轉換。2） 能用疊代的不用遞歸,遞歸調用函數,浪費空間,并且遞歸太深容易造成堆棧的溢出./相對/

舉例如下：

#include <iostream>
using namespace std;
 
//疊代實作斐波那契數列
long fab_iteration(int index)
{
    if(index == 1 || index == 2)
    {
        return 1;
    }
    else
    {
        long f1 = 1L;
        long f2 = 1L;
        long f3 = 0;
        for(int i = 0; i < index-2; i++)
        {   
            f3 = f1 + f2; //利用變量的原值推算出變量的一個新值
            f1 = f2;
            f2 = f3;
        }
         return f3;
    }
}
 
//遞歸實作斐波那契數列
 long fab_recursion(int index)
 {    
    if(index == 1 || index == 2)
    {
        return 1;
    }
    else
    {
        return fab_recursion(index-1)+fab_recursion(index-2);    //遞歸求值
    }
}
 
int main(int argc, char* argv[])
{
    cout << fab_recursion(10) << endl;
    cout << fab_iteration(10) << endl;
    return 0;
}           

作者：銘毅天下

來源：CSDN

原文：

https://blog.csdn.net/laoyang360/article/details/7855860

版權聲明：本文為部落客原創文章，轉載請附上博文連結！