Menu

- Chapter 1 Distilled
- Introduction
- 1.1 - The Elements Of Programming
- Expressions
- Naming and the Environment
- Evaluating Combinations
- Defining New Functions
- The Substitution Model
- Exercises
- Predicates
- Conditional Expressions
- Example: Newton’s Method
- Functions as Black-Box Abstractions
- 1.2 - Procedures and the Processes They Generate
- Linear Recursion and Iteration
- Tree Recursion
- Orders of Growth
- Exponentiation
- Example: Testing For Primality
- 1.3 Higher Order Functions
- Project - Blackjack

- Chapter 2 Distilled
- Introduction
- Data Abstraction
- Everything From Nothing
- Abstractions In Clojure
- Clojure's Data Structures
- Data Abstraction, Revisited
- Escher
- Project - Escher
- Symbolic Data
- Representing Sets
- Huffman Encoding Trees
- Zippers

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, 2, 3, 5, 8, 13, 21 \dots $$

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:

```
(defn 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. Notice below 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`

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

$$ a \leftarrow a+b $$ $$ b \leftarrow a $$

It is not hard to show that, aer applying this transformation `n`

times, `a`

and `b`

will be equal, respectively, to `Fib(n + 1)`

and
`Fib(n)`

. Thus, we can compute Fibonacci numbers iteratively using the
procedure

```
(defn fib [n]
(fib-iter 1 0 n))
(defn- fib-iter [a b count]
(if (= count 0)
b
(fib-iter (+ a b) a (- count 1))))
```

This second method for computing `fib(n)`

is a linear iteration. The
difference in number of steps required by the two methods—one linear
in n, one growing as fast as `fib(n`

) itself—is enormous, even for
small inputs.

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 (the interpretation process itself is recursive in this way). 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.

One approach to coping with redundant computations is to arrange matters so that we automatically construct a table of values as they are computed. Each time we are asked to apply the procedure to some argument, we first look to see if the value is already stored in the table, in which case we avoid performing the redundant computation. This strategy, known as tabulation or memoization , can be implemented in a straightforward way. Tabulation can sometimes be used to transform processes that require an exponential number of steps into processes whose space and time requirements grow linearly with the input.

A function f is defined by the rule that

Write a procedure that computes f by means of

- a recursive process
- an iterative process