递归困境

Question

我试图创建代码来找到三个用户输入数字的GCD。我的目标是用输入数字调用该方法，除以初始化为1的q，只有余数为零才记录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，并再次调用recursiveMethod q = 1！这个过程重演。

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。没有注意到那一点。在本地范围内，maximumVar的值不会通过递归调用进行维护，因此它也必须传递给recursiveMethod调用（或者声明为类范围变量或其他类）。一个合适的起始值为0.

Answer 2

一个我注意到的失误，你如果条件是错误的：

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

如果你是每次一递增Q，用合适的号码，你总是会用完栈。我会为每对数字使用欧几里德算法，然后从那里开始。我的意思是，如果它在a，b，c之间是共同的，它必须是a和b或a和c或c和b之间的共同因子，对吗？

https://math.stackexchange.com/questions/85830/how-to-use-the-extended-euclidean-algorithm-manually

Answer 4

不要忘记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) 
}