Java - 針對主要遞歸的StackOverflowError

Question

爲什麼此代碼會給我一個stackoverflowerror？我試圖使計數素數函數比O(n**2)更快。

我的代碼：

public class TestingJavaCode { 

    public int countPrimes(int n) { 
     int counter = 0; 
     n--; 

     if (n > -1 && this.isPrime(n)) { 
      counter++; 
     } 

     counter += countPrimes(n); 

     return counter; 
    } 


    public boolean isPrime(int n) { 
     for (int i = 2; i < n; i++) { 
      if (n % i == 0) 
       return false; 
     } 
     return true; 
    } 

Answer 1

存在這樣使得遞歸無盡的代碼中的錯誤。

但即使情況並非如此，總共可爲countPrimes創建n堆棧幀。使n足夠大，你會得到一個堆棧溢出。

在這種情況下，您可以輕鬆使用循環而不是遞歸。這也會稍快一點。

在isPrime中可能會有更加有效的加速，您實際上只需要檢查除數直到數字的平方根。在檢查2之後，你也不需要檢查其他的因子。