如果我从函数中删除 "else"，为什么输出不同？

Question

我正在尝试编写一个 GCD 函数来使用 euclids 算法计算两个整数的 gcd。在函数中，如果我擦除 "else"，它会输出 3，这是不正确的。但是如果我使用 "else" 它输出 1 这是正确的输出。我假设如果我不使用 "else" 函数仍然是正确的。为什么我得到两个不同的输出。

这是我的代码，

 #include <iostream>

using namespace std;


int euclidGcd(int x , int y){

    if(x%y!=0)
        euclidGcd(y , x%y );
    else
        return y;

}

int main(){

    cout<<euclidGcd(2,3)<<"\n";


    return 0;
}

Answer 1

您的函数有未定义的行为。当 % 运算符 return 为非零值时，您的函数根本不会 returning 任何内容，因此输出是垃圾。您需要 return 递归调用的结果：

int euclidGcd(int x, int y)
{
    if ((x % y) != 0)
        return euclidGcd(y, x % y); // <-- here
    else
        return y;
}

但是，根据算法的 Wikipedia's description，函数应该如下所示：

int euclidGcd(int x, int y)
{
    if (y != 0)
       return euclidGcd(y, x % y);
    else
       return x; 
}

或者，使用其他完全不使用递归的描述实现：

基于部门：

int euclidGcd(int x, int y)
{
    while (y != 0)
    {
        int t = y; 
        y = x % y; 
        x = t; 
    }
    return x;
}

基于减法：

int euclidGcd(int x, int y)
{
    while (x != y)
    { 
        if (x > y)
            x -= y; 
        else
            y -= x; 
    }
    return x;
}

如果我从函数中删除 "else"，为什么输出不同？

Why output differs if i erase "else" from the function?

c++

greatest-common-divisor