În acest articol, veți învăța să creați funcții recursive; o funcție care se numește singură. De asemenea, veți afla despre funcția recursivă a cozii.
O funcție care se numește singură este cunoscută sub numele de funcție recursivă. Și această tehnică este cunoscută sub numele de recursivitate.
Un exemplu fizic al lumii ar fi plasarea a două oglinzi paralele una față de cealaltă. Orice obiect între ele s-ar reflecta recursiv.
Cum funcționează recursivitatea în programare?
fun main (args: Array) (… recurse () …) fun recurse () (… recurse () …)
Aici, recurse()funcția este numită din corpul recurse()funcției în sine. Iată cum funcționează acest program:
Aici, apelul recursiv continuă pentru totdeauna provocând recursivitate infinită.
Pentru a evita recursivitatea infinită, dacă … altfel (sau o abordare similară) poate fi utilizat acolo unde o ramură face apelul recursiv și alta nu.
Exemplu: Găsiți factorialul unui număr folosind Recursivitate
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) )
Când rulați programul, ieșirea va fi:
Factorial de 4 = 24
Cum funcționează acest program?
Apelul recursiv al factorial()funcției poate fi explicat în următoarea figură:
Iată pașii implicați:
factorial (4) // primul apel funcțional. Argument: 4 4 * factorial (3) // a doua funcție de apel. Argument: 3 4 * (3 * factorial (2)) // a treia funcție. Argument: 2 4 * (3 * (2 * factorial (1))) // a 4-a funcție de apel. Argument: 1 4 * (3 * (2 * 1)) 24
Recursiunea cozii Kotlin
Recursivitatea cozii este mai degrabă un concept generic decât caracteristica limbajului Kotlin. Unele limbaje de programare, inclusiv Kotlin, îl folosesc pentru a optimiza apelurile recursive, în timp ce alte limbaje (de exemplu, Python) nu le acceptă.
Ce este recursiunea cozii?
În recursivitate normală, efectuați mai întâi toate apelurile recursive și calculați rezultatul din valorile returnate în cele din urmă (așa cum se arată în exemplul de mai sus). Prin urmare, nu obțineți rezultate până când nu sunt efectuate toate apelurile recursive.
În recursivitatea de coadă, calculele sunt efectuate mai întâi, apoi apelurile recursive sunt executate (apelul recursiv trece rezultatul pasului curent la următorul apel recursiv). Acest lucru face apelul recursiv echivalent cu buclarea și evită riscul de revărsare a stivei.
Condiție pentru recursivitatea cozii
O funcție recursivă este eligibilă pentru recursivitatea cozii dacă funcția apelată la sine este ultima operație pe care o efectuează. De exemplu,
Exemplul 1: Nu este eligibil pentru recursivitatea cozii, deoarece apelul funcției către sine n*factorial(n-1)nu este ultima operație.
fun factorial (n: Int): Long (if (n == 1) (return n.toLong ()) else (return n * factorial (n - 1)))
Exemplul 2: eligibil pentru recursivitatea cozii, deoarece apelul de funcție către sine fibonacci(n-1, a+b, a)este ultima operație.
Fibonacci fun (n: Int, a: Long, b: Long): Long (returnează dacă (n == 0) b else Fibonacci (n-1, a + b, a))
Pentru a spune compilatorului să efectueze recursiunea cozii în Kotlin, trebuie să marcați funcția cu tailrecmodificator.
Exemplu: recursivitatea cozii
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) )
Când rulați programul, ieșirea va fi:
354224848179261915075
Acest program calculează al 100- lea termen al seriei Fibonacci. Deoarece, ieșirea poate fi un număr întreg foarte mare, am importat clasa BigInteger din biblioteca standard Java.
Aici, funcția fibonacci()este marcată cu tailrecmodificator și funcția este eligibilă pentru apel recursiv. Prin urmare, compilatorul optimizează recursivitatea în acest caz.
Dacă încercați să găsiți cel de-al 20000- lea termen (sau orice alt număr întreg) din seria Fibonacci fără a utiliza recursivitatea cozii, compilatorul va arunca o java.lang.StackOverflowErrorexcepție. Cu toate acestea, programul nostru de mai sus funcționează foarte bine. Acest lucru se datorează faptului că am folosit recursivitatea cozii care folosește o versiune eficientă bazată pe buclă în loc de recursivitatea tradițională.
Exemplu: Factorial folosind recursiunea cozii
Exemplul de calcul al factorialului unui număr din exemplul de mai sus (primul exemplu) nu poate fi optimizat pentru recursivitatea cozii. Iată un program diferit pentru a efectua aceeași sarcină.
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) )
Când rulați programul, ieșirea va fi:
Factorial de 5 = 120
Compilatorul poate optimiza recursivitatea în acest program, deoarece funcția recursivă este eligibilă pentru recursiunea cozii și am folosit un tailrecmodificator care îi spune compilatorului să optimizeze recursiunea.
