Ebben a cikkben megtanulja létrehozni a rekurzív függvényeket; egy olyan funkció, amely önmagát hívja. Ezenkívül megismerheti a farok rekurzív funkcióját.
Az önmagát hívó függvény rekurzív függvénynek ismert. Ezt a technikát rekurziónak nevezik.
A fizikai világ példája az lenne, ha két párhuzamos tükröt egymással szemben helyeznének el. A köztük lévő bármely objektum rekurzív módon tükröződik.
Hogyan működik a rekurzió a programozásban?
fun main (args: Array) (… recurse ()…) fun recurse () (… recurse ()…)
Itt recurse()a recurse()függvényt magából a funkciótestből hívják meg. A program így működik:
Itt a rekurzív hívás örökké folytatódik, végtelen rekurziót okozva.
A végtelen rekurzió elkerülése érdekében, ha… más (vagy hasonló megközelítés) használható, ahol az egyik ág rekurzív hívást kezdeményez, a másik nem.
Példa: Keresse meg a szám faktoriálját a Rekurzió használatával
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) )
A program futtatásakor a kimenet a következő lesz:
4 = 24 tényező
Hogyan működik ez a program?
A factorial()függvény rekurzív hívása a következő ábrán magyarázható:
Itt vannak az érintett lépések:
faktoriális (4) // 1. függvényhívás. Argumentum: 4 4 * faktoriális (3) // 2. függvényhívás. Argumentum: 3 4 * (3 * faktoriális (2)) // 3. függvényhívás. Argumentum: 2 4 * (3 * (2 * faktoriális (1))) // 4. függvényhívás. Érv: 1 4 * (3 * (2 * 1)) 24
Kotlin farok rekurzió
A farokrekurzió általános fogalom, nem pedig a Kotlin nyelv sajátossága. Egyes programozási nyelvek, beleértve a Kotlin-t is, a rekurzív hívások optimalizálására használják, míg más nyelvek (pl. Python) nem támogatják őket.
Mi az a farok rekurzió?
Normál rekurzióban először az összes rekurzív hívást hajtja végre, és az eredményt végül a visszatérési értékekből számítja ki (amint az a fenti példában látható). Ezért nem kap eredményt, amíg az összes rekurzív hívás meg nem történik.
A farokrekurzióban először a számításokat hajtják végre, majd a rekurzív hívásokat hajtják végre (a rekurzív hívás átadja az aktuális lépés eredményét a következő rekurzív hívásnak). Ez egyenértékűvé teszi a rekurzív hívást a hurokkal és elkerüli a verem túlcsordulásának kockázatát.
A farok rekurziójának feltétele
A rekurzív függvény akkor alkalmas farokrekurzióra, ha a funkcióhívás önmagában az utolsó művelet, amelyet végrehajt. Például,
1. példa: Nem jogosult farok rekurzióra, mert a saját maga n*factorial(n-1)által kapott függvényhívás nem az utolsó művelet.
szórakoztató faktoriális (n: Int): Hosszú (ha (n == 1) (return n.toLong ()) else (return n * faktoriális (n - 1)))
2. példa: Jogosult a farok rekurziójára, mert a funkcióhívás önmagában fibonacci(n-1, a+b, a)az utolsó művelet.
fun fibonacci (n: Int, a: Long, b: Long): Long (return if (n == 0) b else fibonacci (n-1, a + b, a))
Ahhoz, hogy a fordító megmondja, hogy végezzen farokrekurziót Kotlinban, meg kell jelölnie a függvényt tailrecmódosítóval.
Példa: Farok rekurzió
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) )
A program futtatásakor a kimenet a következő lesz:
354224848179261915075
Ez a program kiszámítja a 100 th kifejezés a Fibonacci-sorozat. Mivel a kimenet nagyon nagy egész szám lehet, importáltuk a BigInteger osztályt a Java szabványos könyvtárából.
Itt a függvényt módosítóval fibonacci()jelölik, tailrecés a funkció alkalmas farok rekurzív hívásra. Ezért a fordító ebben az esetben optimalizálja a rekurziót.
Ha megpróbálja megtalálni a Fibonacci sorozat 20000- ik tagját (vagy bármely más nagy egész számot) farokrekurzió használata nélkül, a fordító java.lang.StackOverflowErrorkivételt vet . A fenti programunk azonban remekül működik. Ennek oka, hogy farokrekurziót használtunk, amely a hagyományos rekurzió helyett hatékony hurok alapú verziót használ.
Példa: Faktori a farokrekurzió használatával
A fenti példában szereplő szám tényleges kiszámításához szükséges példa (első példa) nem optimalizálható farokrekurzióra. Itt egy másik program ugyanazon feladat végrehajtására.
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) )
A program futtatásakor a kimenet a következő lesz:
5-ös tényező = 120
A fordító optimalizálhatja a rekurziót ebben a programban, mivel a rekurzív függvény alkalmas a farok rekurziójára, és olyan tailrecmódosítót használtunk, amely megmondja a fordítónak, hogy optimalizálja a rekurziót.
