遞歸和尾遞歸，遞歸尾遞歸

遞歸和尾遞歸，遞歸尾遞歸

        相信如果一個人讓我們求一個斐波那契數列，如果你學過c語言，你一定會說用遞歸法啊，很容易就實現了，但是如果人家讓你求斐波那契的第50個數，而且你對遞歸了解的話，估計幫你不會說遞歸了，如果了解夠深的話，其實你會說遞歸也可以求出來。 1、遞歸        首先我們來說說什麼是遞歸，簡單的來說，就是一個函數需要調用自己來完成某種功能，這種調用就叫做遞歸。        但我們需要清楚一點，遞歸在使用的時候，並不是一直調用自己，我們需要給他一個停下來的時機。就像打仗一樣，要知道進攻的路線，但如果遇到突發狀況也要能計時撤退。所以我們的遞歸也一樣，你需要給他一條前進路徑也要給他一條返回路徑。所以在使用遞歸策略時，必須有一個明確的遞歸結束條件，稱為遞歸出口。       但我們都清楚，遞歸有它致命的缺點，在遞歸調用的過程當中系統為每一層的返回點、局部量等開辟了棧來存儲，因此遞歸次數過多容易造成棧溢出，正是因為如此它和循環比較效率是很低的，這也就是我前面所說的如果讓你計算斐波那契的第五十個數你直接用遞歸法去求其實是不太好的。   下面我們來看看程序：

int Fib(int n)
{
    if( n < 2)
         return n;
     return (Fib(n-1)+Fib(n-2));
}

這樣寫出來的代碼很簡潔，來分析一下它的執行過程，我們給n=5：

可能這樣你還看不出問題，其實上面的圖相當是一個樹狀結構：

   紅色的部分在之後又會被求到，如果我們給的數值不是5是一個更大的數，則被重復計算和調用的數和次數會變得更多。可見，在這樣一個過程中，我們把某些值一直在重復計算，再加上重復的開辟棧空間，使得它的效率變得非常低，你們可以試著求一下第40 50個斐波那契額。

2、尾遞歸

   尾部遞歸是一種編程技巧。如果在遞歸函數中，遞歸調用返回的結果總被直接返回，則稱為尾部遞歸。尾部遞歸的函數有助將算法轉化成函數編程語言，而且從編譯器角度來說，亦容易優化成為普通循環。這是因為從電腦的基本面來說，所有的循環都是利用重復移跳到代碼的開頭來實現的。如果有尾部歸遞，就只需要疊套一個堆棧，因為電腦只需要將函數的參數改變再重新調用一次。

 1 int Fib(int n, int ret1, int ret2)
 2  
 3 {
 4     if (n ==0 )
 5     {
 6         return ret1;
 7     }
 8     else
 9     {
10  return Fib(n - 1, ret2, ret1 +ret2);
11     }
12 }

 

  它的執行步驟如下，每次的ret1就是要求當前的返回值，當執行到n減到0的時候，此時的ret1就是我們要求的第n個數：     這裡我們在傳參的時候需要傳ret=0，ret2=1； Fib(n - 1, ret2, ret1 +ret2)的使用，原本樸素的遞歸產生的棧的層次像二叉樹一樣，以指數級增長，但是現在棧的層次卻像是數組，變成線性增長了，實在是奇妙，總結起來也很簡單，原本棧是先擴展開，然後邊收攏邊計算結果，現在卻變成在調用自身的同時通過參數來計算。 ret1就是第n個數，而ret2就是第n與第n+1個數的和，這其實和我們的“迭代”殊途同歸。 我們可以看看迭代寫出來的斐波那契數列求法。3、迭代法

int Fib(int n)
{
    int num1 = 1;
    int num2 = num1;
    int num3 = num1;
    while (n > 2)
    {
        num3 = num1 + num2;
        num1 = num2;
        num2 = num3;
        n--;
    }
    return num3;
}

　　

可以看出迭代法實現的方法其實和我們的尾遞歸法一個道理，但是迭代法比較通俗易懂，而且和尾遞歸比較起來，因為不用開辟棧空間，所以這三種方法比較起來迭代法是效率最高的。我們在解決實際問題的時候，根據實際要求選擇合適的方法。