C++ Gossip - 函式《進階議題》遞迴 - C語言C++程式 - 程式設計 - 頂客論壇 ,免費遊戲,免費交友,免費空間,免費部落格,免費相簿,免費開店 - 頂客社區 dk101.com 最用心的華人社群網站
發新話題

C++ Gossip - 函式《進階議題》遞迴

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

TOP

發新話題

本站所有圖文均屬網友發表,僅代表作者的觀點與本站無關,如有侵權請通知版主會盡快刪除。