Kotlin Academy · Lektion

tailrec-Funktionen

Optimieren Sie Rekursion

tailrec-Funktionen ist eine kostenlose Kotlin Academy-Lektion auf CoddyKit. Dies ist Lektion 3 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des Kotlin Academy-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der Kotlin Academy-Kurs umfasst insgesamt 4 Lektionen.

Was ist Tail-Rekursion?

Eine Funktion ist tailrekursiv, wenn ihr rekursiver Aufruf die allerletzte Operation ist. Kotlin kann sie dann in eine Schleife umwandeln und so einen Stacküberlauf vermeiden.

tailrec fun countdown(n: Int) {
    if (n < 0) return
    println(n)
    countdown(n - 1)
}

fun main() {
    countdown(3)
}

Der tailrec-Modifikator

Fügen Sie den Modifikator tailrec hinzu, und der Compiler schreibt die Rekursion in eine Iteration um, die konstanten Stack-Speicher verwendet.

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))
}

Das Akkumulator-Muster

Damit eine Rekursion die Tail-Form erreicht, speichern Sie Ergebnisse in einem Akkumulator-Parameter, sodass nach dem Aufruf nichts mehr zu berechnen bleibt.

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))
}

Warum der Aufruf an letzter Stelle stehen muss

Wenn nach dem rekursiven Aufruf noch etwas geschieht, etwa die Multiplikation mit seinem Ergebnis, steht der Aufruf nicht an der letzten Stelle und kann nicht optimiert werden.

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"))
}

Gegenbeispiel: keine Tail-Rekursion

Diese Fakultätsfunktion ist NICHT tailrekursiv, weil die Multiplikation erst nach der Rückkehr des Aufrufs erfolgt. Eine Kennzeichnung mit tailrec würde eine Warnung auslösen.

fun badFactorial(n: Int): Long {
    if (n <= 1) return 1
    return n * badFactorial(n - 1)
}

fun main() {
    println(badFactorial(5))
}

Stacküberläufe vermeiden

Tiefe Rekursion ohne tailrec kann zum Absturz führen. Mit tailrec können selbst große Eingaben mit konstantem Stack-Speicher verarbeitet werden.

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))
}

Überprüfung durch den Compiler

Wenn Sie eine Funktion mit tailrec kennzeichnen, der Aufruf aber nicht an der letzten Stelle steht, gibt der Compiler eine Warnung aus und optimiert nicht. Nehmen Sie diese Warnung ernst.

tailrec fun gcd(a: Int, b: Int): Int {
    if (b == 0) return a
    return gcd(b, a % b)
}

fun main() {
    println(gcd(48, 18))
}

Tail-Rekursion im Vergleich zur Schleife

Eine tailrec-Funktion wird ungefähr in denselben Code wie die entsprechende Schleife kompiliert, drückt den Algorithmus aber rekursiv aus.

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))
}

Mehrere Parameter

Tailrekursive Funktionen geben häufig mehrere Zustandsparameter weiter, die im rekursiven Aufruf alle aktualisiert werden.

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))
}

Mit tailrec umkehren

Ein Akkumulator kann ein Ergebnis wie eine umgekehrte Zeichenkette aufbauen.

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"))
}

Eine praktische Suche

Iterative Suchvorgänge lassen sich direkt in Tail-Rekursion übertragen.

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))
}

Kurzer Test

Testen Sie Ihr Verständnis von tailrec-Funktionen.

Zusammenfassung

Sie haben tailrec-Funktionen gelernt:

tailrec wandelt Rekursion an der letzten Aufrufstelle in eine Schleife um und vermeidet so Stacküberläufe.
Der rekursive Aufruf muss die letzte Operation sein.
Verwenden Sie einen Akkumulator-Parameter, um die Tail-Form zu erreichen.
Der Compiler warnt, wenn eine Funktion nicht optimiert werden kann.

tailrec fun sum(n: Int, acc: Int = 0): Int =
    if (n == 0) acc else sum(n - 1, acc + n)

fun main() {
    println(sum(50))
}

Häufig gestellte Fragen

Ist die Lektion „tailrec-Funktionen“ kostenlos?

Ja — der vollständige Text von „tailrec-Funktionen“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des Kotlin Academy-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der Kotlin Academy-Kurs umfasst insgesamt 4 Lektionen.

Was lerne ich in „tailrec-Funktionen“?

Optimieren Sie Rekursion Du übst Kotlin Academy mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.

Brauche ich Erfahrung, um Kotlin Academy zu starten?

Keine Vorkenntnisse erforderlich. Kotlin Academy auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 3 von 4.

Wie lange dauert die Lektion „tailrec-Funktionen“?

Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.

Kann ich in dieser Kotlin Academy-Lektion Code schreiben und ausführen?

Ja. Jede Kotlin Academy-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.

Alle Lektionen in diesem Kurs

← Zurück zu Kotlin Academy