Ошибка переполнения стека Java

Question

Я пытаюсь запрограммировать алгоритм GCD, и все кажется правильным, за исключением StackOverflowError. Вот код:

public class Gcd { 
    public static BigInteger gcdNaive(BigInteger a, BigInteger b) { 
     int res = a.compareTo(b); 

     if (res == 0) { 
      BigInteger g = a; 
      return g; 
     } 
     else if (res == 1) { 
      BigInteger h = a.subtract(b); 
      a = h; 
      return gcdNaive(a, b); 
     } 
     else if (res == -1) { 
      BigInteger g = b.subtract(a); 
      b = g; 
      return gcdNaive(a, b); 
     } 

     return BigInteger.ZERO; 
    } 

    public static BigInteger gcdEuclid(BigInteger a, BigInteger b) { 
     if(b == BigInteger.ZERO) { 
      BigInteger g = a; 
      return g; 
     } 
     else if (b != BigInteger.ZERO) { 
      BigInteger g = b; 
      BigInteger h = a.mod(b); 
      a = g; 
      b = h; 
      return gcdEuclid(a, b); 
     } 

     return BigInteger.ZERO; 
    } 
} 

Исключение:

Exception in thread "main" java.lang.StackOverflowError 


    at Gcd.gcdNaive(Gcd.java:7) 
    at Gcd.gcdNaive(Gcd.java:19) 

Answer 1

Раствор для gcdNaive является:

public static BigInteger gcdNaive(BigInteger a, BigInteger b) { 
    int res = a.compareTo(b); 

    if(res == 0) 
    { 
     return b; 
    } 

    if(res == 1) 
    { 
     a = a.subtract(b); 
     return gcdNaive(a, b); 
    } 
    else 
    { 
     b = b.subtract(a); 
     return gcdNaive(a, b); 
    } 
} 

Комплексное решение для gcdEuclid является

public static BigInteger gcdEuclid(BigInteger a, BigInteger b) { 

    if(b == BigInteger.ZERO) 
    { 
     return a; 
    } 

    return gcdEuclid(b, a.mod(b)); 
}