В тази статия ще се научите да създавате рекурсивни функции; функция, която се извиква. Също така ще научите за рекурсивната функция на опашката.
Функция, която се извиква, е известна като рекурсивна функция. И тази техника е известна като рекурсия.
Пример за физически свят би бил поставянето на две успоредни огледала един срещу друг. Всеки обект между тях ще бъде отразен рекурсивно.
Как работи рекурсията в програмирането?
fun main (args: Array) (… repeatse () …) fun recuse () (… 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. Някои езици за програмиране, включително 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)е последната операция.
забавни фибоначи (n: Int, a: Long, b: Long): Long (връщане 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модификатор, който казва на компилатора да оптимизира рекурсията.
