Трамплининг
Рекурсия без переполнения стека
«Трамплининг» — бесплатный урок Scala for Backend Engineering & Functional Programming на CoddyKit. Это урок 4 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Scala for Backend Engineering & Functional Programming, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Scala for Backend Engineering & Functional Programming содержит 4 уроков всего.
Ограничение @tailrec
@tailrec оптимизирует только функцию, напрямую вызывающую саму себя. Она не помогает при взаимной рекурсии (две функции вызывают друг друга), которая по-прежнему наращивает стек. Эту проблему решает трамплинная рекурсия.
Проблема взаимной рекурсии
Рассмотрим isEven и isOdd, определённые через друг друга. Для большого числа это приводит к переполнению стека, и ни одну из функций нельзя пометить как @tailrec.
object Main {
def isEven(n: Int): Boolean = if (n == 0) true else isOdd(n - 1)
def isOdd(n: Int): Boolean = if (n == 0) false else isEven(n - 1)
def main(args: Array[String]): Unit = {
println(isEven(10))
}
}Что такое трамплинная рекурсия
Трамплинная рекурсия превращает рекурсивные вызовы в данные. Вместо вызова самой себя функция возвращает описание следующего шага. Управляющий цикл многократно выполняет эти шаги, сохраняя стек неизменным.
TailRec в стандартной библиотеке
Scala предоставляет scala.util.control.TailCalls с типом TailRec. Используйте done(x) для окончательного результата и tailcall(...), чтобы отложить следующий вызов.
import scala.util.control.TailCalls._
object Main {
def isEven(n: Int): TailRec[Boolean] =
if (n == 0) done(true) else tailcall(isOdd(n - 1))
def isOdd(n: Int): TailRec[Boolean] =
if (n == 0) done(false) else tailcall(isEven(n - 1))
def main(args: Array[String]): Unit = {
println(isEven(100000).result)
}
}done и tailcall
Два строительных блока:
done(value)оборачивает окончательный ответ.tailcall(expr)откладывает вызов, возвращающийTailRec.
Вызов .result запускает трамплинный цикл и выдаёт значение.
Безопасность стека
Поскольку каждый tailcall передаёт управление управляющему циклу, а не вкладывает вызов Java, стек JVM не растёт вместе с глубиной рекурсии. Пример выше обрабатывает 100 000 шагов без переполнения.
Трамплинная рекурсия с вызовом самой себя
Трамплинная рекурсия подходит и для обычной глубокой рекурсии с вызовом самой себя, когда аккумулятор использовать непросто. Здесь глубокий обратный отсчёт остаётся безопасным для стека.
import scala.util.control.TailCalls._
object Main {
def countDown(n: Int): TailRec[Int] =
if (n == 0) done(0) else tailcall(countDown(n - 1))
def main(args: Array[String]): Unit = {
println(countDown(500000).result)
}
}Объединение результатов с flatMap
TailRec поддерживает map и flatMap, поэтому Вы можете выполнять работу после отложенного вызова, сохраняя безопасность стека.
import scala.util.control.TailCalls._
object Main {
def sum(n: Int): TailRec[Int] =
if (n == 0) done(0)
else tailcall(sum(n - 1)).map(_ + n)
def main(args: Array[String]): Unit = {
println(sum(100000).result)
}
}Как работает управляющий цикл
Концептуально .result запускает цикл: получает текущий шаг; если это done, возвращает его значение; если это отложенный вызов, вычисляет один уровень и продолжает работу. Всё это выполняется с постоянным объёмом стека.
Трамплинная рекурсия в библиотеках эффектов
Библиотеки вроде Cats Effect и ZIO внутренне используют трамплинную рекурсию для своих цепочек flatMap, поэтому Вы можете строить глубоко вложенные программы эффектов без переполнения стека. Трамплинная рекурсия — основа безопасных для стека функциональных эффектов.
Когда использовать трамплинную рекурсию
Используйте трамплин, когда:
- У Вас есть взаимная рекурсия, которую нельзя свести к одной хвостовой рекурсивной функции.
- Рекурсия слишком глубокая для стека, а аккумулятор здесь неприменим.
Для простой рекурсии функции на себя сначала предпочитайте @tailrec с аккумулятором.
Быстрая проверка
Проверьте, насколько хорошо Вы поняли работу трамплина.
Итоги
Вы изучили трамплинирование:
- Оно делает взаимную и очень глубокую рекурсию безопасной для стека.
- Используйте
TailCalls:done(x)иtailcall(...), затем.result. TailRecподдерживаетmap/flatMap.- Оно лежит в основе библиотек эффектов, безопасных для стека.
Часто задаваемые вопросы
Урок «Трамплининг» бесплатный?
Да — полный текст урока «Трамплининг» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 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 структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 4 из 4.
Сколько времени занимает урок «Трамплининг»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке Scala for Backend Engineering & Functional Programming?
Да. Каждый урок Scala for Backend Engineering & Functional Programming включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.