Scala for Backend Engineering & Functional Programming · Lekcja

Myślenie rekurencyjne

Przypadki bazowe i kroki rekurencyjne.

Myślenie rekurencyjne 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.

Znaczenie rekurencji

Rekurencja występuje wtedy, gdy funkcja wywołuje samą siebie, aby rozwiązać mniejszą wersję tego samego problemu.

W języku Scala rekurencja dobrze pasuje do programowania funkcyjnego, ponieważ pozwala wyrażać pętle bez zmiennych modyfikowalnych.

Każda funkcja rekurencyjna potrzebuje dwóch rzeczy: sposobu zakończenia oraz sposobu zmniejszania problemu.

Najpierw przypadek bazowy

Przypadek bazowy to najprostsze dane wejściowe, na które funkcja potrafi odpowiedzieć bezpośrednio, bez dalszej rekurencji.

Bez przypadku bazowego funkcja wywoływałaby samą siebie w nieskończoność i zakończyłaby działanie błędem przepełnienia stosu.

Przypadek bazowy należy zawsze zaprojektować przed krokiem rekurencyjnym.

def countdown(n: Int): Unit =
  if (n < 0) ()           // base case: stop
  else {
    println(n)
    countdown(n - 1)      // recursive step
  }

Pierwsza funkcja rekurencyjna

Oto kompletny program sumujący liczby od 1 do n.

Przypadek bazowy zwraca 0, a przypadek rekurencyjny dodaje n do sumy wszystkich mniejszych liczb.

def sum(n: Int): Int =
  if (n == 0) 0
  else n + sum(n - 1)

@main def run(): Unit =
  println(sum(5))   // 15

Śledzenie wywołań

Aby zrozumieć rekurencję, należy ręcznie rozwinąć wywołania.

sum(3) zmienia się w 3 + sum(2), następnie w 3 + 2 + sum(1), a potem w 3 + 2 + 1 + sum(0).

Dopiero gdy sum(0) zwróci 0, łańcuch zwija się do jednej wartości: 6.

// sum(3)
// = 3 + sum(2)
// = 3 + (2 + sum(1))
// = 3 + (2 + (1 + sum(0)))
// = 3 + (2 + (1 + 0))
// = 6

Rekurencja na listach

Listy mają z natury rekurencyjną strukturę: lista jest albo pusta (Nil), albo składa się z głowy i krótszego ogona.

Ta struktura bezpośrednio odwzorowuje funkcje rekurencyjne. Pusta lista jest przypadkiem bazowym, a głowa wraz z rekurencją na ogonie tworzy krok rekurencyjny.

def length[A](xs: List[A]): Int = xs match {
  case Nil     => 0
  case _ :: t  => 1 + length(t)
}

Dopasowywanie wzorca ogona

Wzorzec :: rozdziela niepustą listę na głowę i ogon.

Każde wywołanie rekurencyjne działa na ściśle krótszej liście, co gwarantuje zbliżanie się do Nil.

To kanoniczny sposób rekurencyjnego przechodzenia po liście w języku Scala.

def sumList(xs: List[Int]): Int = xs match {
  case Nil    => 0
  case h :: t => h + sumList(t)
}

@main def run(): Unit =
  println(sumList(List(1, 2, 3, 4)))  // 10

Dwa wywołania rekurencyjne

Niektóre problemy rozgałęziają się na więcej niż jedno wywołanie rekurencyjne.

Klasycznym przykładem jest ciąg Fibonacciego, w którym każda wartość zależy od dwóch poprzednich.

Ta naiwna wersja jest prosta, ale powolna, ponieważ wiele razy oblicza te same wartości.

def fib(n: Int): Int =
  if (n < 2) n
  else fib(n - 1) + fib(n - 2)

@main def run(): Unit =
  println(fib(7))   // 13

Koszt stosu

Każde wywołanie rekurencyjne dodaje ramkę do stosu wywołań, która musi czekać na zakończenie wewnętrznego wywołania.

Przy bardzo głębokiej rekurencji stos może się wyczerpać, powodując błąd StackOverflowError.

Przewidywanie tego ryzyka ułatwia liczenie głębokości, a nie tylko rozmiaru danych.

// This would overflow the stack for large n:
// def deep(n: Int): Int =
//   if (n == 0) 0 else 1 + deep(n - 1)
// deep(1000000)  // StackOverflowError

Zbliżanie się do przypadku bazowego

Kluczowym niezmiennikiem rekurencji jest to, że każde wywołanie musi przybliżać się do przypadku bazowego.

Jeśli argument nie staje się mniejszy lub warunek zakończenia nigdy nie zostaje spełniony, rekurencja się nie kończy.

Należy to sprawdzić przed uruchomieniem programu.

def reverse[A](xs: List[A]): List[A] = xs match {
  case Nil    => Nil
  case h :: t => reverse(t) :+ h   // t is smaller than xs
}

Rekurencja a pętle

Kod imperatywny używa pętli while i modyfikowalnych liczników, a kod funkcyjny — rekurencji i niezmiennych wartości.

Oba podejścia mogą wyrażać te same obliczenia, ale rekurencja bardziej bezpośrednio opisuje strukturę danych.

W języku Scala często wybiera się rekurencję lub funkcje wyższego rzędu zamiast zwykłych pętli.

// Imperative
var total = 0
for (i <- 1 to 5) total += i

// Recursive
def sum(n: Int): Int = if (n == 0) 0 else n + sum(n - 1)

Projektowanie rozwiązania rekurencyjnego

Niezawodny schemat wygląda następująco: określ przypadek bazowy, załóż, że wywołanie rekurencyjne działa już dla mniejszych danych, a następnie połącz głowę z otrzymanym wynikiem.

Ten skok wiary jest sednem myślenia rekurencyjnego. Ufa się mniejszemu wywołaniu i obsługuje tylko jeden krok.

def maxOf(xs: List[Int]): Int = xs match {
  case h :: Nil => h
  case h :: t   => math.max(h, maxOf(t))
}

@main def run(): Unit =
  println(maxOf(List(3, 9, 2, 7)))  // 9

Szybkie sprawdzenie

Sprawdź swoje rozumienie struktury rekurencyjnej.

Podsumowanie

Rekurencja rozwiązuje problem, sprowadzając go do jego mniejszej wersji.

Każda funkcja rekurencyjna potrzebuje przypadku bazowego, który ją zatrzyma, oraz kroku rekurencyjnego zmniejszającego dane wejściowe i przybliżającego je do tego przypadku.

Listy, ze strukturą Nil oraz głowa–ogon, są idealnym środowiskiem do nauki myślenia rekurencyjnego. Przy bardzo dużych danych należy kontrolować głębokość stosu.

Często zadawane pytania

Czy lekcja „Myślenie rekurencyjne” jest bezpłatna?

Tak — pełny tekst „Myślenie rekurencyjne” 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 „Myślenie rekurencyjne”?

Przypadki bazowe i kroki 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 „Myślenie rekurencyjne”?

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

← Powrót do Scala for Backend Engineering & Functional Programming