I den här artikeln lär du dig att skapa rekursiva funktioner; en funktion som kallar sig själv. Du kommer också att lära dig om svansrekursiv funktion.
En funktion som kallar sig själv kallas rekursiv funktion. Och den här tekniken är känd som rekursion.
Ett fysiskt världsexempel skulle vara att placera två parallella speglar mot varandra. Varje objekt däremellan skulle återspeglas rekursivt.
Hur fungerar rekursion i programmering?
kul huvud (args: Array) (… recurse ()…) fun recurse () (… recurse ()…)
Här recurse()kallas recurse()funktionen från själva funktionens kropp . Så här fungerar det här programmet:
Här fortsätter det rekursiva samtalet för alltid och orsakar oändlig rekursion.
För att undvika oändlig rekursion, om … annars (eller liknande tillvägagångssätt) kan användas där en gren gör det rekursiva samtalet och andra inte.
Exempel: Hitta ett faktum för ett nummer med Rekursion
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) )
När du kör programmet blir resultatet:
Faktor 4 = 24
Hur detta program fungerar?
factorial()Funktionens rekursiva samtal kan förklaras i följande bild:
Här är stegen:
factorial (4) // 1: a funktionsanrop. Argument: 4 4 * faktor (3) // 2: a funktionsanrop. Argument: 3 4 * (3 * faktor (2)) // 3: e funktionsanrop. Argument: 2 4 * (3 * (2 * faktor (1))) // 4: e funktionsanrop. Argument: 1 4 * (3 * (2 * 1)) 24
Kotlin Tail Recursion
Svansrekursion är ett generiskt begrepp snarare än funktionen i Kotlin-språket. Vissa programmeringsspråk inklusive Kotlin använder det för att optimera rekursiva samtal, medan andra språk (t.ex. Python) inte stöder dem.
Vad är svansrekursion?
I normal rekursion utför du först alla rekursiva samtal och beräknar slutligen resultatet från returvärden (som visas i exemplet ovan). Därför får du inte resultat förrän alla rekursiva samtal görs.
I svansrekursion utförs beräkningar först och sedan genomförs rekursiva samtal (det rekursiva samtalet skickar resultatet av ditt nuvarande steg till nästa rekursiva samtal). Detta gör att det rekursiva samtalet motsvarar looping och undviker risken för stacköverflöde.
Villkor för svansrekursion
En rekursiv funktion är berättigad till svansrekursion om funktionsanropet till sig själv är den senaste operationen den utför. Till exempel,
Exempel 1: Ej kvalificerad för svansrekursion eftersom funktionsanropet till sig själv n*factorial(n-1)inte är den sista operationen.
kul faktor (n: Int): Lång (om (n == 1) (returnera n.toLong ()) annat (returnera n * faktor (n - 1)))
Exempel 2: Kvalificerad för svansrekursion eftersom funktionsanrop till sig själv fibonacci(n-1, a+b, a)är den sista operationen.
rolig Fibonacci (n: Int, a: Lång, b: Lång): Lång (returnera om (n == 0) b annat Fibonacci (n-1, a + b, a))
För att be kompilatorn att utföra svansrekursion i Kotlin måste du markera funktionen med tailrecmodifierare.
Exempel: Tail Recursion
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) )
När du kör programmet blir resultatet:
354224848179261915075
Detta program beräknar den 100: e perioden av Fibonacci-serien. Eftersom utdata kan vara ett mycket stort heltal har vi importerat BigInteger-klassen från Java standardbibliotek.
Här är funktionen fibonacci()markerad med tailrecmodifierare och funktionen är berättigad till svansrekursivt samtal. Därför optimerar kompilatorn rekursionen i detta fall.
Om du försöker hitta 20000: e termen (eller något annat stort heltal) i Fibonacci-serien utan att använda svansrekursion, kommer kompilatorn att kasta java.lang.StackOverflowErrorundantag. Men vårt program ovan fungerar bra. Det beror på att vi har använt svansrekursion som använder effektiv loopbaserad version istället för traditionell rekursion.
Exempel: Faktor som använder svansrekursion
Exemplet för att beräkna en faktor i ett exempel i ovanstående exempel (första exemplet) kan inte optimeras för svansrekursion. Här är ett annat program för att utföra samma uppgift.
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) )
När du kör programmet blir resultatet:
Faktor 5 = 120
Kompilatorn kan optimera rekursionen i detta program eftersom den rekursiva funktionen är kvalificerad för svansrekursion, och vi har använt tailrecmodifierare som ber kompilatorn att optimera rekursionen.
