Java - StackOverflowError pour le premier récursion

Question

Pourquoi ce code me donne un StackOverflowError? J'essaie de faire fonctionner les nombres premiers plus rapidement que O(n**2).

Mon code:

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

Il y a une erreur dans le code qui rend la récursion sans fin.

Mais même si ce n'était pas le cas, vous créez au total n cadres de pile pour countPrimes. Rendez n assez grand et vous obtiendrez un débordement de pile.

Dans ce cas, vous pouvez facilement utiliser une boucle au lieu de la récursion. Cela fonctionnera aussi légèrement plus vite.

Une accélération beaucoup plus efficace est possible dans isPrime, vous avez juste besoin de vérifier les diviseurs jusqu'à la racine carrée du nombre. Et après avoir vérifié 2, vous n'avez pas besoin de vérifier d'autres diviseurs pairs.