Tässä artikkelissa opit luomaan rekursiivisia toimintoja; toiminto, joka kutsuu itseään. Opit myös hännän rekursiivisesta toiminnosta.
Itsensä kutsuva toiminto tunnetaan rekursiivisena funktiona. Ja tämä tekniikka tunnetaan rekursiona.
Fyysisen maailman esimerkki olisi sijoittaa kaksi rinnakkaista peiliä vastakkain. Mikä tahansa niiden välissä oleva esine heijastuu rekursiivisesti.
Kuinka rekursio toimii ohjelmoinnissa?
hauska pää (arg: Array) (… recurse ()…) fun recurse () (… recurse ()…)
Tässä recurse()funktiota kutsutaan recurse()itse toiminnasta. Näin tämä ohjelma toimii:
Tässä rekursiivinen puhelu jatkuu ikuisesti aiheuttaen ääretöntä rekursiota.
Ääretön rekursio vältetään, jos… muuta (tai vastaavaa lähestymistapaa) voidaan käyttää, kun yksi haara soittaa rekursiivisen puhelun ja toinen ei.
Esimerkki: Etsi luvun faktori rekursiota käyttämällä
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) )
Kun suoritat ohjelmaa, tulos on:
Kerroin 4 = 24
Kuinka tämä ohjelma toimii?
factorial()Funktion rekursiivinen kutsu voidaan selittää seuraavassa kuvassa:
Tässä ovat vaiheet:
factororial (4) // 1. funktion kutsu. Argumentti: 4 4 * kerroin (3) // 2. funktion kutsu. Argumentti: 3 4 * (3 * kerroin (2)) // 3. funktion kutsu. Argumentti: 2 4 * (3 * (2 * kerroin (1))) // 4. funktion kutsu. Väite: 1 4 * (3 * (2 * 1)) 24
Kotlin Tail Recurion
Hännän rekursio on pikemminkin yleinen käsite kuin Kotlinin kielen ominaisuus. Jotkut ohjelmointikielet, mukaan lukien Kotlin, käyttävät sitä rekursiivisten puheluiden optimointiin, kun taas muut kielet (esim. Python) eivät tue niitä.
Mikä on hännän rekursio?
Normaalissa rekursiossa soitat ensin kaikki rekursiiviset puhelut ja lasket tuloksen vihdoin paluuarvoista (kuten yllä olevassa esimerkissä näkyy). Siksi et saa tuloksia ennen kuin kaikki rekursiiviset puhelut on soitettu.
Häntärekursiossa laskelmat suoritetaan ensin, sitten suoritetaan rekursiiviset puhelut (rekursiivinen puhelu siirtää nykyisen vaiheen tuloksen seuraavalle rekursiiviselle puhelulle). Näin rekursiivinen puhelu vastaa silmukointia ja välttää pinon ylivuotoa.
Edellytys hännän rekursiolle
Rekursiivinen toiminto on kelvollinen rekursioon, jos toimintokutsu itselleen on viimeinen toiminto, jonka se suorittaa. Esimerkiksi,
Esimerkki 1: Ei oikeuta hännän rekursioon, koska toimintokutsu itselleen n*factorial(n-1)ei ole viimeinen operaatio.
hauska kerroin (n: Int): Pitkä (jos (n == 1) (palauta n.Pitkä ()) muu (palauta n * kerroin (n - 1)))
Esimerkki 2: Kelpoinen häntärekursioon, koska toimintokutsu itselleen fibonacci(n-1, a+b, a)on viimeinen toiminto.
hauska fibonacci (n: Int, a: Long, b: Long): Long (palaa jos (n == 0) b else fibonacci (n-1, a + b, a))
Jos haluat kertoa kääntäjälle suorittaa hännän rekursio Kotlinissa, sinun on merkittävä funktio tailrecmuokkaimella.
Esimerkki: Hännän rekursio
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) )
Kun suoritat ohjelmaa, tulos on:
354224848179261915075
Tämä ohjelma laskee 100 : nnen aikavälin Fibonacci-sarjan. Koska tulos voi olla erittäin suuri kokonaisluku, olemme tuoneet BigInteger-luokan Java-standardikirjastosta.
Tässä toiminto fibonacci()on merkitty tailrecmodifikaattorilla ja toiminto voidaan käyttää hännän rekursiiviseen puheluun. Täten kääntäjä optimoi rekursio tässä tapauksessa.
Jos yrität löytää 20000 nnen aikavälin (tai jokin muu suuri kokonaisluku) Fibonacci-sarjan käyttämättä häntää rekursiota, kääntäjä heittää java.lang.StackOverflowErrorpoikkeus. Yllä oleva ohjelma toimii kuitenkin hienosti. Se johtuu siitä, että olemme käyttäneet hännän rekursiota, joka käyttää tehokasta silmukkaan perustuvaa versiota perinteisen rekursio sijaan.
Esimerkki: Factorial käyttämällä hännän rekursiota
Yllä olevan esimerkin luvun ensimmäistä laskutoimitusta ei voida optimoida hännän rekursiota varten. Tässä on eri ohjelma saman tehtävän suorittamiseksi.
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) )
Kun suoritat ohjelmaa, tulos on:
Kerroin 5 = 120
Kääntäjä voi optimoida rekursiota tässä ohjelmassa, koska rekursiivinen toiminto on kelvollinen hännän rekursioon, ja olemme käyttäneet tailrecmuokkaajaa, joka kertoo kääntäjän rekursion optimoimiseksi.
