Section 3: Accumulators

Table of Contents > Chapter 2 > Section 3

In CPSC 110, you learned that instead of accumulating the computation that arises from natural recursion in memory, we can explicitly accumulate the desired result as we process the data. We achieved this using a special parameter called an accumulator. In the case of sum_loi, we use the accumulator to accumulate the sum of the entries in loi that have been seen so far. In the process, we put the recursive call in tail position.

Here's the process for designing our sum_loi function to make use of an accumulator and tail recursion:

Step 1: design the function in the usual way up to the point where you have the function template in place (note that for brevity we will omit the signature, purpose and tests):

define sum_loi(loi):
    if loi == []:
        return ...
    else:
        return ...loi[0] ...sum_loi(loi[1:])

Step 2: wrap this function in an outer function of the same name, rename the parameter on the outer function to something like loi0 and have the outer function make a call to the inner function.

define sum_loi(loi0):
    define sum_loi(loi):
        if loi == []:
          return ...
      else:
            return ...loi[0] ...sum_loi(loi[1:])

    return sum_loi(loi0)

Step 3: add an accumulator parameter to the inner function and modify the template to account for the additional parameter:

define sum_loi(loi0):
    define sum_loi(loi, acc):
        if loi == []:
          return ...acc
      else:
            return sum_loi(loi[1:], ...loi[0] ...acc)

    return sum_loi(loi0, ...)

Note:

We have used ... as the accumulator argument when calling the inner function from the outer function
The recursive call is in tail position. This means that that value produced by the recursive call is the value that we return - no other computation needs to be performed after the recursive call returns.

Step 4: add documentation to the inner function that includes:

the type of the accumulator
an invariant that specifies what the accumulator represents at each step of the computation
an example that illustrates how the accumulator works

define sum_loi(loi0):
    define sum_loi(loi, acc):
        """
        Accumulator: acc is int

        Invariant: acc is the sum of all the integers in loi0
        prior to loi[0]

        sum_loi([3, 4, 2], 0)
        sum_loi([4, 2], 3)
        sum_loi([2], 7)
        sum_loi([], 9)
        """
        if loi == []:
          return ...acc
      else:
            return sum_loi(loi[1:], ...loi[0] ...acc)

    return sum_loi(loi0, ...)

Step 5: use the invariant and the example to complete the body of the function.

The final version of the code can be found in .

The language that you learned in CPSC 110 optimizes these tail recursive calls so that no additional memory is consumed by the recursive call to the function - the depth of the recursion can therefore be arbitrarily deep without risk of exhausting available memory. Let's see what happens in Python:

>>> sum_loi(list(range(10)))
 45 
>>> sum_loi(list(range(100)) )
4950
 >>> sum_loi(list(range(1000)))
 ...
 RuntimeError: maximum recursion depth exceeded

Unfortunately, Python does not optimize tail recursive calls. Even though we accumulate the sum of the integers as the list is recursively processed and have the recursive call in tail position, the Python interpreter still consumes memory on each recursive call to the function. Note that many other languages, Java included, behave the same way. For this reason, these languages provide another mechanism known as a loop for processing data of arbitrary size. Designing with loops is the topic of our next chapter.