1樓
大 中
小 發表於 2006-12-6 23:47
C++ Gossip - 函式《進階議題》遞迴
遞迴(Recursion)是在函式中呼叫自身同名函式,而呼叫者本身會先被置入記憶體堆壘中,等到被呼叫者執行完畢之後,再從堆壘中取出之前被置入的函式繼續執行。「堆疊」(Stack)是一種「先進後出」的資料結構,就好比您將書本置入箱中,最先放入的書會最後才取出。
C++支援函式的遞迴呼叫,遞迴的概念較抽像,但實際應用很多,舉個例子來說,求最大公因數就可以使用遞迴來求,下面的程式是使用遞迴來求最大公因數的一個實例:
#include <iostream>
using namespace std;
int gcd(int, int);
int main() {
int m = 0;
int n = 0;
cout << "輸入兩數:";
cin >> m >> n;
cout << "GCD: "
<< gcd(m, n) << endl;
return 0;
}
int gcd(int m, int n) {
if(n == 0)
return m;
else
return gcd(n, m % n);
}
執行結果:
上面的程式是使用輾轉相除法來求最大公因數;遞迴具有重複執行的特性,而可以使用遞迴求解的程式,實際上也可以使用迴圈來求解,例如下面的程式就是最大公因數使用迴圈求解的方式:
#include <iostream>
using namespace std;
int gcd(int, int);
int main() {
int m = 0;
int n = 0;
cout << "輸入兩數:";
cin >> m >> n;
cout << "GCD: "
<< gcd(m, n) << endl;
return 0;
}
int gcd(int m, int n) {
int r = 0;
while(n != 0) {
r = m % n;
m = n;
n = r;
}
return m;
}
那麼使用遞迴好還是使用迴圈求解好?這並沒有一定的答案。不過通常由於遞迴本身有重複執行與記憶體堆疊的特性,所以若在求解時需要使用到堆疊特性的資料結構時,使用遞迴在設計時的邏輯會比較容易理解,程式碼設計出來也會比較簡潔,然而遞迴會有函式呼叫的負擔,因而有時會比使用迴圈求解時來得沒有效率,不過迴圈求解時若使用到堆疊時,通常在程式碼上會比較複雜。
|