遞歸困境

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) 
}