C++最大公約數（遞迴）詳解

使用遞迴可以計算兩個數位的最大公約數。根據歐幾里得演算法，兩個正整數 x 和 y 的最大公約數的計算方法如下:

gcd(x，y) = y; 如果y除以x而沒有餘數
gcd(x，y) = gcd(y, x/y的餘數)；否則

這個定義指出，如果 x/y 沒有餘數，則 x 和 y 的最大公約數是 y；否則，答案就是 y 和 x/y 的餘數的最大公約數。

下面的程式顯示了遞回的 C++ 實現：

// This program demonstrates a recursive function to
// calculate the greatest common divisor (gcd) of two numbers.
#include <iostream>
using namespace std;

// Function prototype
int gcd(int, int);
int main()
{
    int num1, num2;
    cout << "Enter two integers: ";
    cin >> num1 >> num2;
    cout << "The greatest common divisor of " << num1;
    cout << " and " << num2 << " is ";
    cout << gcd(num1, num2) << endl;
    return 0;
}
int gcd(int x, int y)
{
    if (x % y == 0) //base case
        return y;
    else
        return gcd{y, x % y);
}

程式輸出結果：

Enter two integers: 49 28
The greatest common divisor of 49 and 28 is 7