歡迎！您似乎正在使用廣告攔截器。請考慮通過禁用您的廣告攔截器來支持我。

J.J.'s Blogs

Like Share Discussion Bookmark Smile

J.J. Huang   2019-11-21   C C 語言技術 <201910>   瀏覽次數：次   DMCA.com Protection Status {{moment(1574298000000).fromNow()}}

C語言 - 第二十八章 | 函式進階議題 - 遞迴(Recursion)

遞迴(Recursion)

遞迴(Recursion)是在函式中呼叫自身同名函式，而呼叫者本身會先被置入記憶體堆壘中，等到被呼叫者執行完畢之後，再從堆壘中取出之前被置入的函式繼續執行。堆疊(Stack)是一種「先進後出」的資料結構，就好比你將書本置入箱中，最先放入的書會最後才取出。

C支援函式的遞迴呼叫，遞迴的概念看似抽象，但實際應用很多，舉個例子來說，求最大公因數就可以使用遞迴來求。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <stdio.h>

int gcd(int, int); 

int main() {

    int m = 0;
    int n = 0; 

    printf("輸入兩數(num1 num2)：");
    scanf("%d %d", &m, &n);

    printf("GCD: %d\n", gcd(m, n));

    return 0;
}

int gcd(int m, int n) { 
    if(n == 0) {
        return m; 
    }
    else {
        return gcd(n, m % n); 
    }
}
1
2
3
// 執行結果
輸入兩數：10 45
GCD: 5

上面的程式是使用輾轉相除法來求最大公因數；遞迴具有重複執行的特性，而可以使用遞迴求解的程式，實際上也可以使用迴圈來求解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <stdio.h>

int gcd(int, int); 

int main() {

    int m = 0;
    int n = 0; 

    printf("輸入兩數(num1 num2)：");
    scanf("%d %d", &m, &n);

    printf("GCD: %d\n", gcd(m, n));

    return 0;
}

int gcd(int m, int n) { 
    while(n != 0) { 
        int r = m % n;
        m = n; 
        n = r; 
    } 

    return m; 
}

那麼使用遞迴好還是使用迴圈求解好？對於簡單的重複性，使用迴圈較為直覺，像是循序迭代，然而，若想清楚表現目前子任務的獨立性，例如以輾轉相除法求最大公因數時，想展現「每次求餘數後，下個子任務就是求除數與餘數的最大公因數」的這個獨立性，使用遞迴反而清楚的多。

初學者通常會覺得遞迴很複雜，因而傾向於使用迴圈來解決一切事情，然而，迴圈容易因習慣不良，而充斥了許多邏輯泥塊(Logic lump)，反而令除錯不易，有興趣可以進一步參考(遞迴的美麗與哀愁)[https://openhome.cc/Gossip/Programmer/Recursive.html]。


註：以上參考了
遞迴（Recursion）

本文由J.J. Huang 創作，採用CC BY 3.0 TW協議 進行許可。可自由轉載、引用，但需署名作者且註明文章出處。