It takes only a bit of cleverness to come up with the iterative Fibonacci algorithm. In contrast,
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 procedure to
compute the number of ways to change any given amount of money?
This problem has a simple solution as a recursive procedure. Suppose we think of the types of coins
available as arranged in some order. Then the following relation holds:
The number of ways to change amount a using n kinds of coins equals
 the number of ways to change amount a using all but the first kind of coin, plus
 the number of ways to change amount a - d using all n kinds of coins, where d is the
denomination of the first kind of coin.
To see why this is true, observe that the ways to make change can be divided into two groups: those
that do not use any of the first kind of coin, and those that do. Therefore, the total number of ways
to make change for some amount is equal to the number of ways to make change for the amount
without using any of the first kind of coin, plus the number of ways to make change assuming that
we do use the first kind of coin. But the latter number is equal to the number of ways to make
change for the amount that remains after using a coin of the first kind.
Thus, we can recursively reduce the problem of changing a given amount to the problem of
changing smaller amounts using fewer kinds of coins. Consider this reduction rule carefully, and
convince yourself that we can use it to describe an algorithm if we specify the following degenerate
cases:33
 If a is exactly 0, we should count that as 1 way to make change.
 If a is less than 0, we should count that as 0 ways to make change.
 If n is 0, we should count that as 0 ways to make change.
We can easily translate this description into a recursive procedure

(defun count-change(amount)
  (cc amount 5 0))

(defun cc(amount kinds-of-coins callDepth)
  (progn (format t "~%cc( ~d ~d ~d)" amount kinds-of-coins callDepth)
	 (cond ( (= amount 0) (progn (format t "~%change success ") 1))
	       ( (or (< amount 0)
		     (= kinds-of-coins 0)) 0)
	       ( (+ (cc amount
			(- kinds-of-coins 1)
			(+ callDepth 1))
		    (cc (- amount
			   (first-denomination kinds-of-coins))
			kinds-of-coins
			(+ callDepth 1)	)))))) 


(defun first-denomination (kinds-of-coins)
  (cond ( (= kinds-of-coins 1) 1)
	( (= kinds-of-coins 2) 5)
	( (= kinds-of-coins 3) 10)
	( (= kinds-of-coins 4) 25)
	( (= kinds-of-coins 5) 50)))


CL-USER> (count-change 10)
cc( 10 5 0)
cc( 10 4 1)
cc( 10 3 2)
cc( 10 2 3)
cc( 10 1 4)
cc( 10 0 5)
cc( 9 1 5)
cc( 9 0 6)
cc( 8 1 6)
cc( 8 0 7)
cc( 7 1 7)
cc( 7 0 8)
cc( 6 1 8)
cc( 6 0 9)
cc( 5 1 9)
cc( 5 0 10)
cc( 4 1 10)
cc( 4 0 11)
cc( 3 1 11)
cc( 3 0 12)
cc( 2 1 12)
cc( 2 0 13)
cc( 1 1 13)
cc( 1 0 14)
cc( 0 1 14)
change success 
cc( 5 2 4)
cc( 5 1 5)
cc( 5 0 6)
cc( 4 1 6)
cc( 4 0 7)
cc( 3 1 7)
cc( 3 0 8)
cc( 2 1 8)
cc( 2 0 9)
cc( 1 1 9)
cc( 1 0 10)
cc( 0 1 10)
change success 
cc( 0 2 5)
change success 
cc( 0 3 3)
change success 
cc( -15 4 2)
cc( -40 5 1)
4