Scala for Backend Engineering & Functional Programming · Урок

Шаблон аккумулятора

Преобразуйте функцию в хвостовую рекурсию

«Шаблон аккумулятора» — бесплатный урок Scala for Backend Engineering & Functional Programming на CoddyKit. Это урок 3 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Scala for Backend Engineering & Functional Programming, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Scala for Backend Engineering & Functional Programming содержит 4 уроков всего.

Шаблон аккумулятора

Шаблон аккумулятора преобразует функцию без хвостовой рекурсии в хвостовую рекурсивную. Частичный результат передаётся в дополнительном параметре (аккумуляторе), а не строится после возврата из вызова.

Основная идея

Вместо n + sum(n-1) (работы после вызова) вычислите новый частичный итог до вызова: sum(n-1, acc + n). Теперь рекурсивный вызов является последним действием.

До: сумма без хвостовой рекурсии

Эта прямая версия не является хвостовой рекурсией: сложение ожидает завершения рекурсивного вызова.

object Main {
  def sum(n: Int): Int =
    if (n == 0) 0 else n + sum(n - 1)

  def main(args: Array[String]): Unit = {
    println(sum(50))
  }
}

После: хвостовая сумма с аккумулятором

Добавьте параметр acc, содержащий текущий итог. Теперь рекурсивный вызов находится в хвостовой позиции и может быть оптимизирован.

import scala.annotation.tailrec

object Main {
  @tailrec
  def sum(n: Int, acc: Int = 0): Int =
    if (n == 0) acc else sum(n - 1, acc + n)

  def main(args: Array[String]): Unit = {
    println(sum(50))
  }
}

Хвостовая рекурсия для факториала

Примените то же преобразование к факториалу: умножайте значение на аккумулятор до выполнения рекурсивного вызова.

import scala.annotation.tailrec

object Main {
  @tailrec
  def factorial(n: Int, acc: Long = 1): Long =
    if (n <= 1) acc else factorial(n - 1, acc * n)

  def main(args: Array[String]): Unit = {
    println(factorial(10))
  }
}

Скрытие аккумулятора

Дополнительный параметр является деталью реализации. Оберните хвостовую рекурсивную вспомогательную функцию в понятную публичную функцию, чтобы вызывающим не приходилось видеть acc.

import scala.annotation.tailrec

object Main {
  def factorial(n: Int): Long = {
    @tailrec
    def loop(m: Int, acc: Long): Long =
      if (m <= 1) acc else loop(m - 1, acc * m)
    loop(n, 1)
  }

  def main(args: Array[String]): Unit = {
    println(factorial(6))
  }
}

Накопление списка

Этот шаблон также позволяет строить коллекции. Хвостовая рекурсивная функция reverse добавляет каждую голову в начало списка-аккумулятора.

import scala.annotation.tailrec

object Main {
  def reverse[A](xs: List[A]): List[A] = {
    @tailrec
    def loop(rem: List[A], acc: List[A]): List[A] = rem match {
      case Nil    => acc
      case h :: t => loop(t, h :: acc)
    }
    loop(xs, Nil)
  }

  def main(args: Array[String]): Unit = {
    println(reverse(List(1, 2, 3, 4)))
  }
}

Порядок накопления

Обратите внимание: добавление в начало аккумулятора естественным образом меняет порядок элементов на обратный. Если функция построения списка должна сохранять порядок, обычно сначала строят список в обратном порядке, а затем разворачивают его, либо используют эффективную структуру для добавления в конец.

Хвостовая рекурсия в map

Постройте результирующий список с помощью аккумулятора, а затем один раз разверните его в конце, чтобы восстановить порядок.

import scala.annotation.tailrec

object Main {
  def mapTail[A, B](xs: List[A])(f: A => B): List[B] = {
    @tailrec
    def loop(rem: List[A], acc: List[B]): List[B] = rem match {
      case Nil    => acc.reverse
      case h :: t => loop(t, f(h) :: acc)
    }
    loop(xs, Nil)
  }

  def main(args: Array[String]): Unit = {
    println(mapTail(List(1, 2, 3))(_ * 10))
  }
}

Связь с foldLeft

Шаблон аккумулятора — это в точности то, что обобщает foldLeft: он хвостовой рекурсией передаёт аккумулятор через коллекцию. Многие написанные вручную функции с аккумулятором можно переписать с помощью одного foldLeft.

@main def run(): Unit = {
  val total = List(1, 2, 3, 4).foldLeft(0)(_ + _)
  println(total)
}

Когда это использовать

Используйте шаблон аккумулятора, когда рекурсивная функция обрабатывает большую линейную структуру и в противном случае переполнила бы стек. За это приходится платить немного менее очевидной структурой, зато Вы получаете гарантированную безопасность стека.

Быстрая проверка

Проверьте, насколько хорошо Вы усвоили шаблон аккумулятора.

Итоги

Вы изучили шаблон аккумулятора:

Передавайте частичный результат в дополнительном параметре.
Вычисляйте его до рекурсивного вызова, чтобы достичь хвостовой позиции.
Скрывайте аккумулятор за понятной публичной функцией.
Этот шаблон обобщается в foldLeft.

Часто задаваемые вопросы

Урок «Шаблон аккумулятора» бесплатный?

Да — полный текст урока «Шаблон аккумулятора» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Scala for Backend Engineering & Functional Programming, подпишись на CoddyKit PRO. Курс Scala for Backend Engineering & Functional Programming содержит 4 уроков всего.

Чему я научусь в уроке «Шаблон аккумулятора»?

Преобразуйте функцию в хвостовую рекурсию Ты практикуешь Scala for Backend Engineering & Functional Programming с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.

Нужен ли мне опыт, чтобы начать Scala for Backend Engineering & Functional Programming?

Предыдущий опыт не требуется. Scala for Backend Engineering & Functional Programming на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 3 из 4.

Сколько времени занимает урок «Шаблон аккумулятора»?

Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.

Можно ли писать и запускать код в этом уроке Scala for Backend Engineering & Functional Programming?

Да. Каждый урок Scala for Backend Engineering & Functional Programming включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.

Все уроки этого курса

← Назад к Scala for Backend Engineering & Functional Programming