The below code gives -1 output for 25,15 I can't figure out why. please help

public static int getGreatestCommonDivisor(int first, int second){

        if(first<10 || second<10){
            return -1;
        }

        else{
            int remaining = first %second;

            if(remaining != 0){
                return getGreatestCommonDivisor(second , remaining);
            }
            else{
                return second;
            }
        }



    }

CodePudding user response：

Because 25 is 10, 15 is 5 and 5 less than 10.

CodePudding user response：

A sample outlook onto the recursion tree for the code given will be like

                             gcd(25, 15)
                              /
                             /
                           gcd(15, 10)
                           /
                          /
                         gcd(10, 5) - here we have second < 10, so -1 will be returned and thats the problem.  

Fix : Fix can be, you can get rid of the if statement and keep the remaining code there itself.

public static int getGreatestCommonDivisor(int first, int second){

            int remaining = first %second;

            if(remaining != 0)
                return getGreatestCommonDivisor(second , remaining);
           return second;
    }

CodePudding user response：

Assuming you are trying to replicate the euclidian algorithm, all you need to do is remove the if statement at the start of your code:

public static int getGreatestCommonDivisor(int first, int second){
  int remaining = first %second;
  if(remaining != 0){
      return getGreatestCommonDivisor(second , remaining);
  }
  else{
      return second;
  }
}

Input:

System.out.println(getGreatestCommonDivisor(25,15));

Output:

5

As other people have mentioned, the specific reason that you are getting -1 with your input is because of the original if statement:

gcd(25,15) -> remaining = 25 % 15 = 10 -> gcd(15,10) = 5 -> gcd(10,5) -> 5 < 10 -> outputs -1