實現遞歸函數來查找HCF/GCD java

我正在使用euclids algorythm的簡化版本來查找兩個整數的hcf。使用遞歸函數。似乎沒有工作，但它始終只是返回。任何想法爲什麼它最終沒有返回a + b？實現遞歸函數來查找HCF/GCD java

public class Euclid { 

    public static void main(String[] args) { 
    // TODO Class to find HCF (GCD) of two ints, using recursion 

    Euclid r = new Euclid(); 
    System.out.println(r.hcf(188, 112)); 
    } 

    public int hcf(int a, int b){ 
    int c = -11; 
    if(a == 0 || b == 0){ 
     return a+b; // base case 
    } 
    else if (a > b){ 
     return hcf(a-b, b); 
    } 
    else if (b > a){ 
     return hcf(b-a, a); 
    } 
    return c; 
} 
}

來源

2014-02-07 John Setter

當你發現你最終傳遞a和b，使得a==b最大公約數。你不處理這種情況，所以返回c。

一個簡單的解決方法是隻刪除最後的if分支，以便在那裏處理a==b大小寫。

if(a == 0 || b == 0){ 
    return a+b; // base case 
} 
else if (a > b){ 
    return hcf(a-b, b); 
} 
else { // b > a or a == b 
    return hcf(b-a, a); 
}

來源

2014-02-07 17:11:53 Joni

首先，您不能從static main調用非靜態方法。其次，你的算法有很多情況，很難說出你正在做什麼。這是我在幾年前爲Python中的Euclid的GCD寫的一行代碼。讓我們看看我們是否可以將它翻譯成Java。

def gcd(a, b): 
    return b if not a%b else gcd(b, a%b)

這裏是在Java中。

static int gcd(int a, int b) { 
    if(!(a % b)) return b; 
    return gcd(b, a%b); 
}

這似乎比你想要做的更簡單。

來源

2014-02-07 17:13:54 Rainbolt

是的。 'int hcf（int a，int b）{return b == 0？ a：hcf（b，a％b）; 「看起來更簡單，但那不是重點。這個方法是不是靜態的，它在類實例中被調用。 – tkroman

@cdshines不與任何實例變量交互的方法應該始終是靜態的。否則，每個實例都必須攜帶它。這就像額外的行李。爲了進一步說明我的觀點，想象一下，如果main不是靜態 – Rainbolt

情況並非如此。 – tkroman

實現遞歸函數來查找HCF/GCD java

回答

相關問題