tailrec-funktioner
Optimér rekursion
tailrec-funktioner er en gratis Kotlin Academy-lektion på CoddyKit. Dette er lektion 3 af 4. Du kan læse alle 3 lektioner i dette læringsspor gratis i deres fulde længde — derefter låser CoddyKit PRO alle lektioner op samt praktiske øvelser med en indbygget kodeeditor og en AI-underviser døgnet rundt. Den er en del af læringsforløbet i Kotlin Academy, og dine fremskridt synkroniseres på tværs af nettet og CoddyKit-appen. Kotlin Academy-kurset indeholder 4 lektioner i alt.
Hvad er halerekursion?
En funktion er halerekursiv, når det rekursive kald er den allersidste operation. Kotlin kan derefter optimere det til en løkke og undgå stakoverløb.
tailrec fun countdown(n: Int) {
if (n < 0) return
println(n)
countdown(n - 1)
}
fun main() {
countdown(3)
}Modifikatoren tailrec
Tilføj modifikatoren tailrec, så omskriver kompileren rekursionen til iteration med konstant stakplads.
tailrec fun sum(n: Int, acc: Int = 0): Int {
if (n == 0) return acc
return sum(n - 1, acc + n)
}
fun main() {
println(sum(100))
}Akkumulatormønstret
For at gøre rekursionen halerekursiv skal du føre resultaterne videre i en akkumulator-parameter, så der ikke er noget tilbage at beregne efter kaldet.
tailrec fun factorial(n: Int, acc: Long = 1): Long {
if (n <= 1) return acc
return factorial(n - 1, acc * n)
}
fun main() {
println(factorial(10))
}Hvorfor kaldet skal være sidst
Hvis der sker noget efter det rekursive kald, f.eks. at resultatet multipliceres, er kaldet ikke i haleposition og kan ikke optimeres.
tailrec fun length(s: String, acc: Int = 0): Int {
if (s.isEmpty()) return acc
return length(s.drop(1), acc + 1)
}
fun main() {
println(length("hello"))
}Modeksempel på ikke-halerekursion
Denne fakultetsfunktion er IKKE halerekursiv, fordi multiplikationen sker, efter kaldet returnerer. Hvis du markerede den med tailrec, ville du få en advarsel.
fun badFactorial(n: Int): Long {
if (n <= 1) return 1
return n * badFactorial(n - 1)
}
fun main() {
println(badFactorial(5))
}Undgå stakoverløb
Dyb rekursion uden tailrec kan få programmet til at gå ned. Med tailrec kan selv store input behandles med konstant stakplads.
tailrec fun count(n: Int, acc: Int = 0): Int {
if (n == 0) return acc
return count(n - 1, acc + 1)
}
fun main() {
println(count(100000))
}Kontrol i kompileren
Hvis du markerer en funktion med tailrec, men kaldet ikke er i haleposition, udsender kompileren en advarsel og optimerer ikke funktionen. Stol på advarslen.
tailrec fun gcd(a: Int, b: Int): Int {
if (b == 0) return a
return gcd(b, a % b)
}
fun main() {
println(gcd(48, 18))
}Halerekursion kontra løkke
En funktion med tailrec kompileres til omtrent den samme kode som den tilsvarende løkke, men udtrykker algoritmen rekursivt.
tailrec fun powerOfTwo(n: Int, acc: Long = 1): Long {
if (n == 0) return acc
return powerOfTwo(n - 1, acc * 2)
}
fun main() {
println(powerOfTwo(10))
}Flere parametre
Halerekursive funktioner sender ofte flere tilstandsparametre videre, som alle opdateres i det rekursive kald.
tailrec fun fib(n: Int, a: Long = 0, b: Long = 1): Long {
if (n == 0) return a
return fib(n - 1, b, a + b)
}
fun main() {
println(fib(20))
}Omvend med tailrec
En akkumulator kan opbygge et resultat som en omvendt streng.
tailrec fun reverse(s: String, acc: String = ""): String {
if (s.isEmpty()) return acc
return reverse(s.drop(1), s.first() + acc)
}
fun main() {
println(reverse("kotlin"))
}En praktisk søgning
Iterative søgninger kan let omsættes til halerekursion.
tailrec fun indexOf(list: List<Int>, target: Int, i: Int = 0): Int {
if (i >= list.size) return -1
if (list[i] == target) return i
return indexOf(list, target, i + 1)
}
fun main() {
println(indexOf(listOf(5, 6, 7), 7))
}Hurtig kontrol
Test din forståelse af tailrec-funktioner.
Opsummering
Du har lært om tailrec-funktioner:
tailrecomdanner rekursion i haleposition til en løkke og undgår stakoverløb.- Det rekursive kald skal være den sidste operation.
- Brug en akkumulatorparameter for at opnå haleform.
- Kompileren advarer, når en funktion ikke kan optimeres.
tailrec fun sum(n: Int, acc: Int = 0): Int =
if (n == 0) acc else sum(n - 1, acc + n)
fun main() {
println(sum(50))
}
Lær Kotlin med en AI-underviser — gratis
Skriv og kør rigtig kode i din browser, få øjeblikkelig hjælp fra en AI-underviser døgnet rundt, og fortsæt, hvor du slap, på web eller i appen.
- Kurser
- 51
- Lektioner
- 203
Ofte stillede spørgsmål
Er lektionen “tailrec-funktioner” gratis?
Ja — alle 3 lektioner i læringssporet Kotlin Academy, inklusive “tailrec-funktioner”, kan læses gratis i deres fulde længde her på webstedet. Derefter låser CoddyKit PRO alle lektioner op samt interaktive øvelser med en indbygget kodeeditor og en AI-underviser døgnet rundt. Kotlin Academy-kurset indeholder 4 lektioner i alt.
Hvad lærer jeg i “tailrec-funktioner”?
Optimér rekursion Du øver dig i Kotlin Academy med praktisk kode, som du kører direkte i browseren, og en AI-vejleder døgnet rundt besvarer dine spørgsmål, mens du arbejder dig gennem lektionen.
Skal jeg have erfaring for at begynde på Kotlin Academy?
Der kræves ingen tidligere erfaring. Kotlin Academy på CoddyKit er tilrettelagt for både begyndere og øvede, så du kan starte her eller fra begyndelsen og lære i dit eget tempo. Dette er lektion 3 af 4.
Hvor lang tid tager lektionen “tailrec-funktioner”?
De fleste CoddyKit-lektioner tager cirka 5–10 minutter. Hver lektion er kort og interaktiv, så du gør løbende fremskridt og kan fortsætte, hvor du slap – på både web og app.
Kan jeg skrive og køre kode i denne Kotlin Academy-lektion?
Ja. Alle Kotlin Academy-lektioner har en indbygget kodeeditor, så du kan skrive og køre rigtig kode direkte i din browser og få øjeblikkelig feedback fra AI – uden lokal opsætning.