Šajā rakstā jūs iemācīsities izveidot rekursīvas funkcijas; funkcija, kas pati sevi sauc. Jūs arī uzzināsiet par astes rekursīvo funkciju.
Funkcija, kas pati sevi sauc, ir pazīstama kā rekursīvā funkcija. Šī metode ir pazīstama kā rekursija.
Fiziskās pasaules piemērs būtu divu paralēlu spoguļu novietošana viens otram pretī. Jebkurš objekts starp tiem tiks atspoguļots rekursīvi.
Kā rekursija darbojas programmēšanā?
fun main (args: Array) (… recurse ()…) fun recurse () (… recurse ()…)
Šeit recurse()funkcija tiek izsaukta no paša recurse()funkcijas ķermeņa . Šī programma darbojas šādi:
Šeit rekurzīvais zvans turpinās mūžīgi, izraisot bezgalīgu rekursiju.
Lai izvairītos no bezgalīgas rekursijas, ja… var izmantot citu (vai līdzīgu pieeju), kur viena filiāle veic rekursīvu zvanu, bet otra - ne.
Piemērs: Atrodiet skaitļa faktorialu, izmantojot rekursiju
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) )
Palaidot programmu, izeja būs:
Faktoriāls 4 = 24
Kā šī programma darbojas?
Funkcijas rekursīvo izsaukumu factorial()var izskaidrot šādā attēlā:
Šeit ir iesaistītās darbības:
faktoriāls (4) // 1. funkcijas izsaukums. Arguments: 4 4 * faktoriāls (3) // 2. funkcijas izsaukums. Arguments: 3 4 * (3 * faktoriāls (2)) // 3. funkcijas izsaukums. Arguments: 2 4 * (3 * (2 * faktoriāls (1))) // 4. funkcijas izsaukums. Arguments: 1 4 * (3 * (2 * 1)) 24
Kotlina astes rekursija
Astes rekursija ir vispārējs jēdziens, nevis Kotlina valodas iezīme. Dažas programmēšanas valodas, tostarp Kotlin, to izmanto rekursīvo zvanu optimizēšanai, savukārt citas valodas (piemēram, Python) tos neatbalsta.
Kas ir astes rekursija?
Parastajā rekursijā vispirms veicat visus rekursīvos zvanus un beidzot aprēķināt rezultātu no atgriešanās vērtībām (kā parādīts iepriekšējā piemērā). Tādējādi jūs nesaņemat rezultātu, kamēr nav veikti visi rekursīvie zvani.
Astes rekursijā vispirms tiek veikti aprēķini, pēc tam tiek veikti rekursīvi zvani (rekursīvais zvans jūsu pašreizējā soļa rezultātu nodod nākamajam rekursīvajam zvanam). Tas padara rekursīvo zvanu līdzvērtīgu lokēšanai un novērš kaudzes pārpildes risku.
Nosacījums astes rekursijai
Rekursīvā funkcija ir piemērota astes rekursijai, ja funkcijas izsaukums sev ir pēdējā darbība, ko tā veic. Piemēram,
1. piemērs: Nav piemērota astes rekursija, jo funkcijas izsaukums pats par sevi n*factorial(n-1)nav pēdējā darbība.
jautrs faktoriāls (n: Int): garš (ja (n == 1) (atgriež n.toLong ()) cits (atgriež n * faktoriāls (n - 1)))
2. piemērs. Piemērots astes rekursijai, jo funkcija pati par sevi fibonacci(n-1, a+b, a)ir pēdējā darbība.
fun fibonacci (n: Int, a: Long, b: Long): Long (atgriezties, ja (n == 0) b cits fibonacci (n-1, a + b, a))
Lai liktu kompilatoram veikt astes rekursiju Kotlinā, funkcija jāatzīmē ar tailrecmodifikatoru.
Piemērs: astes rekursija
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) )
Palaidot programmu, izeja būs:
354224848179261915075
Šī programma aprēķina 100 th termiņš Fibonači sērija. Tā kā izeja var būt ļoti liels vesels skaitlis, mēs esam importējuši BigInteger klasi no Java standarta bibliotēkas.
Šeit funkcija fibonacci()ir atzīmēta ar tailrecmodifikatoru, un funkcija ir piemērota astes rekursīvajam izsaukumam. Tādējādi kompilators optimizē rekursiju šajā gadījumā.
Ja jūs mēģināt atrast 20000 th vārdu (vai jebkuru citu lielu skaitli) no Fibonači sērija, neizmantojot astes Rekursija, kompilators mest java.lang.StackOverflowErrorizņēmums. Tomēr mūsu programma iepriekš darbojas tikai lieliski. Tas ir tāpēc, ka mēs esam izmantojuši astes rekursiju, kas tradicionālās rekursijas vietā izmanto efektīvu cilpu balstītu versiju.
Piemērs: faktors, izmantojot astes rekursiju
Piemēru, lai aprēķinātu skaitļa faktoriālo skaitli iepriekš minētajā piemērā (pirmais piemērs), nevar optimizēt astes rekursijai. Šī paša uzdevuma veikšanai ir atšķirīga programma.
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) )
Palaidot programmu, izeja būs:
Faktoriskais koeficients 5 = 120
Kompilators var optimizēt rekursiju šajā programmā, jo rekursīvā funkcija ir piemērota astes rekursijai, un mēs esam izmantojuši tailrecmodifikatoru, kas kompilatoram liek rekursijas optimizēšanai.
