From Gossip@caterpillar

C++ Gossip: 遞迴（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; 
}

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