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);
}
執行結果：

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