C 速查手冊

遞迴函數

C 語言的函數 (function) 中除了可以呼叫其他函數,也可以呼叫自己,呼叫自己的函數被稱為遞迴函數。

以下將 C 速查手冊 - 函數介紹的指數函數改成用遞迴 (recursion) 來寫

#include <stdio.h>

int exponent2(int , int);

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

int exponent2(int a, int x)
{
    if (x == 0) {
        return 1;
    }
    else {
        return a * exponent2(a, x - 1);
    }
}

/* 《程式語言教學誌》的範例程式
    http://kaiching.org/
    檔名:exponent3.c
    功能:測試遞迴指數函數,從 2 的 0 次方列印到 10 次方
    作者:張凱慶 */

編譯後執行,結果如下

$ gcc exponent3.c
$ a.out
 0    1
 1    2
 2    4
 3    8
 4   16
 5   32
 6   64
 7  128
 8  256
 9  512
10 1024
$

遞迴的計算分成初始條件與遞迴條件,指數函數中的初始條件便是當指數為 0 的時候,所得的指數函數值為 1exponent2()if 部分便是初始條件的部份。

if (x == 0) {
    return 1;
}

所謂的遞迴條件就是如何把計算拆成相同的重複步驟,問題用相同的條件還原成更早的問題,直到符合初始條件為止。這樣一來,每一次都可以利用呼叫遞迴函數本身進行計算, exponent2()else 部分便是遞迴條件,每一次呼叫都是底數 a 乘上指數 x1 的函數 exponent2()

else {
    return a * exponent2(a, x - 1);
}

由此,遞迴程式會進行堆疊的動作,把每一次的呼叫都放到堆疊之中,直到運算到初始條件之後,再把堆疊之中儲存的值的逐一取出依次計算,例如以下為 exponent2(2, 6) 的第一次執行







exponent2(2, 6)

這是計算 26 次方,第二次執行變成 2 * exponent2(2, 5) ,注意執行時第一次執行的 exponent2(2, 6) 仍保留在記憶體中






2 * exponent2(2, 5)
exponent2(2, 6)

同樣第三次執行





2 * exponent2(2, 4)
2 * exponent2(2, 5)
exponent2(2, 6)

第四次




2 * exponent2(2, 3)
2 * exponent2(2, 4)
2 * exponent2(2, 5)
exponent2(2, 6)

第五次



2 * exponent2(2, 2)
2 * exponent2(2, 3)
2 * exponent2(2, 4)
2 * exponent2(2, 5)
exponent2(2, 6)

第六次


2 * exponent2(2, 1)
2 * exponent2(2, 2)
2 * exponent2(2, 3)
2 * exponent2(2, 4)
2 * exponent2(2, 5)
exponent2(2, 6)

第七次

2 * exponent2(2, 0)
2 * exponent2(2, 1)
2 * exponent2(2, 2)
2 * exponent2(2, 3)
2 * exponent2(2, 4)
2 * exponent2(2, 5)
exponent2(2, 6)

第八次, 初始條件 exponent2(2, 1) 回傳 1

2 * 1
2 * exponent2(2, 1)
2 * exponent2(2, 2)
2 * exponent2(2, 3)
2 * exponent2(2, 4)
2 * exponent2(2, 5)
exponent2(2, 6)

第九次,接下來每個每個 exponent2() 都回傳 2


2 * 2
2 * exponent2(2, 2)
2 * exponent2(2, 3)
2 * exponent2(2, 4)
2 * exponent2(2, 5)
exponent2(2, 6)

第十次



2 * 4
2 * exponent2(2, 3)
2 * exponent2(2, 4)
2 * exponent2(2, 5)
exponent2(2, 6)

第十一次




2 * 8
2 * exponent2(2, 4)
2 * exponent2(2, 5)
exponent2(2, 6)

第十二次





2 * 16
2 * exponent2(2, 5)
exponent2(2, 6)

第十三次






2 * 32
exponent2(2, 6)

最後第十四次得到結果 64







64

回 C 速查手冊首頁