Another common pattern of computation is called * tree recursion*.
As an example, consider computing the sequence of Fibonacci numbers,
in which each number is the sum of the preceding two:

`
0,1,1,2,3,5,8,13,21,...
`

In general, the Fibonacci numbers can be defined by the rule

We can immediately translate this definition into a recursive procedure for computing Fibonacci numbers:

(define (fib n) (cond ((= n 0) 0) ((= n 1) 1) (else (+ (fib (- n 1)) (fib (- n 2))))))

Consider the pattern of this computation. To compute ` (fib 5)`,
we compute ` (fib 4)` and ` (fib 3)`. To compute ` (fib 4)`,
we compute ` (fib 3)` and ` (fib 2)`. In general, the evolved
process looks like a tree, as shown in figure 1.5.
Notice that the branches split into two at each level (except at the
bottom); this reflects the fact that the ` fib` procedure calls
itself twice each time it is invoked.

This procedure is instructive as a prototypical tree recursion, but it is a terrible way to compute Fibonacci numbers because it does so much redundant computation.

**Figure 1.5** The tree recursive process generated in computing `(fib 5).`

Notice in figure 1.5 that the
entire computation of ` (fib 3)` almost half the work
is duplicated. In fact, it is not hard to show that the number
of times the procedure will compute ` (fib 1)` or ` (fib
0)` (the number of leaves in the above tree, in general) is
precisely Fib (*n*+1). To get an idea of how bad this is, one
can show that the value of Fib (*n*) grows exponentially with
*n*. More precisely (see exercise 1.13), Fib (*n*) is the
closest integer to _{}, where

is the *golden ratio*, which satisfies the equation

Thus, the process uses a number of steps that grows exponentially with the input. On the other hand, the space required grows only linearly with the input, because we need keep track only of which nodes are above us in the tree at any point in the computation. In general, the number of steps required by a tree-recursive process will be proportional to the number of nodes in the tree, while the space required will be proportional to the maximum depth of the tree.

We can also formulate an iterative process for computing the Fibonacci
numbers. The idea is to use a pair of integers *a* and
*b*, initialized to Fib`(1)=1` and Fib`(0)=0`,
and to repeatedly apply the simultaneous transformations

It is not hard to show that, after applying this transformation
*n* times, *a* and *b* will be equal,
respectively, to Fib`( n+1)` and
Fib

This second method for computing Fib ((define (fib n) (fib-iter 1 0 n)) (define (fib-iter a b count) (if (= count 0) b (fib-iter (+ a b) a (- count 1))))

One should not conclude from this that tree-recursive processes are
useless. When we consider processes that operate on hierarchically
structured data rather than numbers, we will find that tree recursion
is a natural and powerful tool. ^{32}

But even in numerical operations, tree-recursive processes can be
useful in helping us to understand and design programs. For instance,
although the first ` fib` procedure is much less efficient than
the second one, it is more straightforward, being little more than a
translation into Lisp of the definition of the Fibonacci sequence. To
formulate the iterative algorithm required noticing that the
computation could be recast as an iteration with three state
variables.

**Example: Counting change**

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

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}

We can easily translate this description into a recursive procedure:

(The(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)))

`
(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 a tree-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 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.1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 ...

**Exercise 1.13**

Prove that Fib (*n*) is the closest integer to _{}, where _{}. Hint: Let _{}. Use induction and the definition of the
Fibonacci numbers (see section 1.2.2) to prove that Fib (*n*) =
_{}.