尾遞歸的本質

先直接上兩個例子：求n的階乘，仔細觀察對比一下

例子1：

int fact(int n)

{

    if(n<0)

      return 0;

    else if(n ==0 || n==1)

      return 1;

    return  n * fact(n-1);

}
           

例子2：

int fact(int n)

{

    return  fact_iter(n , 1 ,1);

}

int fact_iter(int n ,int count ,int result)

{

    if(n<0)

      return 0;

    if(count > n)

      return  result;

    return  fact_iter(n , count+1 ,result * count);

}
           

        上邊的兩個例子一個是正常的遞歸實作，另外一個是尾遞歸實作，初次看這兩個例子會感覺遞歸很容易了解而尾遞歸看着怪怪的，的确，尾遞歸有點“違反”正常。

首先我們看看函數與遞歸的本質：

        函數調用的本質是: 我們在做一件事過程中，我們發現必須要先完成另外一件事，于是中斷目前的工作，并把目前的工作資訊儲存到棧(stack); 當别的事情完成了再繼續目前的工作(從stack 中取出工作資訊并繼續)。

        而遞歸的本質也就是函數調用，隻不過目前的工作與另外一件事是相同的執行步驟，不同的隻是工作内容。

        下面介紹一下，尾遞歸的來源。我們知道遞歸的實作本質就是用棧儲存每一層的局部資訊、傳回位址等等，遞歸一層一層遞進調用自己的時候，對應的棧也要一層一層的配置設定空間儲存資訊，遞進到最後一層時再逐層傳回，對應的棧空間也一層一層回收。從遞歸的實作可以看出，它對棧的空間要求随着遞歸遞進的層數增加而增加，如果層數很大，因為對于一個程式來說，棧的大小是有最大值的，如果超過這個值，那麼就會導緻棧溢出而使程式崩潰，解決遞歸調用棧溢出的一個方法就是尾遞歸。

        下邊直接先擺出尾遞歸的本質：将目前層運算的結果以函數參數的形式傳遞給下一層調用。

        為什麼這麼說，因為這展現了尾遞歸的來源，這樣做就是為了解決棧溢出的。那為什麼這樣就可以解決棧溢出呢？首先我們來回憶一下這樣一個知識，通常我們利用函數實作某一個功能的時候，我們有兩種方式獲得結果，第一種方法是直接在函數中利用return語句傳回結果，這是最直接的方法直接調用函數就可以獲得結果，另外一種方法就是給函數設定一個參數專門用來儲存函數的傳回值，這種方法選擇了另外一個變量作為函數參數傳入函數，函數執行完畢後該變量就儲存了函數的傳回結果。

        好了，有了上邊的一些回憶，我們仔細看一下第二個例子中的fact_iter(int n ,int count ,int result)函數，因為我們将結果result以一個函數的參數形式展現，上一層的調用結果直接反映到下一層的函數調用實參中，這樣可以實作上下層之間沒什麼聯系了，不用逐層傳回了，nice，要的就是這個效果，有了這樣一個好處後，我們可以不用每一層都新配置設定一些棧空間，直接覆寫原來的棧空間就行了，因為原來的棧空間沒什麼用了，就這樣，大功告成，棧空間不會一層一層不斷配置設定以及回收，也就不會出現棧溢出了。

        OK，上邊都是講尾遞歸怎麼怎麼好，那麼問題來了，尾遞歸它也是遞歸，具體到實際當中，這種特殊的遞歸其棧空間覆寫是怎麼實作的呢？事實上，一般是由編譯器來對代碼進行優化實作的，尾遞歸有一個顯著的特點就是它的遞歸調用語句總是放在函數的最末尾，這其實是給編譯器一個信号，表明自己身份，當編譯器檢測到一個函數調用是尾遞歸的時候，它就覆寫目前的活躍記錄而不是在棧中去建立一個新的通過覆寫目前的棧幀而不是在其之上重新添加一個，這樣所使用的棧空間就大大縮減了，這使得實際的運作效率會變得更高。

        最後，我們似乎不能高興的太早，各種語言編譯器或者解釋器都能夠自動優化尾遞歸麼？答案不那麼美好，據網上查閱：java、C#和python都不支援編譯環境自動優化尾遞歸，在這種情況下我們可以手動将遞歸改造成循環，但是對于C語言來說，編譯器提供了自動優化，不用白不用，畢竟遞歸代碼好了解。