У овом чланку ћете научити да креирате рекурзивне функције; функција која себе позива. Такође, научићете о рекурзивној функцији репа.
Функција која себе назива позната је као рекурзивна функција. А, ова техника је позната као рекурзија.
Пример физичког света био би постављање два паралелна огледала окренута једно према другом. Било који предмет између њих рефлектовао би се рекурзивно.
Како рекурзија функционише у програмирању?
забавно главно (аргс: Арраи) (… репеатсе ()…) фун рекурсе () (… репеатсе ()…)
Овде се 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
Котлин Таил Рецурсион
Рекурзија репа је генерички концепт, а не карактеристика језика Котлин. Неки програмски језици, укључујући Котлин, користе га за оптимизацију рекурзивних позива, док их други језици (нпр. Питхон) не подржавају.
Шта је рекурзија репа?
У нормалној рекурзији прво извршите све рекурзивне позиве, а резултат коначно израчунавате из повратних вредности (као што је приказано у горњем примеру). Дакле, не добијате резултат док се не изврше сви рекурзивни позиви.
У репној рекурзији прво се извршавају прорачуни, а затим се извршавају рекурзивни позиви (рекурзивни позив преноси резултат вашег тренутног корака на следећи рекурзивни позив). То рекурзивни позив чини еквивалентним петљи и избегава ризик од преливања стека.
Услов за рекурзију репа
Рекурзивна функција испуњава услове за реп рекурзију ако је позив функције сам себи последња операција коју извршава. На пример,
Пример 1: Не испуњава услове за рекурзију репа, јер позив функције сам себи n*factorial(n-1)није последња операција.
фактор фактор забаве (н: Инт): Лонг (иф (н == 1) (ретурн н.тоЛонг ()) елсе (ретурн н * фацториал (н - 1)))
Пример 2: Испуњава услове за рекурзију репа, јер је позив функције сам себи fibonacci(n-1, a+b, a)последња операција.
забавни фибоначи (н: Инт, а: Лонг, б: Лонг): Лонг (врати иф (н == 0) б елсе фибонацци (н-1, а + б, а))
Да бисте компајлеру рекли да изведе рекурзију репа у Котлину, морате означити функцију 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 тх рок за Фибоначијевог серије. Будући да излаз може бити врло велики цео број, увели смо класу БигИнтегер из Јава стандардне библиотеке.
Овде је функција 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модификатор који каже компајлеру да оптимизира рекурзију.
