Ответ.

История вопроса

Рекурсия — полезная техника, встречающаяся в функциональных языках и в Kotlin. Однако прямая рекурсия часто приводит к переполнению стека (StackOverflowError). Для борьбы с этим во многих языках введена оптимизация хвостовой рекурсии (tail call optimization). В Kotlin она реализована явно через ключевое слово tailrec.

Проблема

Обычная рекурсия создаёт новые кадры стека при каждом вызове. Когда глубина рекурсии большая, это приводит к StackOverflowError. Автоматическая оптимизация хвостовой рекурсии возможна не всегда, и JVM её не поддерживает как, например, компиляторы некоторых других языков (Scala, Erlang).

Решение

Kotlin позволяет пометить функцию ключевым словом tailrec. Если функция действительно является хвостовой рекурсией ("tail call" — результирующий вызов самой себя является финальной операцией), компилятор заменяет её на цикл, что убирает переполнение стека.

Пример кода:

tailrec fun factorial(n: Int, acc: Int = 1): Int =
    if (n == 0) acc else factorial(n - 1, acc * n)

println(factorial(5)) // 120

Ключевые особенности:

Функция должна быть рекурсивной, последний оператор — это вызов самой себя
tailrec может применяться только к функциям, не являющимся open или абстрактными
Есть ограничения: например, нельзя использовать внутри лямбд или когда непосредственный tail call затенён другими операциями

Вопросы с подвохом.

Что произойдет, если tailrec стоит, но вызов не находится в хвостовой позиции?

Компилятор выдаст ошибку и не применит оптимизацию.

tailrec fun sum(n: Int, acc: Int = 0): Int {
    println(n) // после этого нельзя оптимизировать
    return if (n == 0) acc else sum(n - 1, acc + n)
}
// Ошибка компиляции: вызов не в хвостовой позиции

Можно ли использовать tailrec в open-функциях или абстрактных методах?

Нет, ключевое слово работает только на final-функциях.

open class Base {
    // Ошибка:
    // tailrec open fun test() {}
}

Есть ли разница в производительности между обычной рекурсией и tailrec?

Да, tailrec преобразует функцию в цикл, уменьшая затраты на стек и устраняя StackOverflowError.

Типовые ошибки и анти-паттерны

Ошибочное использование tailrec в не хвостовой позиции, что приводит к ошибке компиляции
Попытка использовать tailrec для лямбд или функций с нестандартной структурой return
Применение tailrec там, где рекурсия тривиальна и проще заменить на обычный цикл

Пример из жизни

Негативный кейс

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

Плюсы:

Желание сделать код оптимальным Минусы:
Компиляция прерывается, логика поломана, рекурсивные вызовы могут не работать

Позитивный кейс

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