В этой статье вы научитесь создавать рекурсивные функции; функция, которая вызывает сама себя. Также вы узнаете о хвостовой рекурсивной функции.
Функция, которая вызывает сама себя, называется рекурсивной функцией. И этот метод известен как рекурсия.
В качестве примера физического мира можно поместить два параллельных зеркала, обращенных друг к другу. Любой объект между ними будет отражаться рекурсивно.
Как работает рекурсия в программировании?
fun main (args: Array) (… recurse ()…) fun recurse () (… recurse ()…)
Здесь recurse()функция вызывается из тела самой recurse()функции. Вот как работает эта программа:
Здесь рекурсивный вызов продолжается вечно, вызывая бесконечную рекурсию.
Чтобы избежать бесконечной рекурсии, можно использовать if… else (или аналогичный подход), когда одна ветвь выполняет рекурсивный вызов, а другая - нет.
Пример: найти факториал числа с помощью рекурсии
fun main(args: Array) ( val number = 4 val result: Long result = factorial(number) println("Factorial of $number = $result") ) fun factorial(n: Int): Long ( return if (n == 1) n.toLong() else n*factorial(n-1) )
Когда вы запустите программу, вывод будет:
Факториал 4 = 24
Как работает эта программа?
Рекурсивный вызов factorial()функции можно пояснить на следующем рисунке:
Вот шаги:
factorial (4) // 1-й вызов функции. Аргумент: 4 4 * factorial (3) // 2-й вызов функции. Аргумент: 3 4 * (3 * factorial (2)) // вызов третьей функции. Аргумент: 2 4 * (3 * (2 * factorial (1))) // 4-й вызов функции. Аргумент: 1 4 * (3 * (2 * 1)) 24
Котлин хвостовая рекурсия
Рекурсия хвоста - это общее понятие, а не особенность языка Kotlin. Некоторые языки программирования, включая Kotlin, используют его для оптимизации рекурсивных вызовов, тогда как другие языки (например, Python) их не поддерживают.
Что такое хвостовая рекурсия?
В обычной рекурсии вы сначала выполняете все рекурсивные вызовы и, наконец, вычисляете результат по возвращаемым значениям (как показано в приведенном выше примере). Следовательно, вы не получите результата, пока не будут выполнены все рекурсивные вызовы.
В хвостовой рекурсии сначала выполняются вычисления, затем выполняются рекурсивные вызовы (рекурсивный вызов передает результат вашего текущего шага следующему рекурсивному вызову). Это делает рекурсивный вызов эквивалентным циклу и позволяет избежать риска переполнения стека.
Условие хвостовой рекурсии
Рекурсивная функция имеет право на хвостовую рекурсию, если вызов функции является последней выполняемой операцией. Например,
Пример 1: Не подходит для хвостовой рекурсии, потому что вызов функции n*factorial(n-1)не является последней операцией.
забавный факториал (n: Int): Long (if (n == 1) (return n.toLong ()) else (return n * factorial (n - 1)))
Пример 2: Подходит для хвостовой рекурсии, потому что вызов функции fibonacci(n-1, a+b, a)является последней операцией.
fun fibonacci (n: Int, a: Long, b: Long): Long (return if (n == 0) b else fibonacci (n-1, a + b, a))
Чтобы компилятор выполнял хвостовую рекурсию в Kotlin, вам нужно пометить функцию tailrecмодификатором.
Пример: хвостовая рекурсия
import java.math.BigInteger fun main(args: Array) ( val n = 100 val first = BigInteger("0") val second = BigInteger("1") println(fibonacci(n, first, second)) ) tailrec fun fibonacci(n: Int, a: BigInteger, b: BigInteger): BigInteger ( return if (n == 0) a else fibonacci(n-1, b, a+b) )
Когда вы запустите программу, вывод будет:
354224848179261915075
Эта программа вычисляет сотый член ряда Фибоначчи. Поскольку на выходе может быть очень большое целое число, мы импортировали класс BigInteger из стандартной библиотеки Java.
Здесь функция fibonacci()отмечена tailrecмодификатором, и функция имеет право на хвостовой рекурсивный вызов. Следовательно, в этом случае компилятор оптимизирует рекурсию.
Если вы попытаетесь найти 20000- й член (или любое другое большое целое число) ряда Фибоначчи без использования хвостовой рекурсии, компилятор выдаст java.lang.StackOverflowErrorисключение. Однако наша программа выше работает нормально. Это потому, что мы использовали хвостовую рекурсию, которая использует эффективную версию на основе цикла вместо традиционной рекурсии.
Пример: факториал с использованием хвостовой рекурсии
Пример вычисления факториала числа в приведенном выше примере (первый пример) не может быть оптимизирован для хвостовой рекурсии. Вот другая программа для выполнения той же задачи.
fun main(args: Array) ( val number = 5 println("Factorial of $number = $(factorial(number))") ) tailrec fun factorial(n: Int, run: Int = 1): Long ( return if (n == 1) run.toLong() else factorial(n-1, run*n) )
Когда вы запустите программу, вывод будет:
Факториал 5 = 120
Компилятор может оптимизировать рекурсию в этой программе, поскольку рекурсивная функция имеет право на хвостовую рекурсию, и мы использовали tailrecмодификатор, который сообщает компилятору об оптимизации рекурсии.
