Функция не возвращается при правильной инструкции возврата для некоторых тестовых случаев

Question

Это мой код.

Вопрос: Я получаю неверный вывод для тестового случая: a = 100 b = 54.

Проблема Найдено: Почему это, что, когда первый if условие в методе computeGcd вызывается (т.е. когда a==b или a делится на b), что она не возвращается из этого, если блок обратно к линии в основной метод, откуда он был вызван?

Вместо этого он переходит к последнему оператору return в методе и возвращает от него старое значение 'b'. Что мне не хватает?

public static void main(String[] args) { 
    Scanner sc = new Scanner(System.in); 
    int a = sc.nextInt(); 
    int b = sc.nextInt(); 
    if (a >= b) { 
     System.out.println("\n\nfinal values are: " + computeGcd(a, b) 
       + " for a is=" + a + " and b=" + b);} 
    else 
     System.out.println(computeGcd(b, a)); 
    sc.close(); 
} 

public static int computeGcd(int a, int b) { 
    System.out.println("out side a is=" + a + " and b=" + b); 
    if (a == b || a % b == 0) { 
     System.out.println("Inside final : a is=" + a + " and b=" + b); 
     return b; 
    } else { 
     a = (a - b * (a/b)); 
     if (a > b) { 
      System.out.println("Inside test a>b : a is=" + a + " and b=" + b); 
      computeGcd(a, b); 
     } 
     if (b > a) { 
      System.out.println("Inside test a<b : a is=" + a + " and b=" + b); 
      computeGcd(b, a); 
     } 
    } 
    System.out.println("exiting else"); 
    System.out.println("i m here :P "); 
    return b; 
} 

отладки для тестового случая: 100 54

Answer 1

Ваши рекурсивные вызовы не return.

if (a > b) { 
    System.out.println("Inside test a>b : a is=" + a + " and b=" + b); 
    return computeGcd(a, b); // <-- add return 
} else { // if (b > a) { 
    System.out.println("Inside test a<b : a is=" + a + " and b=" + b); 
    return computeGcd(b, a); // <-- add return 
} 

Альтернативно

Максимально возможный НОД есть квадратный корень из минимума двух терминов. Вы можете начать с этого значения и итерации назад. Нечто подобное,

public static int computeGcd(int a, int b) { 
    if (a == b) { 
     return a; 
    } 
    for (int i = (int) Math.sqrt(Math.min(a, b)); i >= 2; i--) { 
     if (a % i == 0 && b % i == 0) { 
      return i; 
     } 
    } 
    return 1; 
} 

который возвращает 2 (для 100, 54), потому что одна половина 54 является 27 что 3 оставляя только общие знаменатели, являющиеся 2 и 1.