StackoverflowError

Question

J'ai ce genre d'erreur bizarre. J'essaye d'implémenter l'algorithme euclidien de base en utilisant la classe BigInteger comme montré. Quand je l'exécute, il lance StackoverFlowError, alors que si je le débogue, il fonctionne correctement et me donne la bonne réponse.

Je ne comprends pas sérieusement la différence lors du débogage et de l'exécution normale.

 static BigInteger gcd(BigInteger a, BigInteger b) { 
     if (a.equals(BigInteger.ZERO)) { 
      return b; 
     } else if (b.equals(BigInteger.ZERO)) { 
      return a; 
     } 
     BigInteger max = a.max(b); 
     BigInteger min = a.min(b); 
     return gcd(max.subtract(min), min); 
     } 

Answer 1

Ce n'est pas l'algorithme euclidien pour GCD. L'algorithme GCD correct peut être facilement défini comme une procédure récursive parce que le nombre d'itérations est en pratique petit. Mais cet algorithme implémenté incorrectement peut fonctionner pour des millions d'itérations, par ex. si 'a' est 1 000 000 et 'b' est 1, ce qui donne 1 million d'appels récursifs. (Cependant, l'appel est un appel récursif de queue, donc une bonne implémentation Java permettrait d'optimiser le cadre de la pile.) Cependant, pour une raison inconnue, la version du débogueur pourrait implémenter l'optimisation des appels. , bien que cela semble étrange.)

Dans l'algorithme actuel, l'étape récursive est (a% b, b) au lieu de (a - b, b). Google pour "algorithme GCD euclid".

Answer 2

L'algorithme nécessiterait moins d'appels si vous avez remplacé la soustraction répétée par une opération mod. Vérifiez ce qui se passe si max est très grand et min est très petit.