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

Аннотация tailrec

Гарантированная оптимизация

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

Что такое хвостовая рекурсия

Рекурсивный вызов находится в хвостовой позиции, если он является последним действием функции. Хвостовую рекурсивную функцию можно оптимизировать до цикла с повторным использованием одного кадра стека, поэтому переполнения не произойдёт.

Хвостовая позиция

В выражении n * factorial(n-1) рекурсивный вызов не является последним: после его возврата выполняется умножение. В выражении gcd(b, a % b) вызов является последним. Только второй вариант является хвостовой рекурсией.

Аннотация @tailrec

Импортируйте scala.annotation.tailrec и аннотируйте метод. Затем компилятор проверит, действительно ли вызов находится в хвостовой позиции, и применит оптимизацию. Если это не так, компиляция завершится ошибкой.

import scala.annotation.tailrec

object Main {
  @tailrec
  def countdown(n: Int): Unit = {
    if (n >= 0) {
      println(n)
      countdown(n - 1)
    }
  }

  def main(args: Array[String]): Unit = countdown(3)
}

Гарантированная оптимизация

Главное преимущество @tailrec — гарантия во время компиляции. Вы сразу узнаете, что функция небезопасна для стека, вместо того чтобы обнаружить это по сбою во время выполнения на больших входных данных.

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

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

import scala.annotation.tailrec

object Main {
  @tailrec
  def gcd(a: Int, b: Int): Int =
    if (b == 0) a else gcd(b, a % b)

  def main(args: Array[String]): Unit = {
    println(gcd(1071, 462))
  }
}

Что нарушает хвостовую позицию

Распространённые конструкции, выводящие вызов из хвостовой позиции:

Выполнение арифметики над результатом: n + f(...).
Обертывание в конструктор: x :: f(...).
Использование результата в блоке try.

Пример без хвостовой рекурсии

Эта сумма не является хвостовой рекурсией, потому что сложение оборачивает вызов. Аннотация @tailrec вызвала бы ошибку компиляции. (Здесь она не указана, поэтому пример выполняется.)

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

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

Почему оптимизация невозможна

Выражение n + sum(n - 1) должно сохранить n, чтобы завершить сложение после возврата из вызова, поэтому каждому уровню нужен собственный кадр стека. Компилятор не может преобразовать это в цикл, поэтому такая функция не является хвостовой рекурсией.

Большой хвостовой рекурсивный цикл

Хвостовая рекурсивная сумма с аккумулятором работает для огромных входных данных без переполнения, потому что повторно использует один кадр.

import scala.annotation.tailrec

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

  def main(args: Array[String]): Unit = {
    println(sumTo(1000000))
  }
}

Для tailrec нужен final или локальный метод

Чтобы применить @tailrec, метод не должен допускать переопределение: он должен быть private, final или локальным/вложенным методом. Открытый метод можно переопределить, что нарушило бы оптимизацию, поэтому компилятор отклоняет его.

Ограничение взаимной рекурсии

@tailrec оптимизирует только функцию, вызывающую саму себя. Две функции, вызывающие друг друга (взаимная рекурсия), не могут быть напрямую оптимизированы JVM для хвостовых вызовов; для этого нужна трамплинная рекурсия, которую мы рассмотрим позже.

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

Проверьте, насколько хорошо Вы поняли принцип работы @tailrec.

Итоги

Вы изучили аннотацию @tailrec:

Вызов в хвостовой позиции можно оптимизировать до цикла.
@tailrec даёт гарантию безопасности стека во время компиляции.
Метод должен быть final, private или локальным.
Аннотация применима только к рекурсии с вызовом самой себя, но не к взаимной рекурсии.

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

Урок «Аннотация tailrec» бесплатный?

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

Чему я научусь в уроке «Аннотация tailrec»?

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

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

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

Сколько времени занимает урок «Аннотация tailrec»?

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

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

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

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

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