如果我從函數中刪除「else」，爲什麼輸出不同？

Question

我想寫一個GCD函數來計算使用歐幾里德算法的兩個整數的gcd。在函數中，如果我刪除「其他」，則輸出3，這是不正確的。但是，如果我使用「其他」它輸出1這是正確的輸出。我假設如果我不使用「其他」功能仍然是正確的。爲什麼我得到兩個不同的輸出。

這裏是我的代碼，

#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

你的函數有未定義行爲。當%運算符返回一個非零值時，你的函數根本沒有返回任何東西，所以輸出是垃圾。你需要返回遞歸調用的結果：

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