Selles artiklis õpitakse looma rekursiivseid funktsioone; funktsioon, mis kutsub ennast. Samuti saate teada saba rekursiivse funktsiooni kohta.
Ise ennast kutsuv funktsioon on tuntud kui rekursiivne funktsioon. Ja seda tehnikat tuntakse rekursioonina.
Füüsilise maailma näide oleks asetada kaks paralleelset peeglit üksteise poole. Kõik nende vahel olevad objektid kajastuksid rekursiivselt.
Kuidas rekursioon programmeerimisel töötab?
lõbus peamine (args: massiiv) (… kordus ()…) lõbus kordus () (… kordus ()…)
Siin recurse()nimetatakse recurse()funktsiooni funktsiooni kehast endast. See programm töötab nii:
Siin jätkub rekursiivne kõne igavesti, põhjustades lõpmatut rekursiooni.
Lõputu rekursiooni vältimiseks võib kasutada… (või muud sarnast lähenemist), kus üks haru teeb rekursiivse kõne ja teine mitte.
Näide: leidke rekursiooni abil numbri faktorial
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) )
Programmi käivitamisel on väljund järgmine:
Faktor 4 = 24
Kuidas see programm töötab?
Funktsiooni rekursiivset väljakutset factorial()saab selgitada järgmisel joonisel:
Siin on etapid:
faktoriaal (4) // 1. funktsiooni väljakutse. Argument: 4 4 * faktoriaal (3) // funktsiooni 2. kõne. Argument: 3 4 * (3 * faktoriaal (2)) // kolmanda funktsiooni kõne. Argument: 2 4 * (3 * (2 * faktoriaal (1))) // funktsiooni 4. kõne. Argument: 1 4 * (3 * (2 * 1)) 24
Kotlini saba rekursioon
Saba rekursioon on pigem üldine mõiste kui Kotlini keele tunnus. Mõni programmeerimiskeel, sealhulgas Kotlin, kasutab seda rekursiivsete kõnede optimeerimiseks, samas kui teised keeled (nt Python) neid ei toeta.
Mis on saba rekursioon?
Tavalises rekursioonis sooritate kõigepealt kõik rekursiivsed kõned ja arvutate tulemuse lõpuks tagastusväärtuste põhjal (nagu on näidatud ülaltoodud näites). Seega ei saa te tulemusi enne, kui kõik rekursiivsed kõned on tehtud.
Saba rekursioonis tehakse kõigepealt arvutused, seejärel täidetakse rekursiivsed kõned (rekursiivne kõne edastab teie praeguse sammu tulemuse järgmisele rekursiivsele kõnele). See muudab rekursiivse kõne samaväärseks loopimisega ja väldib virna ülevoolu ohtu.
Tingimus saba rekursiooniks
Rekursiivne funktsioon sobib saba rekursiooniks, kui funktsioonikõne iseendale on viimane toiming, mille ta teeb. Näiteks,
Näide 1: ei sobi saba rekursiooniks, kuna funktsiooni väljakutse iseendale n*factorial(n-1)pole viimane toiming.
lõbus faktoriaal (n: Int): pikk (kui (n == 1) (tagastage n.Pikk ()) muu (tagastage n * faktoriaal (n - 1)))
Näide 2: saba rekursiooniks sobilik, kuna funktsioonikõne iseendale fibonacci(n-1, a+b, a)on viimane toiming.
lõbus fibonacci (n: Int, a: Long, b: Long): Long (return if (n == 0) b else fibonacci (n-1, a + b, a))
Kompilaatori käskimiseks Kotlinis saba rekursiooni sooritamiseks peate funktsiooni tailrecmuutjaga märkima .
Näide: saba rekursioon
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) )
Programmi käivitamisel on väljund järgmine:
354224848179261915075
See programm arvutab 100 th Termin Fibonacci seerias. Kuna väljund võib olla väga suur täisarv, oleme importinud BigIntegeri klassi Java standardkogust.
Siin on funktsioon fibonacci()tähistatud tailrecmodifikaatoriga ja funktsioon sobib saba rekursiivseks kõneks. Seega optimeerib kompilaator sel juhul rekursiooni.
Kui püüad leida 20000 th perspektiivis (või mõne muu suure täisarv) Fibonacci seeria ilma saba rekursioon, koostaja viskavad java.lang.StackOverflowErrorerand. Meie ülaltoodud programm töötab aga suurepäraselt. Selle põhjuseks on see, et oleme kasutanud saba rekursiooni, mis kasutab traditsioonilise rekursiooni asemel tõhusat silmusepõhist versiooni.
Näide: faktori kasutamine saba rekursiooni abil
Ülalolevas näites numbri faktori arvutamiseks mõeldud näidet (esimene näide) ei saa saba rekursiooni jaoks optimeerida. Sama ülesande täitmiseks on erinev programm.
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) )
Programmi käivitamisel on väljund järgmine:
Faktoor 5 = 120
Koostaja saab selles programmis rekursiooni optimeerida, kuna rekursiivne funktsioon sobib saba rekursiooniks ja oleme kasutanud tailrecmodifikaatorit, mis rekursiooni optimeerimiseks käsib kompilaatoril.
