c - 递归 GCD 逻辑错误

Question

据我所知，这其中的逻辑是有道理的。然而输出是不正确的，我似乎可以理解它。

#include <stdio.h>

int gcd(int, int);

int main()
{
    int n, m;

    printf("enter two numbers");
    scanf("%d%d", &n, &m);

    printf("The gcd of %d and %d is: %d \n", n, m, gcd(n,m));

    return 0;
}

int gcd(int x, int y)
{
    while(x!=y){
           if(x>y)
                    return (x-y,y);

            else
                    return(x,y-x);
    }
    return x;
}

Answer 1

这不是 的递归实现gcd，该函数没有调用自身，而且它使用while循环。真正的递归方法如下所示：

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

或者更短一点：

int gcd(int x, int y) {
    return y == 0 ? x : gcd(y, x % y);
}

上面的实现是基于欧几里得算法的，更多细节参考this。

Answer 2

return (x-y,y);

将简单地返回y。该代码可以编译，但可能不是您所期望的。

非递归 Euclid GCD 算法如下所示：

int gcd (int x, int y)
{
    while (y != 0)
    {
        int r = x % y;
        x = y;
        y = r;
    }
    return x;
}

与递归版本相比：

int gcd (int x, int y)
{
    return y == 0 ? x : gcd (y, x%y);
}

与这些琐碎的示例一样，递归方法使用的源代码较少，但效率低下。

x和加上返回地址的副本y在堆栈上传递，而线性版本仅使用中间变量r来处理x / y.

即使某些编译器可能足够聪明，可以检测到不必要的递归并将其优化掉，我认为了解递归编码的内在成本还是很有用的。