title: Recursive memoization solutio to solve "count changes"
body: <p>I am trying to solving the "Counting Change" problem with memorization. </p>
  
  <blockquote>
    <p>Consider the following problem: How many different ways can we make change of $1.00, given half-dollars, quarters, dimes, nickels, and pennies? More generally, can we write a function to compute the number of ways to change any given amount of money using any set of currency denominations?</p>
  </blockquote>
  
  <p>And the intuitive solution with recursoin.</p>
  
  <p>The number of ways to change an amount a using n kinds of coins equals</p>
  
  <ol>
  <li>the number of ways to change a using all but the first kind of coin, plus</li>
  <li>the number of ways to change the smaller amount a - d using all n kinds of coins, where d is the denomination of the first kind of coin.</li>
  </ol>
  
  <hr>
  
  <pre><code>#+BEGIN_SRC python :results output
  # cache = {} # add cache 
  def count_change(a, kinds=(50, 25, 10, 5, 1)):
      """Return the number of ways to change amount a using coin kinds."""
      if a == 0:
          return 1
      if a &lt; 0 or len(kinds) == 0:
          return 0
      d = kinds[0]　# d for digit
      return count_change(a, kinds[1:]) + count_change(a - d, kinds) 
  print(count_change(100))
  #+END_SRC
  #+RESULTS:
  : 292
  </code></pre>
  
  <p>I try to take advantage of memorization, </p>
  
  <pre><code>Signature: count_change(a, kinds=(50, 25, 10, 5, 1))
  Source:   
  def count_change(a, kinds=(50, 25, 10, 5, 1)):
      """Return the number of ways to change amount a using coin kinds."""
      if a == 0:
          return 1
      if a &lt; 0 or len(kinds) == 0:
          return 0
      d = kinds[0]
      cache[a] = count_change(a, kinds[1:]) + count_change(a - d, kinds)
      return cache[a]
  </code></pre>
  
  <p>It works properly for small number like </p>
  
  <pre><code>In [17]: count_change(120)
  Out[17]: 494
  </code></pre>
  
  <p>work on big numbers</p>
  
  <pre><code>In [18]: count_change(11000)                        
  ---------------------------------------------------------------------------
  RecursionError                            Traceback (most recent call last)
  &lt;ipython-input-18-52ba30c71509&gt; in &lt;module&gt;
  ----&gt; 1 count_change(11000)
  
  /tmp/ipython_edit_h0rppahk/ipython_edit_uxh2u429.py in count_change(a, kinds)
        9         return 0
       10     d = kinds[0]
  ---&gt; 11     cache[a] = count_change(a, kinds[1:]) + count_change(a - d, kinds)
       12     return cache[a]
  
  ... last 1 frames repeated, from the frame below ...
  
  /tmp/ipython_edit_h0rppahk/ipython_edit_uxh2u429.py in count_change(a, kinds)
        9         return 0
       10     d = kinds[0]
  ---&gt; 11     cache[a] = count_change(a, kinds[1:]) + count_change(a - d, kinds)
       12     return cache[a]
  
  RecursionError: maximum recursion depth exceeded in comparison
  </code></pre>
  
  <p>What's the problem with memorization solution?</p>