Šiame straipsnyje išmoksite kurti rekursines funkcijas; funkcija, kuri save vadina. Taip pat sužinosite apie uodegos rekursinę funkciją.
Funkcija, kuri save vadina, vadinama rekursine funkcija. Ši technika yra žinoma kaip rekursija.
Fizinio pasaulio pavyzdys būtų dviejų lygiagrečių veidrodžių pastatymas vienas priešais kitą. Bet koks tarp jų esantis objektas būtų atspindėtas rekursiškai.
Kaip vyksta rekursija programuojant?
linksmas pagrindinis (argumentai: masyvas) (… recurse ()…) fun recurse () (… recurse ()…)
Čia recurse()funkcija iškviečiama iš paties recurse()funkcijos kūno . Štai kaip ši programa veikia:
Čia rekurzinis skambutis tęsiasi amžinai ir sukelia begalinį rekursiją.
Kad būtų išvengta begalinio rekurso, jei … galima panaudoti dar vieną (ar panašų metodą), kai vienas filialas atlieka rekursinį skambutį, o kitas ne.
Pavyzdys: raskite skaičiaus faktorialą naudodamiesi rekursija
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) )
Kai paleisite programą, išvestis bus:
Faktorinis koeficientas 4 = 24
Kaip ši programa veikia?
Rekursinis factorial()funkcijos iškvietimas gali būti paaiškintas šiame paveiksle:
Štai keli veiksmai:
faktorius (4) // 1-osios funkcijos iškvietimas. Argumentas: 4 4 * faktorius (3) // 2-asis funkcijos iškvietimas. Argumentas: 3 4 * (3 * faktorius (2)) // 3-iosios funkcijos iškvietimas. Argumentas: 2 4 * (3 * (2 * faktorialas (1))) // 4-osios funkcijos iškvietimas. Argumentas: 1 4 * (3 * (2 * 1)) 24
Kotlino uodegos rekursija
Uodegos rekursija yra bendrinė sąvoka, o ne Kotlino kalbos bruožas. Kai kurios programavimo kalbos, įskaitant „Kotlin“, naudoja ją rekursiniams skambučiams optimizuoti, o kitos kalbos (pvz., „Python“) jų nepalaiko.
Kas yra uodegos rekursija?
Įprasto rekurso metu pirmiausia atliekate visus rekursinius skambučius ir pagaliau apskaičiuojate rezultatą iš grąžinimo verčių (kaip parodyta aukščiau pateiktame pavyzdyje). Taigi, rezultato negausite, kol nebus atlikti visi rekursiniai skambučiai.
Atliekant uodegos rekursiją, pirmiausia atliekami skaičiavimai, tada atliekami rekursiniai skambučiai (rekursinis skambutis perduoda jūsų dabartinio veiksmo rezultatą kitam rekursiniam skambučiui). Tai daro rekursinį skambutį tolygų kilpai ir išvengia kamino perpildymo rizikos.
Uodegos rekursijos sąlyga
Rekursinė funkcija yra tinkama uodegos rekursijai, jei funkcijos iškvietimas į save yra paskutinė operacija, kurią ji atlieka. Pavyzdžiui,
1 pavyzdys: netinkamas uodegos rekursija, nes funkcijos iškvietimas į save n*factorial(n-1)nėra paskutinė operacija.
įdomus faktorius (n: Int): ilgas (jei (n == 1) (grąžinti n.Long ()) dar (grąžinti n * faktorialą (n - 1)))
2 pavyzdys: Tinkamas atlikti uodegos rekursiją, nes funkcijos iškvietimas į save fibonacci(n-1, a+b, a)yra paskutinė operacija.
linksmas fibonacci (n: Int, a: Long, b: Long): Long (grįžti, jei (n == 0) b else fibonacci (n-1, a + b, a))
Norėdami pasakyti kompiliatoriui atlikti uodegos rekursiją Kotline, turite pažymėti funkciją tailrecmodifikatoriumi.
Pavyzdys: uodegos rekursija
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) )
Kai paleisite programą, išvestis bus:
354224848179261915075
Ši programa apskaičiuoja 100 -ąjį „Fibonacci“ serijos terminą. Kadangi išvestis gali būti labai didelis sveikas skaičius, mes importavome „BigInteger“ klasę iš „Java“ standartinės bibliotekos.
Čia funkcija fibonacci()pažymėta tailrecmodifikatoriumi ir funkcija gali būti naudojama uodegos rekursiniam skambučiui. Taigi šiuo atveju kompiliatorius optimizuoja rekursiją.
Jei bandysite rasti 20000 -ąjį „Fibonacci“ serijos terminą (arba bet kurį kitą didelį skaičių) nenaudodamas uodegos rekursijos, kompiliatorius išims java.lang.StackOverflowErrorišimtį. Tačiau mūsų aukščiau pateikta programa veikia puikiai. Taip yra todėl, kad mes naudojome uodegos rekursiją, kurioje vietoj tradicinės rekursijos naudojama efektyvi ciklo versija.
Pavyzdys: faktorius naudojant uodegos rekursiją
Aukščiau pateiktame pavyzdyje pateiktas skaičiaus faktorialo apskaičiavimo pavyzdys (pirmasis pavyzdys) negali būti optimizuotas uodegos rekursijai. Čia yra kita programa, skirta atlikti tą pačią užduotį.
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) )
Kai paleisite programą, išvestis bus:
Faktorinis koeficientas 5 = 120
Kompiliatorius gali optimizuoti šios programos rekursiją, nes rekursinė funkcija yra tinkama uodegos rekursijai, ir mes naudojome tailrecmodifikatorių, kuris kompiliatoriui liepia optimizuoti rekursiją.
