Scala for Backend Engineering & Functional Programming · Lekcja

Trampolinowanie

Rekurencja bez przepełnienia stosu

Trampolinowanie to bezpłatna lekcja Scala for Backend Engineering & Functional Programming na CoddyKit. To lekcja 4 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.

Ograniczenie @tailrec

@tailrec optymalizuje wyłącznie funkcję wywołującą bezpośrednio samą siebie. Nie pomaga w przypadku rekurencji wzajemnej (dwóch funkcji wywołujących się wzajemnie), która nadal rozbudowuje stos. Rozwiązaniem jest trampolinowanie.

Problem rekurencji wzajemnej

Rozważmy funkcje isEven i isOdd zdefiniowane za pomocą siebie nawzajem. Dla dużej liczby przepełnią stos, a żadnej z nich nie można oznaczyć adnotacją @tailrec.

object Main {
  def isEven(n: Int): Boolean = if (n == 0) true else isOdd(n - 1)
  def isOdd(n: Int): Boolean  = if (n == 0) false else isEven(n - 1)

  def main(args: Array[String]): Unit = {
    println(isEven(10))
  }
}

Czym jest trampolina

Trampolina przekształca wywołania rekurencyjne w dane. Zamiast wywoływać samą siebie, funkcja zwraca opis następnego kroku. Pętla sterująca wielokrotnie wykonuje te kroki, utrzymując stałą głębokość stosu.

TailRec w bibliotece standardowej

Scala udostępnia scala.util.control.TailCalls wraz z typem TailRec. Należy użyć done(x) dla wyniku końcowego oraz tailcall(...), aby odroczyć następne wywołanie.

import scala.util.control.TailCalls._

object Main {
  def isEven(n: Int): TailRec[Boolean] =
    if (n == 0) done(true) else tailcall(isOdd(n - 1))
  def isOdd(n: Int): TailRec[Boolean] =
    if (n == 0) done(false) else tailcall(isEven(n - 1))

  def main(args: Array[String]): Unit = {
    println(isEven(100000).result)
  }
}

done i tailcall

Dwa podstawowe elementy:

done(value) opakowuje końcową odpowiedź.
tailcall(expr) odracza wywołanie zwracające TailRec.

Wywołanie .result uruchamia pętlę trampoliny i zwraca wartość.

Bezpieczeństwo stosu

Ponieważ każde tailcall przekazuje sterowanie z powrotem do pętli sterującej zamiast zagnieżdżać wywołanie Javy, stos JVM nie rośnie wraz z głębokością rekurencji. Powyższy przykład obsługuje 100 000 kroków bez przepełnienia.

Trampolinowanie rekurencji własnej

Trampoliny sprawdzają się również przy zwykłej głębokiej rekurencji własnej, gdy nie można łatwo użyć akumulatora. Przedstawione tutaj głębokie odliczanie pozostaje bezpieczne dla stosu.

import scala.util.control.TailCalls._

object Main {
  def countDown(n: Int): TailRec[Int] =
    if (n == 0) done(0) else tailcall(countDown(n - 1))

  def main(args: Array[String]): Unit = {
    println(countDown(500000).result)
  }
}

Łączenie wyników za pomocą flatMap

TailRec obsługuje map i flatMap, dzięki czemu można wykonywać pracę po odroczonym wywołaniu, zachowując bezpieczeństwo stosu.

import scala.util.control.TailCalls._

object Main {
  def sum(n: Int): TailRec[Int] =
    if (n == 0) done(0)
    else tailcall(sum(n - 1)).map(_ + n)

  def main(args: Array[String]): Unit = {
    println(sum(100000).result)
  }
}

Jak działa pętla sterująca

W ujęciu koncepcyjnym .result uruchamia pętlę: pobiera bieżący krok; jeśli jest to done, zwraca jego wartość; jeśli jest to odroczone wywołanie, oblicza jedną warstwę i kontynuuje. Wszystko to odbywa się przy stałym zużyciu stosu.

Trampolinowanie w bibliotekach efektów

Biblioteki takie jak Cats Effect i ZIO wewnętrznie stosują trampolinowanie swoich łańcuchów flatMap, dlatego można tworzyć głęboko zagnieżdżone programy efektów bez przepełnienia stosu. Trampolinowanie stanowi podstawę bezpiecznych dla stosu efektów funkcyjnych.

Kiedy stosować trampolinowanie

Użyj trampoliny, gdy:

Masz wzajemną rekurencję, której nie można wyrazić jako jednej funkcji rekurencyjnej ogonowej.
Rekurencja jest zbyt głęboka dla stosu, a akumulator nie pasuje do rozwiązania.

W przypadku prostej rekurencji własnej najpierw preferuj @tailrec z akumulatorem.

Szybki sprawdzian

Sprawdź swoje rozumienie trampolinowania.

Podsumowanie

Nauczyłeś się, czym jest trampolinowanie:

Zapewnia bezpieczeństwo stosu przy wzajemnej i bardzo głębokiej rekurencji.
Używaj TailCalls: done(x) i tailcall(...), a następnie .result.
TailRec obsługuje map/flatMap.
Stanowi podstawę bibliotek efektów bez przepełnienia stosu.

Często zadawane pytania

Czy lekcja „Trampolinowanie” jest bezpłatna?

Tak — pełny tekst „Trampolinowanie” 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 „Trampolinowanie”?

Rekurencja bez przepełnienia stosu Ć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 4 z 4.

Ile czasu zajmuje lekcja „Trampolinowanie”?

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