斐波那契與尾遞歸

尾遞歸wiki解釋如下：

• 尾部遞歸是一種程式設計技巧。遞歸函數是指一些會在函數内調用自己的函數，如果在遞歸函數中，遞歸調用傳回的結果總被直接傳回，則稱為尾部遞歸。尾部遞歸的函數有助将算法轉化成函數程式設計語言，而且從編譯器角度來說，亦容易優化成為普通循環。這是因為從電腦的基本面來說，所有的循環都是利用重複移跳到代碼的開頭來實作的。如果有尾部歸遞，就隻需要疊套一個堆棧，因為電腦隻需要将函數的參數改變再重新調用一次。利用尾部遞歸最主要的目的是要優化，例如在Scheme語言中，明确規定必須針對尾部遞歸作優化。可見尾部遞歸的作用，是非常依賴于具體實作的。
• 我們還是從簡單的斐波那契開始了解尾遞歸吧。
• 用普通的遞歸計算Fibonacci數列：

#include "stdio.h"
#include "math.h"

int factorial(int n);

int main(void)
{
    int i, n, rs;

    printf("請輸入斐波那契數n：");
    scanf("%d",&n);

    rs = factorial(n);
    printf("%d \n", rs);

    return 0;
}

// 遞歸
int factorial(int n)
{
    if(n <= 2)
    {
        return 1;
    }
    else
    {
        return factorial(n-1) + factorial(n-2);
    }
}      

程式員運作結果如下：

請輸入斐波那契數n：20

6765

Process returned 0 (0x0) execution time : 3.502 s

Press any key to continue.

在i5的CPU下也要花費 3.502 秒的時間。

下面我們看看如何用尾遞歸實作斐波那契數。

/#include "stdio.h"
/#include "math.h"

int factorial(int n);

int main(void)
{
    int i, n, rs;

    printf("請輸入斐波那契數n：");
    scanf("%d",&n);

    rs = factorial_tail(n, 1, 1);
    printf("%d ", rs);

    return 0;
}

int factorial_tail(int n,int acc1,int acc2)
{
    if (n < 2)
    {
        return acc1;
    }
    else
    {
        return factorial_tail(n-1,acc2,acc1+acc2);
    }
}      

• 程式員運作結果如下：

請輸入斐波那契數n：20

6765

Process returned 0 (0x0) execution time : 1.460 s

Press any key to continue.

快了一倍有多。當然這是不完全統計，有興趣的話可以自行計算大規模的值，這裡隻是介紹尾遞歸而已。

我們可以列印一下程式的執行過程，函數加入下面的列印語句：

int factorial_tail(int n,int acc1,int acc2)
{
    if (n < 2)
    {
        return acc1;
    }
    else
    {
        printf("factorial_tail(%d, %d, %d) \n",n-1,acc2,acc1+acc2);
        return factorial_tail(n-1,acc2,acc1+acc2);
    }
}      

程式運作結果：

請輸入斐波那契數n：10
factorial_tail(9, 1, 2)
factorial_tail(8, 2, 3)
factorial_tail(7, 3, 5)
factorial_tail(6, 5, 8)
factorial_tail(5, 8, 13)
factorial_tail(4, 13, 21)
factorial_tail(3, 21, 34)
factorial_tail(2, 34, 55)
factorial_tail(1, 55, 89)
55
Process returned 0 (0x0)   execution time : 1.393 s
Press any key to continue.
從上面的調試就可以很清晰地看出尾遞歸的計算過程了。acc1就是第n個數，而acc2就是第n與第n+1個數的和，這就是我們前面講到的“疊代”的精髓，計算結果參與到下一次的計算，進而減少很多重複計算量。