Course contentsShow
← Computer Science
Lesson 871 of 2,87220. Recursion Patterns and TechniquesFree lesson

Accumulator Pattern in Recursion

Use accumulator parameters to build up results during recursive descent, avoiding extra work on return.

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.