遞迴(Recursion)


遞迴(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);
}

執行結果:
輸入兩數:10 45
GCD: 5


上面的程式是使用輾轉相除法來求最大公因數;遞迴具有重複執行的特性,而可以使用遞迴求解的程式,實際上也可以使用迴圈來求解,例如下面的程式就是最大公 因數使用迴圈求解的方式:

#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;
}

那麼使用遞迴好還是使用迴圈求解好?這並沒有一定的答案。不過通常由於遞迴本身有重複執行與記憶體堆疊的特性,所以若在求解時需要使用到堆疊特性的資料結 構時,使用遞迴在設計時的邏輯會比較容易理解,程式碼設計出來也會比較簡潔,然而遞迴會有函式呼叫的負擔,因而有時會比使用迴圈求解時來得沒有效率,不過 迴圈求解時若使用到堆疊時,通常在程式碼上會比較複雜。