I denne artikel lærer du at oprette rekursive funktioner; en funktion, der kalder sig selv. Du vil også lære om halen rekursiv funktion.
En funktion, der kalder sig selv, er kendt som rekursiv funktion. Og denne teknik er kendt som rekursion.
Et fysisk verdenseksempel ville være at placere to parallelle spejle overfor hinanden. Ethvert objekt imellem dem reflekteres rekursivt.
Hvordan fungerer rekursion i programmering?
sjov hoved (args: Array) (… recurse ()…) fun recurse () (… recurse ()…)
Her recurse()kaldes funktionen fra selve recurse()funktionskroppen. Sådan fungerer dette program:
Her fortsætter det rekursive opkald for evigt og forårsager uendelig rekursion.
For at undgå uendelig rekursion, hvis … ellers (eller lignende tilgang) kan bruges, hvor en gren foretager det rekursive opkald, og en anden ikke gør det.
Eksempel: Find et nummer af et nummer ved hjælp af rekursion
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 kører programmet, vil output være:
Faktor af 4 = 24
Hvordan dette program fungerer?
Funktionens rekursive opkald factorial()kan forklares i følgende figur:
Her er de involverede trin:
factorial (4) // 1. funktionskald. Argument: 4 4 * faktor (3) // 2. funktionsopkald. Argument: 3 4 * (3 * faktor (2)) // 3. funktionskald. Argument: 2 4 * (3 * (2 * faktor (1))) // 4. funktionskald. Argument: 1 4 * (3 * (2 * 1)) 24
Kotlin Tail Recursion
Hale rekursion er et generisk koncept snarere end træk ved Kotlin sprog. Nogle programmeringssprog inklusive Kotlin bruger det til at optimere rekursive opkald, mens andre sprog (f.eks. Python) ikke understøtter dem.
Hvad er hale rekursion?
I normal rekursion udfører du først alle rekursive opkald og beregner endelig resultatet fra returværdier (som vist i ovenstående eksempel). Derfor får du ikke resultat, før alle rekursive opkald foretages.
I hale rekursion udføres beregninger først, derefter udføres rekursive opkald (det rekursive opkald sender resultatet af dit nuværende trin til det næste rekursive opkald). Dette gør det rekursive opkald svarende til looping og undgår risikoen for stackoverløb.
Betingelse for halerekursion
En rekursiv funktion er berettiget til halenrekursion, hvis funktionsopkaldet til sig selv er den sidste operation, det udfører. For eksempel,
Eksempel 1: Ikke berettiget til halenrekursion, fordi funktionsopkaldet til sig selv n*factorial(n-1)ikke er den sidste operation.
sjov faktor (n: Int): Lang (hvis (n == 1) (return n.toLong ()) andet (return n * faktor (n - 1)))
Eksempel 2: Berettiget til hale rekursion, fordi funktionsopkald til sig selv fibonacci(n-1, a+b, a)er den sidste operation.
sjov Fibonacci (n: Int, a: Lang, b: Lang): Lang (returnere hvis (n == 0) b ellers Fibonacci (n-1, a + b, a))
For at bede kompilatoren om at udføre halerekursion i Kotlin skal du markere funktionen 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 kører programmet, vil output være:
354224848179261915075
Dette program beregner den 100 th løbetid Fibonacci serien. Da output kan være et meget stort heltal, har vi importeret BigInteger-klasse fra Java-standardbiblioteket.
Her er funktionen fibonacci()markeret med tailrecmodifikator, og funktionen er berettiget til rekursivt haleopkald. Derfor optimerer compileren rekursionen i dette tilfælde.
Hvis du forsøger at finde 20000 th sigt (eller ethvert andet stort heltal) i Fibonacci-serien uden at bruge hale rekursion, kaster compileren java.lang.StackOverflowErrorundtagelse. Imidlertid fungerer vores program ovenfor fint. Det er fordi vi har brugt tail recursion, der bruger effektiv loopbaseret version i stedet for traditionel rekursion.
Eksempel: Faktor ved hjælp af halerekursion
Eksemplet til beregning af et nummer i ovenstående eksempel (første eksempel) kan ikke optimeres til halerekursion. Her er et andet program til at udføre den samme opgave.
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 kører programmet, vil output være:
Faktor af 5 = 120
Compileren kan optimere rekursionen i dette program, da den rekursive funktion er berettiget til halenrekursion, og vi har brugt en tailrecmodifikator, der fortæller kompilatoren at optimere rekursionen.
