Funkcje tailrec
Optymalizuj rekurencję
Funkcje tailrec to bezpłatna lekcja Kotlin Academy na CoddyKit. To lekcja 3 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej Kotlin Academy, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs Kotlin Academy zawiera 4 lekcji w sumie.
Czym jest rekurencja ogonowa?
Funkcja jest ogonowo rekurencyjna, gdy jej wywołanie rekurencyjne jest ostatnią operacją. Kotlin może wtedy zoptymalizować ją do postaci pętli, unikając przepełnienia stosu.
tailrec fun countdown(n: Int) {
if (n < 0) return
println(n)
countdown(n - 1)
}
fun main() {
countdown(3)
}Modyfikator tailrec
Dodaj modyfikator tailrec, a kompilator przekształci rekurencję w iterację, używając stałej ilości miejsca na stosie.
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))
}Wzorzec akumulatora
Aby nadać rekurencji postać ogonową, przekazuj wyniki w parametrze akumulatora, tak aby po zakończeniu wywołania nie pozostało już nic do obliczenia.
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))
}Dlaczego wywołanie musi być ostatnie
Jeśli po wywołaniu rekurencyjnym wykonywana jest jakakolwiek operacja (na przykład mnożenie jego wyniku), wywołanie nie znajduje się na pozycji ogonowej i nie może zostać zoptymalizowane.
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"))
}Przykład rekurencji nieogonowej
Ta funkcja obliczająca silnię NIE jest ogonowo rekurencyjna, ponieważ mnożenie następuje po powrocie z wywołania. Oznaczenie jej jako tailrec spowodowałoby ostrzeżenie.
fun badFactorial(n: Int): Long {
if (n <= 1) return 1
return n * badFactorial(n - 1)
}
fun main() {
println(badFactorial(5))
}Unikanie przepełnienia stosu
Głęboka rekurencja bez tailrec może doprowadzić do awarii. Dzięki niemu nawet duże dane wejściowe są przetwarzane przy stałym zużyciu miejsca na stosie.
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))
}Weryfikacja przez kompilator
Jeśli oznaczysz funkcję jako tailrec, ale wywołanie nie znajduje się na pozycji ogonowej, kompilator wyświetli ostrzeżenie i nie przeprowadzi optymalizacji. Należy potraktować to ostrzeżenie poważnie.
tailrec fun gcd(a: Int, b: Int): Int {
if (b == 0) return a
return gcd(b, a % b)
}
fun main() {
println(gcd(48, 18))
}Rekurencja ogonowa a pętla
Funkcja tailrec kompiluje się w przybliżeniu do tego samego kodu co równoważna pętla, ale pozwala wyrazić algorytm rekurencyjnie.
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))
}Wiele parametrów
Funkcje ogonowo rekurencyjne często przekazują kilka parametrów stanu, które są aktualizowane w wywołaniu rekurencyjnym.
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))
}Odwracanie za pomocą tailrec
Akumulator może stopniowo budować wynik, na przykład odwrócony ciąg znaków.
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"))
}Praktyczne wyszukiwanie
Wyszukiwanie iteracyjne można łatwo odwzorować za pomocą rekurencji ogonowej.
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))
}Szybkie sprawdzenie
Sprawdź swoją wiedzę na temat funkcji tailrec.
Podsumowanie
Opanowali Państwo funkcje tailrec:
tailrecprzekształca rekurencję na pozycji ogonowej w pętlę, unikając przepełnienia stosu.- Wywołanie rekurencyjne musi być ostatnią operacją.
- Aby uzyskać postać ogonową, używaj parametru akumulatora.
- Kompilator ostrzega, gdy funkcji nie można zoptymalizować.
tailrec fun sum(n: Int, acc: Int = 0): Int =
if (n == 0) acc else sum(n - 1, acc + n)
fun main() {
println(sum(50))
}Często zadawane pytania
Czy lekcja „Funkcje tailrec” jest bezpłatna?
Tak — pełny tekst „Funkcje tailrec” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu Kotlin Academy, przejdź na CoddyKit PRO. Kurs Kotlin Academy zawiera 4 lekcji w sumie.
Co nauczysz się w „Funkcje tailrec”?
Optymalizuj rekurencję Ćwiczysz Kotlin Academy z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.
Czy potrzebuję doświadczenia, aby zacząć Kotlin Academy?
Nie wymagamy żadnego doświadczenia. Kotlin Academy w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 3 z 4.
Ile czasu zajmuje lekcja „Funkcje tailrec”?
Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.
Czy mogę pisać i uruchamiać kod w tej lekcji Kotlin Academy?
Tak. Każda lekcja Kotlin Academy zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.