V tomto článku se naučíte vytvářet rekurzivní funkce; funkce, která si říká. Dozvíte se také rekurzivní funkci ocasu.
Funkce, která se sama nazývá, se nazývá rekurzivní funkce. A tato technika je známá jako rekurze.
Příkladem fyzického světa by bylo umístění dvou paralelních zrcadel proti sobě. Jakýkoli objekt mezi nimi by se odrazil rekurzivně.
Jak funguje rekurze v programování?
fun main (args: Array) (… recurse ()…) fun recurse () (… recurse ()…)
Zde je recurse()funkce volána z těla recurse()samotné funkce. Tento program funguje takto:
Zde rekurzivní volání pokračuje navždy a způsobuje nekonečnou rekurzi.
Aby se zabránilo nekonečné rekurzi, pokud … else (nebo podobný přístup) lze použít tam, kde jedna větev provádí rekurzivní volání a jiná ne.
Příklad: Najděte faktoriál čísla pomocí rekurze
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) )
Když spustíte program, výstup bude:
Faktoriál 4 = 24
Jak tento program funguje?
Rekurzivní volání factorial()funkce lze vysvětlit na následujícím obrázku:
Jedná se o tyto kroky:
faktoriál (4) // 1. volání funkce. Argument: 4 4 * faktoriál (3) // 2. volání funkce. Argument: 3 4 * (3 * faktoriál (2)) // 3. volání funkce. Argument: 2 4 * (3 * (2 * faktoriál (1))) // 4. volání funkce. Argument: 1 4 * (3 * (2 * 1)) 24
Kotlinova ocasní rekurze
Ocasní rekurze je spíše obecný pojem než rys jazyka Kotlin. Některé programovací jazyky včetně Kotlin jej používají k optimalizaci rekurzivních volání, zatímco jiné jazyky (např. Python) je nepodporují.
Co je rekurze ocasu?
V normální rekurzi nejprve provedete všechna rekurzivní volání a nakonec vypočítáte výsledek z návratových hodnot (jak je uvedeno ve výše uvedeném příkladu). Z tohoto důvodu nedostanete výsledek, dokud neproběhnou všechny rekurzivní hovory.
V ocasní rekurzi se nejprve provedou výpočty, poté se provedou rekurzivní volání (rekurzivní volání předá výsledek vašeho aktuálního kroku dalšímu rekurzivnímu volání). Díky tomu je rekurzivní volání ekvivalentní smyčce a vyhnete se riziku přetečení zásobníku.
Podmínka rekurze ocasu
Rekurzivní funkce je způsobilá pro rekurzi ocasu, pokud je volání funkce samo o sobě poslední operací, kterou provádí. Například,
Příklad 1: Nelze použít pro rekurzi ocasu, protože volání funkce samo o sobě n*factorial(n-1)není poslední operací.
zábavný faktoriál (n: Int): Long (if (n == 1) (návrat n.toLong ()) else (návrat n * faktoriál (n - 1)))
Příklad 2: Vhodné pro rekurzi ocasu, protože volání funkce samo o sobě fibonacci(n-1, a+b, a)je poslední operací.
fun fibonacci (n: Int, a: Long, b: Long): Long (return if (n == 0) b else fibonacci (n-1, a + b, a))
Chcete-li kompilátoru říct, aby v Kotlinu provedl rekurzi ocasu, musíte funkci označit tailrecmodifikátorem.
Příklad: Ocasní rekurze
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) )
Když spustíte program, výstup bude:
354224848179261915075
Tento program počítá stý termín série Fibonacci. Protože výstupem může být velmi velké celé číslo, importovali jsme třídu BigInteger ze standardní knihovny Java.
Zde je funkce fibonacci()označena tailrecmodifikátorem a funkce je způsobilá pro ocasní rekurzivní volání. Kompilátor proto v tomto případě optimalizuje rekurzi.
Pokud jste se snaží najít 20000 tý termín (nebo jakýkoli jiný velký integer) na Fibonacciho bez ocasu rekurze, kompilátor hodit java.lang.StackOverflowErrorvýjimku. Náš výše uvedený program však funguje dobře. Je to proto, že jsme použili ocasní rekurzi, která používá efektivní verzi založenou na smyčce místo tradiční rekurze.
Příklad: Faktoriál pomocí rekurze ocasu
Příklad pro výpočet faktoriálu čísla ve výše uvedeném příkladu (první příklad) nelze optimalizovat pro rekurzi ocasu. Tady je jiný program pro provádění stejného úkolu.
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) )
Když spustíte program, výstup bude:
Faktoriál 5 = 120
Kompilátor může optimalizovat rekurzi v tomto programu, protože rekurzivní funkce je způsobilá pro rekurzi ocasu a použili jsme tailrecmodifikátor, který říká kompilátoru k optimalizaci rekurze.
