Что такое функция с хвостовой рекурсией и как она работает в языке Kotlin?

Функция с хвостовой рекурсией — это функция, в которой рекурсивный вызов является последним действием перед возвратом значения.

Особенности и принцип работы в Kotlin:

1. Аннотация tailrec: Kotlin требует явной аннотации @tailrec для функций, которые должны быть оптимизированы с помощью хвостовой рекурсии.
2. Оптимизация компилятором: Если функция аннотирована как tailrec и соответствует критериям хвостовой рекурсии (рекурсивный вызов — последнее действие, результат вызова не используется в других вычислениях), компилятор оптимизирует ее.
3. Трансформация в цикл: Оптимизация заключается в трансформации рекурсивного вызова в обычный цикл while. Это позволяет избежать роста стека вызовов и, как следствие, предотвращает переполнение стека при большом количестве рекурсивных вызовов.
4. Предотвращение StackOverflowError: Основное преимущество — возможность эффективно работать с глубокими рекурсивными вызовами, не опасаясь исключения StackOverflowError.

Пример:

// Неоптимизированная рекурсия - может вызвать StackOverflowError для больших N
fun factorialRecursive(n: Long): Long {
    return if (n <= 1) 1 else n * factorialRecursive(n - 1)
}

// Функция с хвостовой рекурсией
tailrec fun factorialTailrec(n: Long, accumulator: Long = 1): Long {
    return if (n <= 1) accumulator else factorialTailrec(n - 1, n * accumulator)
}

fun main() {
    println(factorialTailrec(5)) // Выведет 120
}