How to Code: Accumulators

I recently finished working on How to Code: Complex Data from UBCx. I wanted to take a look at the second to last lesson on Accumulator. Hopefully by explaining the concepts here I can better internalize them for myself.

When to Use Accumulators

First of all, accumulators depend on a few other structures that I’m not going to get into here. The How to Code course meticulously built up to this point starting from the most basic data structures possible.

But in broad strokes, accumulators need a few things to work properly. First, accumulators work within recursive functions. How to Code used recursive functions exclusively but it’s worth mentioning if only because other languages won’t rely on recursion so much in the future. 

Second, accumulators are used when context needs to be preserved in some way within each iteration of the recursion.

Accumulator Types 

Context Preserving Accumulator
These guys keep track of some outside context to the prblem as you dig deeper into the recursion. It might be simply how many recusive calls you’ve made so far. But it could also be something like elements from the previous iteration’s call. The main difference between a Context Preserving Accumulator and the Result-so-Far accumulator is that the CPA doesn’t become the return value. Rather, it contributes to it.

Result-So-Far Accumulator
These keep a record of what would be the we need result of the function if you returned it before the recursion finished. Especially useful for tail recursion. An RSF accumulator needs an initial value and should be the same type of data as you want returned. In many ways, this simply moves the base case into the parameters of the function. 

Worklist Accumulator
This accumulator is used for navigating datasets that branch of in multiple directions, namely trees. Since a child node can’t reference or call on their “aunts and uncles” a work list saves the other side of a tree into a list which is eventually appended onto a leaf of the tree. This is efficient because it means we only have to visit reach node once, and is especially powerful with result so far accumulators. 

Tail Recursion

The classic downside of using recursion is that it you can end up with a huge amount of data sitting on the stack as each copy of the function waits for its recursive calls to resolve. This can be mitigated a little bit by making sure the recursive calls are in “tail position”. This means that no other function within the definition can be waiting on the recursive call to resolve. This means that we cannot add the result of a recursive call to something else, for example. It also means a recursive call cannot be the condition of an if statement, but it can be the result of one.

Tail recursion can be achieved by moving information operating on the recursive call to be inside the function’s parameters. An accumulator can pass the needed information along to the recursive call so that in the end, all the heavy lifting is done in the final call, and the first call effectively returns the same result as the last call.