程式語言教學誌 FB, YouTube: PYDOING: C 語言初學教材

利用遞迴的計算方式解決問題比較直覺，但是當計算的值越大時，所需的時間也就越多。其實遞迴的方法都能夠用迭代的計算方式來代替，所謂的迭代類似公式解，利用一個迴圈進行計算工作，因此不會消耗太多的記憶體，得到結果的時間也會快很多。

迭代的方案雖然有其優點，問題是迭代並非顯而易見的，例如計算階層數，我們該怎麼把計算都濃縮在一個迴圈之中呢？

因為每一個階層數都是從 1 開始相乘，因此我們可以設定迴圈變數 i 從 1 開始遞增，然後另外用一個儲存算結果的變數 result ，把 result 乘上每一個遞增的 i 。

基於這個想法，程式如下

#include <stdio.h>

int factorial(int n);

int main(void)
{
    int i;
    
    for (i = 0; i < 10; i++) {
        printf("%d! = %d\n", i, factorial(i));
    }
    
    return 0;
}

int factorial(int n)
{
    int i, result;
    
    result = 1;
    for (i = 1; i <= n; i++) {
        result *= i;
    }
    
    return result; 
}

/* 《程式語言教學誌》的範例程式
    http://pydoing.blogspot.com/
    檔名：iterative1.c
    功能：計算階層
    作者：張凱慶
    時間：西元2010年7月 */

編譯後行，結果如下

結果符合預期，因此計算階層數可以用這個方法代替。

那計算費伯納西數可以用怎麼樣的迭代方法計算呢？由於每個費伯納西數都是前兩個數字相加，因此迴圈變數在實際計算過程就只代表要做幾次計算，這也是說，我們需要額外的兩個變數來儲存要進行相加的前兩個數字。

以下程式為計算費伯納西數的迭代版本，變數 a 及變數 b 分別儲存費伯納西數列的起始值 0 及 1 ，然後 result 儲存結果，初值設為 1 ，這樣的計算結果會跟遞迴版本相同

#include <stdio.h>

int fabonacii(int n);

int main(void)
{
    int i;
    
    for (i = 0; i < 16; i++) {
        printf("F%d\t= %d\n", i, fabonacii(i));
    }
    
    return 0;
}

int fabonacii(int n)
{
    int i, result, a, b;
    
    a = 0;
    b = 1;
    result = 1;
    for (i = 0; i < n; i++) {
        result = a + b;
        a = b;
        b = result;
    }
    
    return result;
}

/* 《程式語言教學誌》的範例程式
    http://pydoing.blogspot.com/
    檔名：iterative2.c
    功能：計算費伯納西數列
    作者：張凱慶
    時間：西元2010年7月 */

編譯後執行，結果如下