Accumulators

Accumulation of a result is a very useful way to view algorithms that traverse data structures. All recursive algorithms on recursive data types, e.g. lists and trees, can be viewed as accumulator algorithms.  Accumulator algorithms howver, or NOT limited to recursive data structures!

The fundamental notion of an accumulator algorithm is that the data needed for a particular calculation is spread throughout a data structure, thus necessitating a traversal process that "accumulates" the answer as the algorithm "travels" from one data element to the next.  Note that the notion of "accumulation" here is at its most general and does not necessarily mean an additive or multiplicative process--it could be one where each element is kept or discarded, as a filtering algorithm would do.

Let's look at an example of what the HTDP book calls a "natural" recursion algorithm:

;; sum a list of numbers
(define (sum lon)
   (cond
      [(empty? lon) 0]
      [(cons? lon) (+ (first lon) (sum (rest lon)))])) 

Look at the role of the recursive result "(sum (rest lon))".   The cons? clause can be described as the addition of first with the recursive result.   We can say that the recursive result is the accumulation of the sum of the rest of the list.   That is, the value returned by the recursive call to "sum" is the accumulated sum so far in the algorithm.    All the cons? clause is doing is to create a new value for the accumulated result by adding first to recursive result.

In this sort of algorithm, the final answer is created by sweeping the data from the rear of the list (i.e. from the empty list towards the front of the list)  and accumulating a sum as one sweeps through the data.   The accumulated result is passed along via the return value of the function.

We will call this style of accumulation a Reverse Accumulation algorithm because the result is being accumulated as one "reverses" back out of the data structure.