# 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:

- Go through each club.
- You can choose to use current club and use it again,
- Or you can choose to use current club and use next club,
- 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.