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之后，你也不需要检查其他的因子。