Podstawy rekurencji
Funkcje rekurencyjne
Podstawy rekurencji to bezpłatna lekcja Scala for Backend Engineering & Functional Programming na CoddyKit. To lekcja 1 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 Scala for Backend Engineering & Functional Programming, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs Scala for Backend Engineering & Functional Programming zawiera 4 lekcji w sumie.
Czym jest rekurencja
Rekurencja zachodzi wtedy, gdy funkcja wywołuje samą siebie, aby rozwiązać mniejszą wersję tego samego problemu. Jest naturalnie dopasowana do programowania funkcyjnego i pozwala zastąpić wiele pętli definicjami odwołującymi się do samych siebie.
Dwa niezbędne elementy
Każda poprawna funkcja rekurencyjna potrzebuje:
- Przypadku bazowego, który zatrzymuje rekurencję.
- Przypadku rekurencyjnego, który przybliża wykonanie do przypadku bazowego.
Bez osiągalnego przypadku bazowego rekurencja będzie trwać bez końca.
Silnia
Klasyczny przykład: n! = n * (n-1)!, przy czym 0! = 1 jest przypadkiem bazowym.
object Main {
def factorial(n: Int): Int =
if (n <= 1) 1
else n * factorial(n - 1)
def main(args: Array[String]): Unit = {
println(factorial(5))
}
}Śledzenie wywołań
Każde wywołanie rekurencyjne wstrzymuje się i czeka na wynik wewnętrznego wywołania. factorial(3) rozwija się do 3 * (2 * (1)). Mnożenia są wykonywane podczas powrotu z wywołań.
object Main {
def factorial(n: Int): Int = {
println(s"entering factorial($n)")
if (n <= 1) 1 else n * factorial(n - 1)
}
def main(args: Array[String]): Unit = {
println("result = " + factorial(3))
}
}Suma listy
Rekurencja dla listy: suma to głowa plus suma ogona, przy czym suma pustej listy wynosi zero.
object Main {
def sum(xs: List[Int]): Int = xs match {
case Nil => 0
case h :: t => h + sum(t)
}
def main(args: Array[String]): Unit = {
println(sum(List(1, 2, 3, 4)))
}
}Długość listy
Ten sam schemat pozwala obliczyć długość: dla pustej listy wynik to 0, a w przeciwnym razie 1 plus długość ogona.
object Main {
def length[A](xs: List[A]): Int = xs match {
case Nil => 0
case _ :: t => 1 + length(t)
}
def main(args: Array[String]): Unit = {
println(length(List("a", "b", "c")))
}
}Stos wywołań
Każde oczekujące wywołanie rekurencyjne zajmuje ramkę stosu. Głęboka rekurencja tworzy wiele ramek. W przypadku bardzo dużych danych może to wyczerpać stos i spowodować zgłoszenie StackOverflowError.
Ciąg Fibonacciego
Niektóre problemy rozgałęziają się na wiele wywołań rekurencyjnych. Fibonacci wywołuje sam siebie dwukrotnie, co jest eleganckie, ale ma wykładniczy koszt.
object Main {
def fib(n: Int): Int =
if (n < 2) n
else fib(n - 1) + fib(n - 2)
def main(args: Array[String]): Unit = {
println(fib(10))
}
}Odwracanie listy
Rekurencja może budować nowe struktury: funkcja odwracająca listę dołącza głowę po odwróceniu ogona.
object Main {
def reverse[A](xs: List[A]): List[A] = xs match {
case Nil => Nil
case h :: t => reverse(t) :+ h
}
def main(args: Array[String]): Unit = {
println(reverse(List(1, 2, 3)))
}
}Rekurencja a iteracja
Pętle modyfikują licznik, natomiast rekurencja opisuje problem deklaratywnie. Oba podejścia są poprawne. Rekurencja sprawdza się szczególnie dobrze dla danych o strukturze drzewa oraz algorytmów dziel i zwyciężaj, ale naiwna rekurencja grozi przepełnieniem stosu przy dużych danych o strukturze liniowej.
Największy wspólny dzielnik
Algorytm Euklidesa jest naturalnie rekurencyjny i szybko zbieżny.
object Main {
def gcd(a: Int, b: Int): Int =
if (b == 0) a else gcd(b, a % b)
def main(args: Array[String]): Unit = {
println(gcd(48, 18))
}
}Szybki test
Proszę sprawdzić podstawy rekurencji.
Podsumowanie
Poznali Państwo podstawy rekurencji:
- Każda funkcja rekurencyjna potrzebuje przypadku bazowego i przypadku rekurencyjnego.
- Każde oczekujące wywołanie zajmuje ramkę stosu; głęboka rekurencja może doprowadzić do przepełnienia.
- Rekurencja naturalnie wyraża algorytmy operujące na listach i drzewach.
W następnym kroku zapewnią Państwo bezpieczeństwo stosu rekurencji za pomocą adnotacji @tailrec.
Często zadawane pytania
Czy lekcja „Podstawy rekurencji” jest bezpłatna?
Tak — pełny tekst „Podstawy rekurencji” 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 Scala for Backend Engineering & Functional Programming, przejdź na CoddyKit PRO. Kurs Scala for Backend Engineering & Functional Programming zawiera 4 lekcji w sumie.
Co nauczysz się w „Podstawy rekurencji”?
Funkcje rekurencyjne Ćwiczysz Scala for Backend Engineering & Functional Programming 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ąć Scala for Backend Engineering & Functional Programming?
Nie wymagamy żadnego doświadczenia. Scala for Backend Engineering & Functional Programming 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 1 z 4.
Ile czasu zajmuje lekcja „Podstawy rekurencji”?
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 Scala for Backend Engineering & Functional Programming?
Tak. Każda lekcja Scala for Backend Engineering & Functional Programming 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.
Wszystkie lekcje w tym kursie
- Podstawy rekurencji
- Adnotacja tailrec
- Wzorzec akumulatora
- Trampolinowanie