Previous | Table of Contents | Next |
There are situations in which a procedure is called many times with the same argument values and always returns the same value for those arguments. Obviously, recomputation is expensive in terms of time and in some cases in terms of space. Also, in some cases, the amount of such redundant computation is so great that it limits what is possible to compute.
6.3.3.1. The Problem
The problem with redundant computation is particularly serious when a computation is defined recursively, so one call may lead to many other calls. The examples of this situation that are easy to understand are somewhat artificial in the sense that they are not likely to occur in real programs. Nevertheless, the basic problem is real and can occur when searching databases, traversing structures, and so forth.
The Fibonacci numbers, mentioned earlier, provide an example. The Fibonacci numbers are defined by the recurrence relation:
f (i ) = 1 i = 1, 2 f (i ) = f (i 1) + f (i 2) i > 2
The resulting sequence is 1, 1, 2, 3, 5, 8, 13, 21, 34, and so on. The numbers get large quickly. For example, f(35) is 9,227,465.
A straightforward procedure for computing the ith Fibonacci number follows directly from the recurrence:
procedure f(i) if i = (1 | 2) then return 1 else return f(i 1) + f(i 2) end
The problem with this kind of a formulation is not that any one call is expensive. The problem is that one call leads to another, and many of the calls have the same argument and hence result in redundant computation. For example, f(8) calls f(7) and f(6), f(7) calls f(6) and f(5), and so on. The way the calls add up is illustrated by the computation of f(10), where the numbers of calls are
f(10) | 1 |
f(9) | 1 |
f(8) | 2 |
f(7) | 3 |
f(6) | 5 |
f(5) | 8 |
f(4) | 13 |
f(3) | 21 |
f(2) | 34 |
f(1) | 21 |
total | 109 |
Note that except for f(1), the number of calls itself forms the Fibonacci sequence. This is not a coincidence, and the consequences are significant, considering how rapidly the Fibonacci numbers grow.
Of course, computing Fibonacci numbers recursively is not the best approach. An efficient iterative method was given earlier.
Although there are general methods for converting recursive formulations to iterative ones (Kleene, 1952), they are impractical in many cases. Consider this nested recurrence (Hofstadter, 1979):
q (i ) = 1 i = 1, 2 q (i ) = q (i q (i 1)) + q (i q (i 2)) i > 2
The sequence for this recurrence is chaotic in the sense that values do not get progressively larger. Instead, a value sometimes is less than the preceding one, although on the average the values increase. Heres how the sequence starts: 1, 1, 2, 3, 3, 4, 5, 5, 6, 6, 6, 8, 8, 8, 10, 9, 10, 11, 11, 12, 12, 12, 16, 14, 14, 16, and so on. The underscores show values that are less than their predecessors.
A recursive procedure based on the preceding recurrence is trivial to formulate:
procedure q(i) if i = (1 | 2) then return 1 else return q(i q(i 1)) + q(i q(i 2)) end
Although redundant computation clearly is a problem in the recursive computation of the Fibonacci sequence, it is a much more serious problem here. The calls for computing q(10) are
q(10) | 1 |
q(9) | 1 |
q(8) | 2 |
q(7) | 3 |
q(6) | 5 |
q(5) | 9 |
q(4) | 22 |
q(3) | 77 |
q(2) | 284 |
q(1) | 77 |
total | 481 |
For q(11), q(12), and q(13) computed in this way, the total numbers of calls are 813, 1,393, and 2,325, respectively. Getting values of q(i) for large i in this manner is impractical.
Previous | Table of Contents | Next |