U ovom ćete članku naučiti stvarati rekurzivne funkcije; funkcija koja sebe naziva. Također, naučit ćete o rekurzivnoj funkciji repa.
Funkcija koja sebe naziva poznata je kao rekurzivna funkcija. A, ova je tehnika poznata kao rekurzija.
Primjer fizičkog svijeta bio bi postavljanje dva paralelna ogledala okrenuta jedno prema drugome. Bilo koji objekt između njih reflektirao bi se rekurzivno.
Kako rekurzija djeluje u programiranju?
zabavno glavno (args: Array) (… repeatse () …) fun rekurse () (… repeatse () …)
Ovdje se recurse()funkcija poziva iz tijela same recurse()funkcije. Evo kako ovaj program funkcionira:
Ovdje se rekurzivni poziv nastavlja zauvijek uzrokujući beskonačnu rekurziju.
Da bi se izbjegla beskonačna rekurzija, može se koristiti… ako se išta drugo (ili sličan pristup) tamo gdje jedna grana uputi rekurzivni poziv, a druga ne.
Primjer: Pronađite faktorijel broja pomoću 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) )
Kada pokrenete program, izlaz će biti:
Faktorijal od 4 = 24
Kako ovaj program radi?
Rekurzivni poziv factorial()funkcije može se objasniti na sljedećoj slici:
Ovdje su navedeni koraci:
faktorijel (4) // 1. poziv funkcije. Argument: 4 4 * faktorijel (3) // 2. poziv funkcije. Argument: 3 4 * (3 * faktorijel (2)) // 3. poziv funkcije. Argument: 2 4 * (3 * (2 * faktorijel (1))) // 4. poziv funkcije. Argument: 1 4 * (3 * (2 * 1)) 24
Kotlinska repna rekurzija
Rekurzija repa je generički pojam, a ne obilježje jezika Kotlin. Neki programski jezici, uključujući Kotlin, koriste ga za optimizaciju rekurzivnih poziva, dok ih drugi jezici (npr. Python) ne podržavaju.
Što je rekurzija repa?
U normalnoj rekurziji prvo izvodite sve rekurzivne pozive, a rezultat konačno izračunavate iz povratnih vrijednosti (kao što je prikazano u gornjem primjeru). Dakle, nećete dobiti rezultat dok se ne izvrše svi rekurzivni pozivi.
U repnoj rekurziji prvo se izvršavaju izračuni, a zatim se izvršavaju rekurzivni pozivi (rekurzivni poziv prosljeđuje rezultat vašeg trenutnog koraka sljedećem rekurzivnom pozivu). To rekurzivni poziv čini ekvivalentnim petljanjem i izbjegava rizik od preljeva steka.
Uvjet za rekurziju repa
Rekurzivna funkcija prihvatljiva je za rekurziju repa ako je poziv funkcije sam sebi zadnja operacija koju izvršava. Na primjer,
Primjer 1: Ne ispunjava uvjete za rekurziju repa, jer poziv funkcije na sebe n*factorial(n-1)nije zadnja operacija.
faktor zabavnosti (n: Int): Long (if (n == 1) (return n.toLong ()) else (return n * factorial (n - 1)))
Primjer 2: Ispunjava uvjete za rekurziju repa, jer je poziv funkcije na sebe fibonacci(n-1, a+b, a)zadnja operacija.
zabavno fibonacci (n: Int, a: Long, b: Long): Long (povratak if (n == 0) b else fibonacci (n-1, a + b, a))
Da biste kompajleru rekli da izvede rekurziju repa u Kotlinu, morate označiti funkciju tailrecmodifikatorom.
Primjer: 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) )
Kada pokrenete program, izlaz će biti:
354224848179261915075
Ovaj program izračunava stoti pojam Fibonaccijeve serije. Budući da izlaz može biti vrlo velik cijeli broj, uveli smo klasu BigInteger iz standardne Java knjižnice.
Ovdje je funkcija fibonacci()označena tailrecmodifikatorom i funkcija je prihvatljiva za repni rekurzivni poziv. Stoga prevodilac u ovom slučaju optimizira rekurziju.
Ako pokušate pronaći 20000- ti pojam (ili bilo koji drugi veliki cijeli broj) Fibonaccijeve serije bez korištenja rep rekurzije, sastavljač će izbaciti java.lang.StackOverflowErroriznimku. Međutim, naš gore navedeni program dobro funkcionira. To je zato što smo koristili repnu rekurziju koja koristi učinkovitu verziju temeljenu na petlji umjesto tradicionalne rekurzije.
Primjer: Faktorijalno korištenje rekurzije repa
Primjer za izračunavanje faktorijela broja u gornjem primjeru (prvi primjer) ne može se optimizirati za rekurziju repa. Evo različitog programa za izvođenje istog zadatka.
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) )
Kada pokrenete program, izlaz će biti:
Faktorijal od 5 = 120
Prevoditelj može optimizirati rekurziju u ovom programu jer rekurzivna funkcija ispunjava uvjete za rekurziju repa, a mi smo koristili tailrecmodifikator koji kaže kompajleru da optimizira rekurziju.
