Accumulator Patterns
Carry state through recursion.
Why Accumulators
Plain recursion builds its result on the way back up the call stack, after the recursive call returns.
An accumulator carries a running result down into each call instead, so the answer is ready when the base case is reached.
This small shift unlocks tail recursion and constant stack usage.
The Helper Function
The accumulator pattern uses an inner helper that takes an extra parameter: the result so far.
The outer function just kicks it off with a starting value, often 0 or an empty list.
def sum(xs: List[Int]): Int = {
def loop(rest: List[Int], acc: Int): Int = rest match {
case Nil => acc
case h :: t => loop(t, acc + h)
}
loop(xs, 0)
}All lessons in this course
- Thinking Recursively
- Accumulator Patterns
- foldLeft and foldRight
- reduce and aggregate