V tem članku se boste naučili ustvarjati rekurzivne funkcije; funkcija, ki se sama pokliče. Spoznali boste tudi rekurzivno funkcijo repa.
Funkcija, ki sama kliče, je znana kot rekurzivna funkcija. Ta tehnika je znana kot rekurzija.
Primer fizičnega sveta bi bil postavitev dveh vzporednih ogledal drug proti drugemu. Vsak predmet vmes bi se odseval rekurzivno.
Kako deluje rekurzija pri programiranju?
fun main (args: Array) (… repeatse ()…) fun repeatse () (… repeatse ()…)
Tu se recurse()funkcija pokliče iz telesa recurse()same funkcije. Ta program deluje tako:
Tu se rekurzivni klic nadaljuje za vedno in povzroči neskončno rekurzijo.
Da bi se izognili neskončni rekurziji, se lahko uporabi… če (ali podoben pristop), kjer ena veja izvede rekurzivni klic, druga pa ne.
Primer: Poiščite faktorijev števila z uporabo rekurzije
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) )
Ko zaženete program, bo rezultat:
Faktorijev od 4 = 24
Kako deluje ta program?
Rekurzivni klic factorial()funkcije je razložen na naslednji sliki:
Tu so navedeni koraki:
factorial (4) // 1. klic funkcije. Argument: 4 4 * faktorijel (3) // 2. klic funkcije. Argument: 3 4 * (3 * faktorijel (2)) // 3. klic funkcije. Argument: 2 4 * (3 * (2 * factorial (1))) // 4. klic funkcije. Argument: 1 4 * (3 * (2 * 1)) 24
Kotlinova repna rekurzija
Rekurzija repa je splošen pojem in ne značilnost jezika Kotlin. Nekateri programski jeziki, vključno s Kotlinom, ga uporabljajo za optimizacijo rekurzivnih klicev, medtem ko jih drugi jeziki (npr. Python) ne podpirajo.
Kaj je rekurzija repa?
V običajni rekurziji najprej izvedete vse rekurzivne klice in rezultat izračunate nazadnje iz vrnjenih vrednosti (kot je prikazano v zgornjem primeru). Zato ne dobite rezultata, dokler niso opravljeni vsi rekurzivni klici.
V repni rekurziji se najprej izvedejo izračuni, nato se izvedejo rekurzivni klici (rekurzivni klic posreduje rezultat vašega trenutnega koraka v naslednji rekurzivni klic). S tem je rekurzivni klic enakovreden zanki in se izogne nevarnosti prelivanja skladov.
Pogoj za rekurzijo repa
Rekurzivna funkcija je primerna za rekurzijo repa, če je klic funkcije zadnja operacija, ki jo izvede. Na primer
Primer 1: Ni primerno za rekurzijo repa, ker klic funkcije sam n*factorial(n-1)ni zadnja operacija.
fun factorial (n: Int): Long (if (n == 1) (return n.toLong ()) else (vrni n * factorial (n - 1)))
Primer 2: Primerno za rekurzijo repa, ker je klic funkcije sam sebi fibonacci(n-1, a+b, a)zadnja operacija.
zabavno fibonacci (n: Int, a: Long, b: Long): Long (vrne, če (n == 0) b drugo fibonacci (n-1, a + b, a))
Če želite prevajalniku povedati, da izvede rekurzijo repa v Kotlinu, morate funkcijo označiti z tailrecmodifikatorjem.
Primer: Rekurzija repa
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) )
Ko zaženete program, bo rezultat:
354224848179261915075
Ta program izračunal 100 th izraz serije Fibonaccijevega. Ker je rezultat lahko zelo veliko celo število, smo iz standardne knjižnice Java uvozili razred BigInteger.
Tu je funkcija fibonacci()označena z tailrecmodifikatorjem in je primerna za rekurzivni klic. Zato prevajalnik v tem primeru optimizira rekurzijo.
Če poskusite najdejo 20000 th izraz (ali katero koli drugo veliko celo število) serije Fibonaccijevega brez uporabe rep rekurzije, bo prevajalnik vrže java.lang.StackOverflowErrorizjemo. Vendar naš zgornji program deluje v redu. Ker smo uporabili repno rekurzijo, ki namesto tradicionalne rekurzije uporablja učinkovito različico, ki temelji na zanki.
Primer: Faktorska uporaba rekorzije repa
Primera za izračun faktorja števila v zgornjem primeru (prvi primer) ni mogoče optimizirati za rekurzijo repa. Tukaj je drug program za izvajanje iste naloge.
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) )
Ko zaženete program, bo rezultat:
Faktorijev od 5 = 120
Prevajalnik lahko v tem programu optimizira rekurzijo, saj je rekurzivna funkcija primerna za repno rekurzijo, zato smo uporabili tailrecmodifikator, ki prevajalniku pove, naj optimizira rekurzijo.
