0Pricing
Scala for Backend Engineering & Functional Programming · Lesson

Accumulator Patterns

Carry state through recursion.

Accumulator Patterns is a free Scala for Backend Engineering & Functional Programming lesson on CoddyKit — lesson 2 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the Scala for Backend Engineering & Functional Programming learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.

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)
}

Running the Accumulator

Here the full program sums a list using an accumulator.

Notice the base case returns acc directly, not 0. The total has been built up as we descended through the 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)
}

@main def run(): Unit =
  println(sum(List(1, 2, 3, 4)))  // 10

Comparing the Two Shapes

In plain recursion the combine step (h + ...) waits for the inner call.

In the accumulator version the combine happens before the call, and the call is the very last thing the function does.

That last-call property is what makes it tail recursive.

// Plain: combine after the call
case h :: t => h + sum(t)

// Accumulator: combine before the call
case h :: t => loop(t, acc + h)

Tail Recursion

A tail-recursive call is one where the recursive call is the function's final action, with nothing left to do afterward.

Scala can optimize this into a loop, reusing a single stack frame, so it never overflows no matter how deep.

import scala.annotation.tailrec

@tailrec
def countDown(n: Int): Unit =
  if (n < 0) ()
  else { println(n); countDown(n - 1) }

The @tailrec Annotation

Adding @tailrec asks the compiler to verify the function really is tail recursive.

If it is not, compilation fails with a clear error. This turns a silent performance trap into a build-time guarantee.

import scala.annotation.tailrec

def sum(xs: List[Int]): Int = {
  @tailrec
  def loop(rest: List[Int], acc: Int): Int = rest match {
    case Nil    => acc
    case h :: t => loop(t, acc + h)
  }
  loop(xs, 0)
}

@main def run(): Unit = println(sum((1 to 100000).toList))

Accumulating a List

Accumulators do not have to hold numbers. They can build collections too.

This reverse function prepends each head onto the accumulator, which naturally flips the order. Prepending with :: is fast, so this is efficient.

def reverse[A](xs: List[A]): List[A] = {
  def loop(rest: List[A], acc: List[A]): List[A] = rest match {
    case Nil    => acc
    case h :: t => loop(t, h :: acc)
  }
  loop(xs, Nil)
}

Reverse in Action

The accumulator starts empty and grows as we consume the input.

Because each head is pushed onto the front of acc, the first element ends up last, giving a reversed list at constant stack cost.

def reverse[A](xs: List[A]): List[A] = {
  def loop(rest: List[A], acc: List[A]): List[A] = rest match {
    case Nil    => acc
    case h :: t => loop(t, h :: acc)
  }
  loop(xs, Nil)
}

@main def run(): Unit =
  println(reverse(List(1, 2, 3)))  // List(3, 2, 1)

Multiple Accumulators

A helper can carry several accumulators at once.

Here we track a running product and a count in the same loop, returning both as a tuple.

Each one threads its updated value into the next call.

def stats(xs: List[Int]): (Int, Int) = {
  def loop(rest: List[Int], prod: Int, count: Int): (Int, Int) =
    rest match {
      case Nil    => (prod, count)
      case h :: t => loop(t, prod * h, count + 1)
    }
  loop(xs, 1, 0)
}

Choosing the Initial Value

The starting accumulator must be the identity for your operation.

For addition use 0, for multiplication use 1, for list building use Nil, for string joining use the empty string.

A wrong seed quietly produces wrong answers.

// addition  -> seed 0
// product   -> seed 1
// list      -> seed Nil
// string    -> seed ""

Order of Results

Accumulator recursion processes elements left to right, but a prepend-based accumulator reverses them.

If you need to preserve order while building a list, either reverse at the end or append, though appending is slower. Prepend-then-reverse is the usual idiom.

def mapInc(xs: List[Int]): List[Int] = {
  def loop(rest: List[Int], acc: List[Int]): List[Int] = rest match {
    case Nil    => acc.reverse
    case h :: t => loop(t, (h + 1) :: acc)
  }
  loop(xs, Nil)
}

Quick Check

Pick the accurate statement about accumulator recursion.

Recap

An accumulator threads the running result down through recursive calls, so the base case can return it directly.

This makes the recursive call sit in tail position, enabling Scala's tail-call optimization and @tailrec safety check.

Seed the accumulator with the operation's identity value, and reverse at the end when order matters.

Frequently asked questions

Is the “Accumulator Patterns” lesson free?

Yes — the full text of “Accumulator Patterns” is free to read here on the web, and the Scala for Backend Engineering & Functional Programming course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the Scala for Backend Engineering & Functional Programming course, upgrade to CoddyKit PRO.

What will I learn in “Accumulator Patterns”?

Carry state through recursion. You practise Scala for Backend Engineering & Functional Programming with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.

Do I need any experience to start Scala for Backend Engineering & Functional Programming?

No prior experience is required. Scala for Backend Engineering & Functional Programming on CoddyKit is structured for beginners through advanced learners; this is — lesson 2 of 4, so you can start here or from the beginning and move at your own pace.

How long does the “Accumulator Patterns” lesson take?

Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.

Can I write and run code in this Scala for Backend Engineering & Functional Programming lesson?

Yes. Every Scala for Backend Engineering & Functional Programming lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.

All lessons in this course

  1. Thinking Recursively
  2. Accumulator Patterns
  3. foldLeft and foldRight
  4. reduce and aggregate
← Back to Scala for Backend Engineering & Functional Programming