递归实现GCD程序无返回结果的原因排查请求

你的递归版GCD函数存在无限递归问题，导致程序栈溢出后异常终止，因此没有任何输出。

问题根源 #

原函数中缺少递归终止条件：不管a和b是否相等，代码都会直接进入if/else分支发起递归调用，永远执行不到最后的return a;。递归没有终止点，会不断调用自身直到栈空间耗尽，程序直接崩溃，自然无法输出结果。

修正后的代码（辗转相减递归版） #

#include <iostream>

using namespace std;

int gcd(int a,int b){
    // 终止条件：a与b相等时，该值就是最大公约数
    if(a == b){
        return a;
    }    
    if(a > b){
        return gcd(a - b, b);
    } else {
        return gcd(a, b - a);
    }
}

int main()
{
    cout << gcd(9,8);
    return 0;
}

更高效的优化版本（辗转相除法递归版） #

如果追求更高效率，推荐使用辗转相除法的递归实现，避免大量减法操作：

#include <iostream>

using namespace std;

int gcd(int a, int b){
    // 终止条件：当b为0时，a就是最大公约数
    if(b == 0){
        return a;
    }
    return gcd(b, a % b);
}

int main()
{
    cout << gcd(9,8);
    return 0;
}

内容的提问来源于stack exchange，提问作者hussain muhammad