本文共 1257 字，大约阅读时间需要 4 分钟。

递归是计算最大公约数的有效方法，基于欧几里得算法的原理。它通过不断交换参数，直到余数为零，从而找到最大公约数。以下是详细的解释和优化后的代码。

递归求最大公约数的步骤解析

当调用函数 dg(a, b) 时，参数分别为两个正整数a和b：

这里是关键：每次递归调用都会减少较大的数，这是欧几里得算法的本质。通过不断地用较大的数除以较小的数，余数越来越小，直到余数为零。

优化后的C++代码

#include 
   
    
#include 
    
      
using namespace std;
int dg(int a, int b) {
    if (b == 0) {
        return a;
    }
    return dg(b, a % b);
}
int main() {
    int a, b;
    cout << "请输入两个整数：";
    cin >> a >> b;
    sort(a, b); // 确保a >= b以简化计算
    cout << dg(a, b) << endl;
    return 0;
}
    
   

分步解释代码和逻辑

• 递归函数 dg(a, b)：

  • base case：当 b == 0 时，直接返回a，因为a已经是和b的最大公约数了。
  • 递归 case：返回 dg(b, a % b)，即调用自身，更新参数为新的b和a % b。

• 主函数 main()：

  • 读取两个整数a和b。
  • 调用 sort(a, b) 确保a是较大的数，b是较小的数，以简化递归过程。
  • 调用递归函数 dg(a, b) 并输出结果。

示例运行

假设输入两个数为24和36：

最终输出最大公约数12。

KLARωσηgle-Trouble Sheldon的讲解

递归的过程简化了多次模运算，随着每次递归，数值被有效减少，直到余数为零，最后返回结果。这个过程在技术和教育领域都有广泛应用。

通过这种优化，代码变得更加有效率，而递归过程亦更易于理解和调试。这种方法不仅展示了递归的强大，但也证明了欧几里得算法的逻辑严密性。