Функции tailrec
Оптимизируйте рекурсию
«Функции tailrec» — бесплатный урок Kotlin Academy на CoddyKit. Это урок 3 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Kotlin Academy, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Kotlin Academy содержит 4 уроков всего.
Что такое хвостовая рекурсия
Функция является хвостовой рекурсивной, если её рекурсивный вызов выполняется последним. Тогда Kotlin может преобразовать его в цикл, предотвращая переполнение стека.
tailrec fun countdown(n: Int) {
if (n < 0) return
println(n)
countdown(n - 1)
}
fun main() {
countdown(3)
}Модификатор хвостовой рекурсии
Добавьте модификатор tailrec, и компилятор перепишет рекурсию в итерацию, используя постоянный объём памяти стека.
tailrec fun sum(n: Int, acc: Int = 0): Int {
if (n == 0) return acc
return sum(n - 1, acc + n)
}
fun main() {
println(sum(100))
}Шаблон Accumulator
Чтобы привести рекурсию к хвостовой форме, передавайте результаты в параметре Accumulator, чтобы после вызова не оставалось вычислений.
tailrec fun factorial(n: Int, acc: Long = 1): Long {
if (n <= 1) return acc
return factorial(n - 1, acc * n)
}
fun main() {
println(factorial(10))
}Почему вызов должен быть последним
Если после рекурсивного вызова выполняется какое-либо действие, например умножение его результата, вызов не находится в хвостовой позиции и не может быть оптимизирован.
tailrec fun length(s: String, acc: Int = 0): Int {
if (s.isEmpty()) return acc
return length(s.drop(1), acc + 1)
}
fun main() {
println(length("hello"))
}Контрпример рекурсии без хвостовой позиции
Эта функция вычисления факториала НЕ является хвостовой рекурсивной, потому что умножение выполняется после возврата из вызова. Пометка tailrec вызвала бы предупреждение.
fun badFactorial(n: Int): Long {
if (n <= 1) return 1
return n * badFactorial(n - 1)
}
fun main() {
println(badFactorial(5))
}Предотвращение переполнения стека
Глубокая рекурсия без tailrec может привести к сбою. С этим модификатором даже большие входные данные обрабатываются при постоянном объёме стека.
tailrec fun count(n: Int, acc: Int = 0): Int {
if (n == 0) return acc
return count(n - 1, acc + 1)
}
fun main() {
println(count(100000))
}Проверка компилятором
Если пометить функцию как tailrec, но вызов не находится в хвостовой позиции, компилятор выдаст предупреждение и не выполнит оптимизацию. Учитывайте это предупреждение.
tailrec fun gcd(a: Int, b: Int): Int {
if (b == 0) return a
return gcd(b, a % b)
}
fun main() {
println(gcd(48, 18))
}Хвостовая рекурсия и цикл
Функция с модификатором tailrec компилируется примерно в тот же код, что и эквивалентный цикл, но описывает алгоритм рекурсивно.
tailrec fun powerOfTwo(n: Int, acc: Long = 1): Long {
if (n == 0) return acc
return powerOfTwo(n - 1, acc * 2)
}
fun main() {
println(powerOfTwo(10))
}Несколько параметров
Хвостовые рекурсивные функции часто передают несколько параметров состояния, обновляя их при рекурсивном вызове.
tailrec fun fib(n: Int, a: Long = 0, b: Long = 1): Long {
if (n == 0) return a
return fib(n - 1, b, a + b)
}
fun main() {
println(fib(20))
}Разворот с помощью tailrec
С помощью Accumulator можно накапливать результат, например перевёрнутую строку.
tailrec fun reverse(s: String, acc: String = ""): String {
if (s.isEmpty()) return acc
return reverse(s.drop(1), s.first() + acc)
}
fun main() {
println(reverse("kotlin"))
}Практический поиск
Итеративные алгоритмы поиска легко выразить с помощью хвостовой рекурсии.
tailrec fun indexOf(list: List<Int>, target: Int, i: Int = 0): Int {
if (i >= list.size) return -1
if (list[i] == target) return i
return indexOf(list, target, i + 1)
}
fun main() {
println(indexOf(listOf(5, 6, 7), 7))
}Быстрая проверка
Проверьте, насколько хорошо Вы поняли функции с модификатором tailrec.
Итоги
Вы изучили функции с модификатором tailrec:
tailrecпреобразует рекурсию в хвостовой позиции в цикл, предотвращая переполнение стека.- Рекурсивный вызов должен быть последней операцией.
- Используйте параметр Accumulator, чтобы привести функцию к хвостовой форме.
- Компилятор предупреждает, если функцию нельзя оптимизировать.
tailrec fun sum(n: Int, acc: Int = 0): Int =
if (n == 0) acc else sum(n - 1, acc + n)
fun main() {
println(sum(50))
}
Изучай Kotlin с ИИ-репетитором — бесплатно
Пиши и запускай код прямо в браузере, получай мгновенную помощь от ИИ-репетитора 24/7 и продолжи учиться на сайте или в приложении.
- Курсы
- 51
- Уроки
- 203
Часто задаваемые вопросы
Урок «Функции tailrec» бесплатный?
Да — полный текст урока «Функции tailrec» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Kotlin Academy, подпишись на CoddyKit PRO. Курс Kotlin Academy содержит 4 уроков всего.
Чему я научусь в уроке «Функции tailrec»?
Оптимизируйте рекурсию Ты практикуешь Kotlin Academy с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать Kotlin Academy?
Предыдущий опыт не требуется. Kotlin Academy на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 3 из 4.
Сколько времени занимает урок «Функции tailrec»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке Kotlin Academy?
Да. Каждый урок Kotlin Academy включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.