递归困境

Question

我正在尝试创建代码来查找三个用户输入数字的GCD。我的目标是用输入的数字调用方法，除以q，Q被初始化为1，仅当余数为0时记录Q，然后确定它是否大于或等于最小数字，如果不是，则增加Q并调用方法，但如果是，我想打印出最大的最后记录的Q，我做错了什么？我一直收到堆栈溢出错误。

public static int recursiveMethod (int x, int y, int z, int q)
{
    int largestVar; 
    int xRes = x % q;
    int yRes = y % q;
    int zRes = z % q;
    if (xRes==0 && yRes ==0 && zRes==0) {
                largestVar = q;
                if (q >= x && q >= y && q >= z)
                {
                    return largestVar;
                }
    }
    else { 
           q++;
    }
   return recursiveMethod(x, y, z, q);

Answer 1

第一种情况是1，此时xRes==0 && yRes ==0 && zRes==0肯定为真，并将largestVar设置为1。然后，由于1可能小于传入的变量，因此它继续，不在else块中递增q，并再次使用q=1调用recursiveMethod！然后这个过程就会重复。

public static int recursiveMethod (int x, int y, int z, int q, int largestVar)
{
    int xRes = x % q;
    int yRes = y % q;
    int zRes = z % q;
    if (xRes==0 && yRes ==0 && zRes==0) {
    //A common denominator found!
                largestVar = q;
    }
    //regardless whether a denominator was found, check for the termination condition
    //Or works here, by the way, since we only need to know when q is greater than one of them.
    if (q >= x || q >= y || q >= z) {
        return largestVar;
    }
    //if we don't terminate, increment q and recurse. 
    q++;
    return recursiveMethod(x, y, z, q, largestVar);
}

已修改以正确处理largestVar。没有注意到这一点。由于是局部作用域，largestVar的值不会通过递归调用来维护，因此还必须将其传递给recursiveMethod调用(要么传递给它，要么声明为类作用域变量，等等)。它的合适起始值应该是0。

Answer 2

我注意到的一个错误是，你的if条件是错误的：

if (q >= x && q >= y && q >= z)

这3个数字的GCD小于或等于每个数字，因此将其更改为：

if (x >= q && y >= q && z >= q)

如果你像这样迭代测试数字，你应该从一个特定的数字开始倒计时，这样你就可以保证一个满足条件的数字是实际的GCD。并且这个特定的起始数字必须是最小的3个数字。和你的方法的完整工作版本在这里：

public static int recursiveMethod(int x, int y, int z, int q) 
{
    int largestVar;
    int xRes = x % q;
    int yRes = y % q;
    int zRes = z % q;
    if (xRes == 0 && yRes == 0 && zRes == 0) {
        largestVar = q;
        if (x >= q && y >= q && z >= q) {
            return largestVar;
        }
    } else {
        q--;
    }
    return recursiveMethod(x, y, z, q);
}

示例调用：

int x = recursiveMethod(30, 60, 45, 30); // x = 15 after this execution.

Answer 3

不要忘记gcd(x, y, z) = gcd(gcd(x, y), z).所以，如果你想要一个更简单的算法，你可以用两个数字实现gcd，然后调用3个数字的方法。

public static int GCD(int x, int y) {
   if (y == 0) return x;
   return GCD(x, x % y);
}

然后对于三个数字：

public static int GCDfor3 (int x, int y, int z) {
    return GCD(GCD(x, y), z)
}