recursion: make changes with fewest coins
<p>I'm studing the data structure and algorithm in python. Here is the classic problem of recursion involving making change with the fewest coins. Here are the codes.
What I do not understand is line 2. why do we need <code>minCoins = change</code>? what does line 8-9 mean? can anyone helo explain that? thank you very much for help!</p>

<pre><code>def recMC(coinValueList,change):
   minCoins = change
   if change in coinValueList:
     return 1
   else:
      for i in [c for c in coinValueList if c &lt;= change]:
         numCoins = 1 + recMC(coinValueList,change-i)
         if numCoins &lt; minCoins:
            minCoins = numCoins
   return minCoins

print(recMC([1,5,10,25],63))
</code></pre>

<p><code>minCoins = change</code>: <code>minCoins</code> is initialized with the value of <code>change</code> which is the maximum value that <code>recMC</code> can return as the minimum value of a coin is 1, assuming integer values of coins.</p>

<p><code>if change in coinValueList: return 1</code>: base case 1 - if some coin has a value of that of <code>change</code> we just need to grab this 1 coin, thus returning 1</p>

<p>&emsp;<code>for i in [c for c in coinValueList if c &lt;= change]:</code>:
The function then loops through all possible values of 1 single coin to</p>

<p>&emsp;&emsp;<code>numCoins = 1 + recMC(coinValueList,change-i)</code>: deduct the coin value <code>i</code> from <code>change</code>, add 1 coin to the number of coins needed which is recursively calculated for the leftover change (<code>change-i</code>). This works inductively from the <em>2</em> base cases</p>

<p>&emsp;&emsp;<code>if numCoins &lt; minCoins: minCoins = numCoins</code> inside this loop effectively assigns the smallest number of coins possible to <code>minCoins</code></p>

<p>If <code>change</code> still had the initialized value of <code>minCoins</code> (implying no value <code>c</code> in <code>coinValueList</code> satisfies <code>c &lt;= change</code>), this means that the number of coins needed is also the value of <code>change</code>, i.e. <code>change</code> 1-unit coins. This is base case 2 that is based on the pre-condition that the coin with value 1 is always available.</p>

python algorithm recursion