的Java：找出一個數是素數遞歸

Question

我正在寫一個數是素數，則返回true的功能，否則爲假

這裏是我當前的代碼：

public static boolean checkPrime(int n, int currDivisor){ 
     if(n < 2){ 
      return true; 
     } 
     if(currDivisor == (n/2)){ 
      return true; 
     } 
     else if(n % currDivisor == 0){ 
      return false;   
     } 
     else{ 
      return checkPrime(n, currDivisor + 1); 
     } 
    } 

    public static void main(String[] args){ 
     System.out.println(checkPrime(23352, 2)); 
    } 

它的工作原理對於大量的測試用例，除了像「1000000007」這樣的數字，我得到的內存不足錯誤。我怎樣才能調整這個代碼來提高空間效率？

Answer 1

我看到的第一個問題是你的程序是越野車。它似乎認爲0，1，& 4是素數，而3不是。我看到的第二個問題是，在遞歸之前，它正在浪費堆棧框架，無法正確處理簡單情況。這裏是我的代碼的返工：

public static boolean checkPrime(int n) { 
    return checkPrime1(n, 3); 
} 

public static boolean checkPrime1(int n, int currDivisor) { 
    if (n < 2) { 
     return false; 
    } 

    if (n % 2 == 0) { 
     return (n == 2); 
    } 

    if (currDivisor * currDivisor > n) { 
     return true; 
    } 

    if (n % currDivisor == 0) { 
     return false; 
    } 

    return checkPrime1(n, currDivisor + 2); 
} 

至於處理：

System.out.println(checkPrime(1000000007)); 

你還是會得到一個java.lang.StackOverflowError但這不是故事的結束。大多數語言都會決定分配給特定用途的內存量。像Perl這種罕見的語言將重新分配內存給任何資源要求最多的內存，而不是假設程序應該如何表現。

您可以更改分配給Java堆棧的內存量 - 調用java與-Xss2m參數分配足夠的額外堆棧，讓你測試1000000007

如果你改變了三種int（true，順便說一句。）以上long聲明，你就可以，只要你展開堆棧像2547487897L或更大的測試號（-Xss4m在這種情況下）。

我並不是說這是遞歸一個很好的問題，不是。但如果你要使用遞歸，明智地使用它。這是很糟糕的遞歸，給遞歸一個壞名字。有低效的遞歸Fibonnaci算法（通常雙遞歸）和高效（單遞歸）算法。遞歸代碼通常對遞歸數據效果最好。

某些語言（不是Java始終如一）可以將上述代碼優化爲尾遞歸併使其有效地反覆執行。

Answer 2

根本問題是遞歸不是正確的方法。原始性測試不是一個遞歸問題，對於大數量，您總是會很快超出可用存儲空間。我建議你在網上做一些關於「素質測試」主題的研究。

至於判斷問題是否遞歸的經驗法則，我已經這麼做了很長時間，我不確定我能否表達完全直觀的東西，所以我會讓別人去做。

但是，值得指出的是，在數學上遞歸的一些問題具有計算解決方案，其中迭代遠遠好於天真遞歸。斐波那契數字的主要（哈！）例子。對於大型的天真遞歸解決方案來說，它可以消耗內存並執行冗餘計算，而迭代解決方案更快，更好。