# SICP Exercise 1.14

You can find a counting coin tree elsewhere. Its form depends on the number of kinds of coins \(n\), the amount of money \(a\) and denominations \(m_1,...,m_n\). The code for recursive process is in the SICP book and you can have a look at the iterative process here: counting change. The behavior of recursive and iterative algorithms is practically identical. In simple terms, both processes try to build a sum \(\sum_{i=1}^n k_{i}m_i\) by incrementing indices \(k_i\) starting from zero values. The iterative algorithm does this in order (with four loops), and the recursive one builds a search tree, that corresponds to five loops in iterative algorithm. When the sum equals to the amount, this is a way of money change. As this sum becomes larger than the amount, this is wrong way, and both processes do not try to increase the sum further and try a different combination of index values. Now let's see how the number of all tries depends on the amount \(a\). I will ignore the issues of rounding to integer values, they are irrelevant for final results. The range of index \(k_1\) is \(a/m_1\), and it is proportional to \(a\). The range of index \(k_2\) is \((a-k_1 m_1)/m_2\), and it is proportional to \(a\) too. The number of pairs \((k_1,k_2)\) grows as \(a^2\). When we add next index, \(k_3\), its range is \((a-k_1 m_1-k_2 m_2)/m_3\) and the number of tuples \((k_1,k_2,k_3)\) is proportional to \(a^3\), etc. We conclude that \(\textrm{time}\sim O(a^n)\). The ranges of all indices \(k_i\) grow proportionally to \(a\), so \(\textrm{space}\sim O(a)\). Weiqun Zhang and other people (see comments there) got the same results. For the iterative algorithm , the number of loops is \(n-1\), and \(\textrm{time}\sim O(a^{n-1})\).