Free Structure and Interpretation of Computer Programs by Harold Abelson and Gerald Jay Sussman with Julie Sussman Page A

make change.

    We can easily translate this description into a recursive
procedure:

    (define (count-change amount)
  (cc amount 5))
(define (cc amount kinds-of-coins)
  (cond ((= amount 0) 1)
        ((or (< amount 0) (= kinds-of-coins 0)) 0)
        (else (+ (cc amount
                     (- kinds-of-coins 1))
                 (cc (- amount
                        (first-denomination kinds-of-coins))
                     kinds-of-coins)))))
(define (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)))

    (The
first-denomination
procedure takes as input the number of
kinds of coins available and returns the denomination of the first
kind. Here we are thinking of the coins as arranged in order from
largest to smallest, but any order would do as well.) We can now
answer our original question about changing a dollar:

    (count-change 100)
292

    Count-change
generates a tree-recursive process with
redundancies similar to those in our first implementation of
fib
. (It will take quite a while for that 292 to be computed.) On
the other hand, it is not obvious how to design a better algorithm
for computing the result, and we leave this problem as a challenge.
The observation that atree-recursive process may be highly
inefficient but often easy to specify and understand has led people to
propose that one could get the best of both worlds by designing a
“smart compiler” that could transform tree-recursive procedures into
more efficient procedures that compute the same result. 34

    Exercise 1.11.   A function
f
is defined by the rule that
f
(
n
) =
n
if
n
<3 and
f
(
n
) =
f
(
n
- 1) + 2
f
(
n
- 2) + 3
f
(
n
- 3) if
n
>
3. Write a procedure that
computes
f
by means of a recursive process. Write a procedure that
computes
f
by means of an iterative process.

    Exercise 1.12.   The following pattern of numbers is called
Pascal's triangle
.

    The numbers at the edge of the triangle are all 1, and
each number inside the triangle is the sum of the two numbers above it. 35 Write a procedure that computes elements of Pascal's triangle by means
of a recursive process.

    Exercise 1.13.   Prove that
F
i
b
(
n
) is the closest integer to
φ
n /√5,
where
φ
= (1 + √5)/2. Hint: Let
ψ
= (1 - √5)/2. Use
induction and the definition of the Fibonacci numbers (see
section  1.2.2 ) to prove that
F
i
b
(
n
) = (
φ
n -
ψ
n )/√5.

1.2.3  Orders of Growth
    The previous examples illustrate that processes can differ
considerably in the rates at which they consume computational
resources. One convenient way to describe this difference is to use
the notion of
order of growth
to obtain a gross measure of theresources required by a process as the inputs become larger.
    Let
n
be a parameter that measures the size of the problem, and let
R
(
n
) be the amount of resources the process requires for a problem
of size
n
. In our previous examples we took
n
to be the number
for which a given function is to be computed, but there are other
possibilities. For instance, if our goal is to compute an
approximation to the square root of a number, we might take
n
to be
the number of digits accuracy required. For matrix multiplication we
might take
n
to be the number of rows in the matrices. In general
there are a number of properties of the problem with respect to which
it will be desirable to analyze a given process. Similarly,
R
(
n
)
might measure the number of internal storage registers used, the
number of elementary machine operations performed, and so on. In
computers that do only a fixed number of operations at a time, the
time required will be proportional to the number of elementary machine
operations performed.
    We say