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
Code
Explorer 2.2.
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.