V tomto článku sa naučíte vytvárať rekurzívne funkcie; funkcia, ktorá si hovorí. Dozviete sa tiež o rekurzívnej funkcii chvosta.
Funkcia, ktorá si hovorí, je známa ako rekurzívna funkcia. A táto technika je známa ako rekurzia.
Fyzickým svetovým príkladom by bolo umiestnenie dvoch paralelných zrkadiel oproti sebe. Akýkoľvek objekt medzi nimi by sa odrážal rekurzívne.
Ako funguje rekurzia v programovaní?
fun main (args: Array) (… recurse () …) fun recurse () (… recurse () …)
Tu sa recurse()funkcia volá z tela samotnej recurse()funkcie. Tento program funguje nasledovne:
Tu pokračuje rekurzívne volanie navždy a spôsobuje nekonečnú rekurziu.
Aby sa zabránilo nekonečnej rekurzii, ak … iný (alebo podobný prístup) sa dá použiť tam, kde jedna vetva robí rekurzívne volanie a druhá nie.
Príklad: Vyhľadajte faktoriál čísla pomocou rekurzie
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) )
Po spustení programu bude výstup:
Faktoriál 4 = 24
Ako tento program funguje?
Rekurzívne volanie factorial()funkcie možno vysvetliť na nasledujúcom obrázku:
Týka sa to týchto krokov:
faktoriál (4) // 1. volanie funkcie. Argument: 4 4 * faktoriál (3) // 2. volanie funkcie. Argument: 3 4 * (3 * faktoriál (2)) // 3. volanie funkcie. Argument: 2 4 * (3 * (2 * faktoriál (1))) // 4. volanie funkcie. Argument: 1 4 * (3 * (2 * 1)) 24
Kotlinova chvostová rekurzia
Koncová rekurzia je skôr všeobecný pojem ako vlastnosť jazyka Kotlin. Niektoré programovacie jazyky vrátane Kotlin ho používajú na optimalizáciu rekurzívnych volaní, zatiaľ čo iné jazyky (napr. Python) ich nepodporujú.
Čo je to rekurzia chvosta?
Pri normálnej rekurzii najskôr vykonáte všetky rekurzívne volania a nakoniec vypočítate výsledok z návratových hodnôt (ako je uvedené vo vyššie uvedenom príklade). Preto nedostanete výsledok, kým nebudú uskutočnené všetky rekurzívne volania.
Pri chvostovej rekurzii sa najskôr vykonajú výpočty, potom sa vykonajú rekurzívne volania (rekurzívne volanie odovzdá výsledok vášho aktuálneho kroku nasledujúcemu rekurzívnemu volaniu). Toto robí rekurzívne volanie rovnocenné so slučkou a vyhýba sa riziku pretečenia zásobníka.
Podmienka pre rekurziu chvosta
Rekurzívna funkcia je spôsobilá na rekurziu chvosta, ak je samotné volanie funkcie poslednou operáciou, ktorú vykonáva. Napríklad,
Príklad 1: Nemá nárok na rekurziu chvosta, pretože volanie funkcie samo o sebe n*factorial(n-1)nie je poslednou operáciou.
zábavný faktoriál (n: Int): Long (if (n == 1) (návrat n.toLong ()) else (návrat n * faktoriál (n - 1)))
Príklad 2: Vhodné pre rekurziu chvosta, pretože volanie funkcie samo o sebe fibonacci(n-1, a+b, a)je poslednou operáciou.
fun fibonacci (n: Int, a: Long, b: Long): Long (return if (n == 0) b else fibonacci (n-1, a + b, a))
Ak chcete kompilátoru povedať, aby v Kotline vykonal rekurziu chvosta, musíte funkciu označiť tailrecmodifikátorom.
Príklad: chvostová rekurzia
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) )
Po spustení programu bude výstup:
354224848179261915075
Tento program počíta 100 th termín série Fibonacci. Pretože výstupom môže byť veľmi veľké celé číslo, importovali sme triedu BigInteger zo štandardnej knižnice Java.
Tu je funkcia fibonacci()označená tailrecmodifikátorom a funkcia je vhodná pre chvostové rekurzívne volanie. Preto kompilátor v tomto prípade optimalizuje rekurziu.
Ak ste sa snaží nájsť 20000 tý termín (alebo akýkoľvek iný veľký integer) na Fibonacciho bez chvosta rekurzia, kompilátor hodiť java.lang.StackOverflowErrorvýnimku. Náš vyššie uvedený program však funguje celkom dobre. Je to preto, že sme použili chvostovú rekurziu, ktorá namiesto tradičnej rekurzie využíva efektívnu verziu založenú na slučke.
Príklad: Faktoriál pomocou chvostovej rekurzie
Príklad na výpočet faktoriálu čísla vo vyššie uvedenom príklade (prvý príklad) nemožno optimalizovať pre chvostovú rekurziu. Toto je iný program na vykonávanie rovnakej úlohy.
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) )
Po spustení programu bude výstup:
Faktoriál 5 = 120
Kompilátor môže v tomto programe optimalizovať rekurziu, pretože rekurzívna funkcia je vhodná na rekurziu chvosta a tailrecna optimalizáciu rekurzie sme použili modifikátor, ktorý kompilátoru hovorí.
