1. Введение
Некоторые алгоритмы работают лучше всего, когда реализованы рекурсивным способом – когда вычисления основаны на более простой форме того же вычисления.
В большинстве языков программирования существует риск переполнения стека, связанный с рекурсией. Существует ограничение на количество вызовов вложенных методов, которые могут быть выполнены за один раз, без возврата.
Если это проблема, алгоритм можно переписать императивным образом, используя вместо этого традиционный цикл. Хвостовая рекурсия - это метод, при котором компилятор может переписать рекурсивный метод императивным образом, предполагая, что соблюдаются определенные правила.
2. Правила для хвостовой рекурсии в Kotlin
Чтобы реализовать функцию в Kotlin с использованием хвостовой рекурсии, необходимо следовать одному правилу: рекурсивный вызов должен быть самым последним вызовом метода.
Следовать этому правилу не так просто, как кажется. Например, в примере с факториалом это было бы реализовано следующим образом:
fun recursiveFactorial(n: Long) : Long {
return if (n <= 1) {
n
} else {
n * recursiveFactorial(n - 1)
}
}
Это работает отлично. Однако, это не подходит для хвостовой рекурсии.
В разбивке приведенная выше функция выполняет следующее:
- If n is <= 1 then return n
- Calculate accum = recursiveFactorial(n – 1)
- return n * accum
Написанный таким образом, вы можете видеть, что рекурсивный вызов не является последним вызовом функции.
3. Реализация факториала в виде хвостовой рекурсии
Вместо этого, чтобы реализовать факториальную функцию с использованием хвостовой рекурсии, нам нужно переработать ее, чтобы изменить место выполнения вычисления. Нам нужно убедиться, что умножение выполняется до рекурсивного вызова, а не после. Это проще всего сделать, передав частичный результат в качестве параметра:
fun factorial(n: Long, accum: Long = 1): Long {
val soFar = n * accum
return if (n <= 1) {
soFar
} else {
factorial(n - 1, soFar)
}
}
Это можно разделить на следующие:
- Calculate soFar = n * accum
- If n <= 1 then return soFar
- Call the factorial function, passing in n – 1 and soFar
На этот раз рекурсивный вызов является последним шагом в нашем процессе.
Как только у нас есть рекурсивная функция, имеющая правильную форму, мы даем команду Kotlin рассмотреть ее для хвостовой рекурсии, используя ключевое слово tailrec. Это информирует компилятор о том, что ему разрешено переписать функцию как цикл, если он может это сделать. Это ключевое слово применяется к самой функции, поэтому становится:
tailrec fun factorial(n: Long, accum: Long = 1): Long
4. Выходные данные компиляции факториала
Цель этого - написать рекурсивный код, который запускается императивным образом, чтобы избежать проблем с переполнением стека. Если мы декомпилируем вышеуказанную функцию, мы увидим, что результат, полученный компилятором, действительно является императивным:
public final long factorial(long n, long accum) {
while(n > (long) 1) {
long var10000 = n - (long)1;
accum = n * accum;
n = var10000;
}
return n * accum;
}
Мы можем сразу увидеть, как это работает, и заметить, что в этом коде нет абсолютно никакого риска переполнения стека.
5. Повышение производительности
Иногда мы можем наблюдать повышение производительности с помощью этой оптимизации, а также повышение безопасности. Эти преимущества зависят от некоторых других факторов, таких как глубина рекурсии и сложность вычислений.
Улучшения связаны с тем фактом, что вызовы методов обходятся дороже, чем простое выполнение цикла.
Снова используя наш факторный пример, мы можем измерить, сколько времени требуется для выполнения, и сравнить:
- Вычисление факториала(50) 1 000 000 раз без хвостовой рекурсии занимает ~70 мс
- Вычисление факториала(50) 1 000 000 раз с хвостовой рекурсией занимает ~45 мс
Используя наивный бенчмарк, мы получили ускорение на 36%, что значительно только потому, что позволяет компилятору переработать нашу реализацию.
Обратите внимание, что эти измерения получены в результате очень простого бенчмаркинга простой функции. Фактические изменения производительности будут варьироваться в зависимости от обстоятельств, и их всегда следует измерять, прежде чем принимать какие-либо решения.
6. Завершение
В некоторых сценариях хвостовая рекурсия может дать некоторые важные преимущества нашему коду – как в отношении безопасности, так и производительности. Компилятор Kotlin может делать это автоматически – нам просто нужно использовать правильное ключевое слово.
Оригинал статьи: https://www.baeldung.com/kotlin/tail-recursion