title: Minimum coin change - Recursion
body: <p>I am a first year computer science student and am currently learning recursion. I attempted Leetcode 322. Coin Change with recursive approach, but couldn't do it. However I found one solution but I still cannot understand the code including time and space complexities after I tried to walk through the code. I have written my questions below. (I understand that my questions should be succinct). Thanks very much!</p>
  <p>I understand that there are three rules I need to comply when writing recursion.</p>
  <ol>
  <li>Define base case : In order for the recursive function to reach to and to avoid memory stackover flow error)</li>
  <li>Recurrence Relation: In the algorithm I write, I need to change the recursive function state and need to ensure it moves towards the base case</li>
  <li>Call itself recursively.</li>
  </ol>
  <p><strong>Java Code</strong></p>
  <pre><code>public int coinChange(int[] coins, int amount) {
          // Base case 
          if(amount==0) return 0;
  
          // Question 1 
          int n = amount+1;
          for(int coin : coins) {
              // Question 2
              int current = 0;
              if (amount &gt;= coin) {
                  int next = coinChange(coins, amount-coin);
                  if(next &gt;= 0)
                      current = 1+next;
              }
              if(current &gt; 0)
                  n = Math.min(n,current);
          }
          int finalCount = (n==amount+1) ? -1 : n;
          return finalCount;
      }
  </code></pre>
  <p><strong>1. Question 1:</strong> int n = amount+1; 1 is added because this is the inductive step? I have just completed discrete maths subject. This amount + 1 reminds me of Mathematical Induction: basic and inducive step.</p>
  <ul>
  <li>Basic step : P(1)</li>
  <li>Inductive Step: if P(n) is true, then P(n+1) is true.</li>
  </ul>
  <p><strong>2. Question 2:</strong> int current is initialised to 0. Is it to get rid of the permutations and make sure coins combination I get is unique one.
  For example, coins = [ 1, 2, 5], amount = 11, Permutations</p>
  <ul>
  <li>Option 1 [ 1, 2, 2, 2, 2]</li>
  <li>Option 2 [ 2, 1, 2, 2, 2]</li>
  <li>Option 3 [ 2, 2, 2, 1, 2], etc</li>
  </ul>
  <p><strong>3. Question 3:</strong> When I draw recursive tree and I can see how coinChain numbers is calculated. But I couldn't understand <code>if(next &gt;= 0) curr = 1+next;</code> Why 1 is required to be added?
  coinChange(coins, amount -1).</p>
  <p>coins = [ 1, 2, 5], amount = 11</p>
  <pre><code>
                                     11 (amount)
                               1/    2|     \5  (coin)
                               10     9      6
                           1/  2| \5
                          9    8   5
                     1/  2| \5
                     8   7    4
                  1/ 2| \5
                 7   6  3
             1/  2| \5
             6    5  2
         1/  2| \5
        5     4  1
      1/ 2| \5
     4   3   0
  1/ 2| \5
  etc. until I get to 0. 
  </code></pre>
  <p><strong>4. Question 4:</strong> <code>int finalCount = (n==amount+1) ? -1 : n;</code> Instead of this, is it better to write as below to improve readability? And also, why I need to return -1 when n == amount +1? I couldn't think any case???</p>
  <pre><code>if(n == amount + 1)
    return -1
  else 
    return n;
  </code></pre>
  <p><strong>5. Question 5 :</strong> Time complexity
  Is it O(number of coins * amount - pseudo-polynomial) or O(number of coins^amount)?</p>
  <p><strong>6. Question 6 :</strong> Space complexity
  Is it O(n) each function call will be stored in the stack memory and will be popped back progressively once it comes back from base case.</p>
  <p>Thanks very much in advance.</p>
  <p>I have read a few online posts including the following references.</p>
  <p><strong>References</strong></p>
  <ol>
  <li><a href="https://runestone.academy/runestone/books/published/pythonds/Recursion/DynamicProgramming.html" rel="nofollow noreferrer">https://runestone.academy/runestone/books/published/pythonds/Recursion/DynamicProgramming.html</a></li>
  <li><a href="http://www.cs.uni.edu/%7Efienup/cs270s04/lectures/lec6_1-29-04_coin_change_web.htm" rel="nofollow noreferrer">http://www.cs.uni.edu/~fienup/cs270s04/lectures/lec6_1-29-04_coin_change_web.htm</a></li>
  </ol>