Accumulator Pattern in Recursion
You'll learn how to use accumulator parameters to collect results as you descend recursively, avoiding inefficient work during the return journey.
The Problem with Building Results on Return
When writing recursive functions, a common approach is to make recursive calls, then build up the final result as those calls return. This can be inefficient—you're doing work on every level of the call stack as it unwinds.
What is an Accumulator?
An accumulator is an extra parameter you add to your recursive function that carries partial results downward through the recursion. Instead of computing the result on the way back up, you compute it on the way down and pass it along.
Think of it like filling a bucket as you walk down stairs, rather than carrying empty buckets down and filling them all on your way back up.
How It Works
Instead of:
- Recurse with smaller problem
- Get answer back
- Do work to combine answer
You:
- Do work to update accumulator
- Recurse with smaller problem and updated accumulator
- Base case returns the accumulator
The accumulator "accumulates" the answer as you go, so when you hit the base case, you're already done!
Example: Reversing a List
Without accumulator (builds result on return):
- Recurse to end, then prepend each element coming back
With accumulator (builds result going down):
- Start with empty result accumulator
- At each step, add current element to accumulator and recurse with remainder
- Base case returns the accumulator
The accumulator version avoids rebuilding intermediate results and often enables tail-call optimization.
Key Takeaway: Accumulator parameters let you build your result during recursion descent rather than on return, making your recursive solution more efficient and often enabling tail-call optimization.