In order to solve this problem, we want to find the minimum number of coins needed to break down the amount, given values. Since the values array doesn't change, there's not really a point in including it as an input in our recursion. We'll assume we have access to it and we won't include it as an input. Here's the recursion we'll write:

1. Recursion

To make change for amount, you can subtract off any of the coin values from it and then make change for the remaining amount. This takes the 1 coin you used, plus the minimum possible number of coins it takes to make change for the remaining amount.

2. Base case

The recursion will call itself on smaller and smaller amounts, and it has to eventually stop.

One case where it should stop is when it reaches one of the coins in the values array. In this case, we should set the minimum number of coins equal to 1. Another equivalent way of doing this is to set $\texttt{numCoins}(0) = 0$ as the base case instead. This is easier, so we'll make this our base case.

We also need another base case since we might reach a negative number. We can't make change for a negative number numCoins(negative number), and so we'll set the number of coins to infinity so it gets ignored.

3. Code

To code this up, you should use Dynamic Programming to make sure that you don't make any redundant function calls.

To do this, you can compute all of the function calls in the order that they're needed, called "Tabulation". The function call numCoins(amount) depends on function calls using smaller inputs numCoins(smaller numbers). This means we can solve the problem by finding numCoins on smaller values first and bigger values last.

Time Complexity $O(\texttt{amount} \cdot |\texttt{values}|)$

Space Complexity $O(\texttt{amount})$