Recursion Question – Java – Minimum number of golf shots

I am trying to calculate the minimum number of shots I need to take based on a given number of club lengths. You can also think of it as the minimum number of coins needed for a given change.

My code is

   public static int golf(int holeLength, int[] clubLengths)
   {
   return golf(holeLength, clubLengths, 0);
   }

   public static int golf(int holeLength, int[] clubLengths, int shots)
   {
      if(holeLength==0) 
         shots+=0;
      else if(holeLength<0)
         shots=-1;
      else
      {      
         for(int i = 0; i<clubLengths.length; i++)
         {
            return golf(holeLength-clubLengths[i], clubLengths, shots+1);
         }
      }

      return shots;
   }

The issue here is that it only seems to give an answer based on the first number on the array. So for example, if I had {25,50,100} and I wanted to get to 100. Obviously, there is only a minimum of one shot required, yet the program will only calculate it using 25 and say 4. Similarly, if the first number is 21, then it will just give a stackoverflow.

Answer

Here is what is happening in your code: when the function runs the first loop, it gets the first element in clubLengths and returns right away without going to the next loop. You need to go through each possible clubs to use.

Here is my recursive solution:

  1. Go through each club.
  2. You can choose to use current club and use it again,
  3. Or you can choose to use current club and use next club,
  4. Or you can choose not to use current club and use next club.

I can implement this the following way:

public static int golf(int holeLength, int[] clubLengths) {
    int[][] dp = int[clubLengths.length()][holeLength+1];
    return golf(holeLength, clubLengths, 0, dp);
}

private static int golf(int holeLength, int[] clubLengths, int ind, int[][] dp) {
    if (holeLength == 0) return 0;
    if (holeLength < 0) return -1;
    if (ind >= clubLengths.length()) return -1;
    if (dp[ind][holeLength] != 0) return dp[ind][holeLength];

    int rec1 = golf(holeLength-clubLengths[ind], clubLengths, ind, dp);
    if (rec1 == -1) rec1 = Integer.MAX_VALUE;
    else rec1++;

    int rec2 = golf(holeLength-clubLengths[ind], clubLengths, ind+1, dp);
    if (rec2 == -1) rec2 == Integer.MAX_VALUE;
    else rec2++;

    int rec3 = golf(holeLength, clubLengths, ind+1, dp);
    if (rec3 == -1) rec3 = Integer.MAX_VALUE;

    int result = Math.min(rec1, rec2);
    result = Math.min(result, rec3);
    if (result == Integer.MAX_VALUE) result = -1;

    dp[ind][holeLength] = result;
    return result;
}

Along with recursion, I have also added dp to optimize time complexity. As a result, the time complexity of my solution would be O(k*n) where k is holeLength and n is number of elements in clubsLengths. If you do not want dp and want just pure recursion, you can just remove all usages of dp from above and the code will still work, but slower.