У цій статті ви навчитеся створювати рекурсивні функції; функція, яка викликає себе. Крім того, ви дізнаєтесь про рекурсивну функцію хвоста.
Функція, яка викликає себе, відома як рекурсивна функція. І ця методика відома як рекурсія.
Прикладом фізичного світу може бути розміщення двох паралельних дзеркал один напроти одного. Будь-який об'єкт між ними буде відображатися рекурсивно.
Як працює рекурсія в програмуванні?
fun main (args: Array) (… repeatse ()…) fun rekurse () (… repeatse ()…)
Тут recurse()функція викликається із самого тіла recurse()функції. Ось як працює ця програма:
Тут рекурсивний дзвінок продовжується назавжди, викликаючи нескінченну рекурсію.
Щоб уникнути нескінченної рекурсії, якщо … може бути використано інше (або подібний підхід), коли одна гілка робить рекурсивний виклик, а інша - ні.
Приклад: Знайти факторіал числа за допомогою рекурсії
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()функції можна пояснити на наступному малюнку:
Ось такі кроки:
факторіал (4) // 1-й виклик функції. Аргумент: 4 4 * факторіал (3) // 2-й виклик функції. Аргумент: 3 4 * (3 * факторіал (2)) // 3-й виклик функції. Аргумент: 2 4 * (3 * (2 * факторіал (1))) // 4-й виклик функції. Аргумент: 1 4 * (3 * (2 * 1)) 24
Рекурсія хвоста Котліна
Рекурсія хвоста - це загальне поняття, а не особливість мови Котліна. Деякі мови програмування, включаючи Kotlin, використовують його для оптимізації рекурсивних викликів, тоді як інші мови (наприклад, Python) їх не підтримують.
Що таке рекурсія хвоста?
У звичайній рекурсії ви спочатку виконуєте всі рекурсивні виклики, а результат обчислюєте з повернутих значень нарешті (як показано у наведеному вище прикладі). Отже, ви не отримаєте результату, доки не будуть зроблені всі рекурсивні дзвінки.
У хвостовій рекурсії спочатку виконуються обчислення, потім виконуються рекурсивні виклики (рекурсивний виклик передає результат вашого поточного кроку до наступного рекурсивного виклику). Це робить рекурсивний виклик еквівалентним циклу та уникає ризику переповнення стека.
Умова рекурсії хвоста
Рекурсивна функція придатна для рекурсії хвоста, якщо виклик функції сам є останньою операцією, яку вона виконує. Наприклад,
Приклад 1: Непридатне для рекурсії хвоста, оскільки виклик функції до себе n*factorial(n-1)не є останньою операцією.
fun factorial (n: Int): Long (if (n == 1) (return n.toLong ()) else (повернути n * факторіал (n - 1)))
Приклад 2: Придатне для рекурсії хвоста, оскільки виклик функції самому собі fibonacci(n-1, a+b, a)є останньою операцією.
веселі фібоначчі (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
Ця програма обчислює 100- й член ряду Фібоначчі. Оскільки результат може бути дуже великим цілим числом, ми імпортували клас 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модифікатор, який повідомляє компілятору оптимізувати рекурсію.
