В Kotlin ключевое слово tailrec используется для обозначения хвостовой рекурсии — особого вида рекурсивных вызовов, которые могут быть оптимизированы компилятором в итеративную конструкцию без использования стека вызовов. Это помогает избежать переполнения стека (StackOverflowError) и повышает производительность.

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

Хвостовая рекурсия (tail recursion) — это когда рекурсивный вызов происходит в самом конце функции, и его результат сразу возвращается без каких-либо дальнейших вычислений.

Пример:

fun factorial(n: Int): Int {
return if (n == 0) 1 else n \* factorial(n - 1)
}

Этот код не является хвостовой рекурсией, потому что после вызова factorial(n - 1) нужно ещё умножить на n, то есть рекурсивный вызов не последний.

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

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

Здесь:

• acc — аккумулятор, в котором сохраняется промежуточный результат.

• factorial(n - 1, acc * n) — последняя операция, и результат сразу возвращается.

Как работает tailrec

Если компилятор Kotlin определяет, что рекурсивный вызов действительно находится в хвостовой позиции (и нет ничего после него), он преобразует рекурсивный вызов в цикл. В результате:

• не создаётся новый стек вызовов;

• нет затрат на переход между функциями;

• устраняется риск StackOverflow.

Условия для использования tailrec

1. Функция должна вызывать себя рекурсивно.

2. Рекурсивный вызов должен быть последней инструкцией в функции.

3. Нельзя вызывать другие рекурсивные функции или использовать результат рекурсивного вызова в вычислениях.

4. Нельзя использовать try/catch/finally вокруг рекурсивного вызова.

5. Функция должна быть неанонимной, с фиксированной сигнатурой (не лямбда).

Если эти условия не выполнены, компилятор выдаст ошибку:
'tailrec' modifier is not applicable to this function.

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

tailrec fun sum(n: Int, acc: Int = 0): Int {
return if (n == 0) acc else sum(n - 1, acc + n)
}

Вызов: sum(1000000) отработает корректно, без переполнения стека.

Пример без tailrec, вызовет StackOverflow

fun sum(n: Int): Int {
return if (n == 0) 0 else n + sum(n - 1)
}

Вызов sum(1000000) приведёт к StackOverflow, потому что каждый вызов ждёт завершения предыдущего.

Пример — поиск в списке

tailrec fun findIndex(
list: List<String>,
target: String,
index: Int = 0
): Int {
if (index >= list.size) return -1
return if (list\[index\] == target) index else findIndex(list, target, index + 1)
}

Этот код безопасен для длинных списков, потому что findIndex — хвостовая функция, и каждый вызов преобразуется в итерацию.

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

tailrec fun countdown(n: Int) {
when {
n <= 0 -> println("Done!")
else -> {
println(n)
countdown(n - 1)
}
}
}

Функция также корректно хвостовая — countdown(n - 1) идёт в самом конце, после println(n).

Ограничения tailrec

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

• Не применяется для взаимной рекурсии (A вызывает B, B вызывает A).

• Нельзя использовать с анонимными функциями (лямбдами).

• Иногда лучше использовать while или for, если хвостовая рекурсия не даёт преимуществ читаемости.

Как проверить, что хвостовая рекурсия сработала

Kotlin компилирует хвостовую функцию в цикл. Чтобы проверить это:

• Скомпилируй код и декомпилируй .class файл через javap или посмотри байткод в IntelliJ IDEA.

• В байткоде не будет рекурсивного вызова, а будет goto.

Tail recursion vs обычный цикл

Иногда люди спрашивают, зачем нужна хвостовая рекурсия, если можно просто написать цикл. Ответ:

• Рекурсия часто проще читается в задачах с естественной рекурсивной структурой (например, дерево, список).

• tailrec позволяет сохранить декларативный стиль без риска переполнения стека.

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

Использование в функциональном стиле

В функциональных языках (Haskell, Scala) хвостовая рекурсия — норма. Kotlin, как мультипарадигменный язык, поддерживает её для удобства и оптимизации функциональных решений без необходимости вручную переписывать рекурсию в цикл.

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