Like Share Discussion Bookmark Smile

J.J. Huang   2019-11-21   C   瀏覽次數:

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)