Recognizing the Need for an Accumulator

Recognizing the need for accumulators is not an easy task. We have seen two reasons, and they are the most prevalent reasons for adding accumulator parameters. In either case, it is critical that we first built a complete function based on a design recipe. Then we study the function and look for one of the following characteristics:

1. If the function is structurally recursive and if the result of a recursive application is processed by an auxiliary, recursive function, then we should consider the use of an accumulator parameter.

   Take the function invert as an example:

   ;; invert : (listof X) -> (listof X)
   ;; to construct the reverse of alox 
   ;; structural recursion  
   (define (invert alox) 
     (cond 
       [(empty? alox) empty] 
       [else (make-last-item (invert (rest alox)) (first alox))]))
   
   ;; make-last-item : X (listof X) -> (listof X) 
   ;; to add an-x to the end of alox 
   ;; structural recursion  
   (define (make-last-item an-x alox) 
     (cond 
       [(empty? alox) (list an-x)] 
       [else (cons (first alox) (make-last-item an-x (rest alox)))])) 
   

   The result of the recursive application produces the reverse of the rest of the list. It is processed by make-last-item, which adds the first item to the reverse of the rest and thus creates the reverse of the entire list. This second, auxiliary function is also recursive. We have thus identified a potential candidate. It is now time to study some hand-evaluations, as we did in section , to see whether an accumulator helps.
2. If we are dealing with a function based on generative recursion, we are faced with a much more difficult task. Our goal must be to understand whether the algorithm can fail to produce a result for inputs for which we expect a result. If so, adding a parameter that accumulates knowledge may help. Because these situations are complex, we postpone the discussion of an example until section .