In dit artikel leer je recursieve functies maken; een functie die zichzelf aanroept. Ook leer je over de recursieve staartfunctie.
Een functie die zichzelf aanroept, staat bekend als recursieve functie. En deze techniek staat bekend als recursie.
Een voorbeeld in de fysieke wereld zou zijn om twee parallelle spiegels tegenover elkaar te plaatsen. Elk object ertussenin zou recursief worden weergegeven.
Hoe werkt recursie bij programmeren?
fun main (args: Array) (… recurse () …) fun recurse () (… recurse () …)
Hier wordt de recurse()functie aangeroepen vanuit het lichaam van de recurse()functie zelf. Dit is hoe dit programma werkt:
Hier gaat de recursieve oproep voor altijd door, wat een oneindige recursie veroorzaakt.
Om oneindige recursie te voorkomen, kan if … else (of vergelijkbare benadering) worden gebruikt wanneer de ene branch de recursieve aanroep doet en de andere niet.
Voorbeeld: vind de faculteit van een getal met behulp van recursie
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) )
Wanneer u het programma uitvoert, is de uitvoer:
Factoriaal van 4 = 24
Hoe werkt dit programma?
De recursieve aanroep van de factorial()functie kan in de volgende afbeelding worden uitgelegd:
Hier zijn de betrokken stappen:
factorial (4) // 1e functieaanroep. Argument: 4 4 * faculteit (3) // 2e functieaanroep. Argument: 3 4 * (3 * faculteit (2)) // 3e functieaanroep. Argument: 2 4 * (3 * (2 * faculteit (1))) // 4e functieaanroep. Argument: 1 4 * (3 * (2 * 1)) 24
Kotlin Tail Recursion
Staartrecursie is een generiek concept in plaats van het kenmerk van de Kotlin-taal. Sommige programmeertalen, waaronder Kotlin, gebruiken het om recursieve oproepen te optimaliseren, terwijl andere talen (bijv. Python) ze niet ondersteunen.
Wat is staartrecursie?
Bij normale recursie voert u eerst alle recursieve aanroepen uit en berekent u als laatste het resultaat op basis van de geretourneerde waarden (zoals getoond in het bovenstaande voorbeeld). Daarom krijgt u pas resultaat als alle recursieve oproepen zijn gedaan.
Bij staartrecursie worden eerst berekeningen uitgevoerd en vervolgens worden recursieve oproepen uitgevoerd (de recursieve oproep geeft het resultaat van uw huidige stap door aan de volgende recursieve oproep). Dit maakt de recursieve aanroep gelijk aan looping en vermijdt het risico van stack-overflow.
Voorwaarde voor staartrecursie
Een recursieve functie komt in aanmerking voor staartrecursie als de functieaanroep naar zichzelf de laatste bewerking is die wordt uitgevoerd. Bijvoorbeeld,
Voorbeeld 1: komt niet in aanmerking voor staartrecursie omdat de functieaanroep naar zichzelf n*factorial(n-1)niet de laatste bewerking is.
fun factorial (n: Int): Long (if (n == 1) (return n.toLong ()) else (return n * factorial (n - 1)))
Voorbeeld 2: komt in aanmerking voor staartrecursie omdat de functieaanroep naar zichzelf fibonacci(n-1, a+b, a)de laatste bewerking is.
fun fibonacci (n: Int, a: Long, b: Long): Long (return if (n == 0) b else fibonacci (n-1, a + b, a))
Om de compiler te vertellen staartrecursie in Kotlin uit te voeren, moet je de functie markeren met een tailrecmodifier.
Voorbeeld: staartrecursie
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) )
Wanneer u het programma uitvoert, is de uitvoer:
354224848179261915075
Dit programma berekent de 100 ste term van de Fibonacci-reeks. Omdat de uitvoer een heel groot geheel getal kan zijn, hebben we de BigInteger-klasse geïmporteerd uit de Java-standaardbibliotheek.
Hier is de functie fibonacci()gemarkeerd met een tailrecmodifier en komt de functie in aanmerking voor een recursieve aanroep van de staart. Daarom optimaliseert de compiler in dit geval de recursie.
Als u probeert om de 20000 vinden ste termijn (of een andere grote integer) van de reeks van Fibonacci zonder gebruik te maken staartrecursie, zal de compiler gooien java.lang.StackOverflowErroruitzondering. Ons programma hierboven werkt echter prima. Het is omdat we staartrecursie hebben gebruikt die een efficiënte op lus gebaseerde versie gebruikt in plaats van traditionele recursie.
Voorbeeld: faculteit met behulp van staartrecursie
Het voorbeeld om de faculteit van een getal te berekenen in het bovenstaande voorbeeld (eerste voorbeeld) kan niet worden geoptimaliseerd voor staartrecursie. Hier is een ander programma om dezelfde taak uit te voeren.
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) )
Wanneer u het programma uitvoert, is de uitvoer:
Factoriaal van 5 = 120
De compiler kan de recursie in dit programma optimaliseren aangezien de recursieve functie in aanmerking komt voor staartrecursie, en we hebben een tailrecmodifier gebruikt die de compiler vertelt om de recursie te optimaliseren.
