I denne artikkelen vil du lære å lage rekursive funksjoner; en funksjon som kaller seg selv. Du vil også lære om rekursiv funksjon av halen.
En funksjon som kaller seg selv er kjent som rekursiv funksjon. Og denne teknikken er kjent som rekursjon.
Et fysisk eksempel på verden ville være å plassere to parallelle speil mot hverandre. Ethvert objekt i mellom dem vil reflekteres rekursivt.
Hvordan fungerer rekursjon i programmering?
morsom hoved (args: Array) (… recurse ()…) fun recurse () (… recurse ()…)
Her recurse()kalles recurse()funksjonen fra selve funksjonens kropp . Slik fungerer dette programmet:
Her fortsetter den rekursive samtalen for alltid og forårsaker uendelig rekursjon.
For å unngå uendelig rekursjon, hvis… ellers (eller lignende tilnærming) kan brukes der en gren gjør det rekursive anropet, og andre ikke gjør det.
Eksempel: Finn et faktura av et tall ved hjelp av rekursjon
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) )
Når du kjører programmet, vil utdataene være:
Faktor av 4 = 24
Hvordan dette programmet fungerer?
Funksjonens rekursive anrop factorial()kan forklares i følgende figur:
Her er trinnene involvert:
fabrikk (4) // 1. funksjonsanrop. Argument: 4 4 * faktoriell (3) // 2. funksjonsanrop. Argument: 3 4 * (3 * faktor (2)) // 3. funksjonsanrop. Argument: 2 4 * (3 * (2 * faktor (1))) // fjerde funksjonsanrop. Argument: 1 4 * (3 * (2 * 1)) 24
Kotlin Tail Recursion
Tail recursion er et generisk konsept snarere enn funksjonen i Kotlin-språket. Noen programmeringsspråk, inkludert Kotlin, bruker det til å optimalisere rekursive samtaler, mens andre språk (f.eks. Python) ikke støtter dem.
Hva er hale rekursjon?
I normal rekursjon utfører du først alle rekursive anrop, og beregner resultatet fra returverdier til slutt (som vist i eksemplet ovenfor). Derfor får du ikke resultat før alle rekursive samtaler er foretatt.
I halen rekursjon utføres beregninger først, deretter utføres rekursive samtaler (den rekursive samtalen sender resultatet av ditt nåværende trinn til neste rekursive samtale). Dette gjør det rekursive anropet som looping, og unngår risikoen for stackoverløp.
Betingelse for halerekursjon
En rekursiv funksjon er kvalifisert for halerekursjon hvis funksjonsanropet til seg selv er den siste operasjonen den utfører. For eksempel,
Eksempel 1: Ikke kvalifisert for halerekursjon fordi funksjonsanropet til seg selv n*factorial(n-1)ikke er den siste operasjonen.
morsom faktor (n: Int): Lang (hvis (n == 1) (return n.toLong ()) annet (return n * faktor (n - 1)))
Eksempel 2: Kvalifisert for halerekursjon fordi funksjonsanrop til seg selv fibonacci(n-1, a+b, a)er den siste operasjonen.
morsom Fibonacci (n: Int, a: Lang, b: Lang): Lang (tilbake hvis (n == 0) b annet Fibonacci (n-1, a + b, a))
For å be kompilatoren om å utføre halerekursjon i Kotlin, må du merke funksjonen med tailrecmodifikator.
Eksempel: Tail Recursion
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) )
Når du kjører programmet, vil utdataene være:
354224848179261915075
Dette programmet beregner 100 th begrepet av Fibonacci-serien. Siden produksjonen kan være et veldig stort heltall, har vi importert BigInteger-klasse fra Java standardbibliotek.
Her er funksjonen fibonacci()merket med tailrecmodifikator, og funksjonen er kvalifisert for rekursiv haleoppringing. Derfor optimaliserer kompilatoren rekursjonen i dette tilfellet.
Hvis du prøver å finne den 20 000 th sikt (eller noen andre store heltall) av Fibonacci-serien uten å bruke halen rekursjon, vil kompilatoren kaste java.lang.StackOverflowErrorunntak. Imidlertid fungerer vårt program ovenfor helt fint. Det er fordi vi har brukt tail recursion som bruker effektiv loopbasert versjon i stedet for tradisjonell rekursion.
Eksempel: Faktor ved bruk av halerekursjon
Eksemplet for å beregne et faktura av et tall i eksemplet ovenfor (første eksempel) kan ikke optimaliseres for halerekursjon. Her er et annet program for å utføre den samme oppgaven.
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) )
Når du kjører programmet, vil utdataene være:
Faktor på 5 = 120
Kompilatoren kan optimalisere rekursjonen i dette programmet ettersom den rekursive funksjonen er kvalifisert for halenrekursjon, og vi har brukt tailrecmodifikator som forteller kompilatoren å optimalisere rekursjonen.
