Scala for Backend Engineering & Functional Programming · Lekcja

Adnotacja tailrec

Gwarantowana optymalizacja

Lekcja 2 z 413 kroki

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

Wywołanie rekurencyjne znajduje się w pozycji ogonowej, gdy jest ostatnią czynnością funkcji. Funkcję rekurencyjną ogonowo można zoptymalizować do postaci pętli wykorzystującej ponownie jedną ramkę stosu, dzięki czemu nigdy nie dojdzie do jego przepełnienia.

Pozycja ogonowa

W wyrażeniu n * factorial(n-1) wywołanie rekurencyjne nie jest ostatnie: po jego powrocie wykonywane jest mnożenie. W wyrażeniu gcd(b, a % b) wywołanie jest ostatnie. Tylko druga funkcja jest rekurencyjna ogonowo.

Adnotacja @tailrec

Należy zaimportować scala.annotation.tailrec i oznaczyć metodę adnotacją. Kompilator sprawdzi wtedy, czy wywołanie rzeczywiście znajduje się w pozycji ogonowej, i zastosuje optymalizację. Jeśli tak nie jest, kompilacja zakończy się niepowodzeniem.

import scala.annotation.tailrec

object Main {
  @tailrec
  def countdown(n: Int): Unit = {
    if (n >= 0) {
      println(n)
      countdown(n - 1)
    }
  }

  def main(args: Array[String]): Unit = countdown(3)
}

Gwarantowana optymalizacja

Najważniejszą zaletą @tailrec jest gwarancja w czasie kompilacji. Od razu otrzymają Państwo informację, jeśli funkcja nie jest bezpieczna dla stosu, zamiast dowiedzieć się o tym dopiero w wyniku awarii podczas działania dla dużych danych.

Rekurencyjny ogonowo gcd

Algorytm Euklidesa jest już rekurencyjny ogonowo: wywołanie rekurencyjne stanowi wynik całego ciała funkcji. Oznaczenie go adnotacją potwierdza ten fakt.

import scala.annotation.tailrec

object Main {
  @tailrec
  def gcd(a: Int, b: Int): Int =
    if (b == 0) a else gcd(b, a % b)

  def main(args: Array[String]): Unit = {
    println(gcd(1071, 462))
  }
}

Co przerywa pozycję ogonową

Typowe konstrukcje wyprowadzające wywołanie z pozycji ogonowej:

Wykonywanie działań arytmetycznych na wyniku: n + f(...).
Umieszczanie wyniku w konstruktorze: x :: f(...).
Użycie wyniku w bloku try.

Przykład bez rekurencji ogonowej

Ta suma nie jest rekurencyjna ogonowo, ponieważ dodawanie otacza wywołanie. Oznaczenie jej adnotacją @tailrec spowodowałoby błąd kompilacji. (Przedstawiono ją bez adnotacji, aby mogła zostać uruchomiona).

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

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

Dlaczego nie można zastosować optymalizacji

Ponieważ wyrażenie n + sum(n - 1) musi zachować n, aby dokończyć dodawanie po powrocie z wywołania, każdy poziom potrzebuje własnej ramki stosu. Kompilator nie może przekształcić tego w pętlę, więc funkcja nie jest rekurencyjna ogonowo.

Duża pętla rekurencyjna ogonowo

Suma rekurencyjna ogonowo wykorzystująca akumulator działa dla ogromnych danych bez przepełnienia stosu, ponieważ ponownie wykorzystuje jedną ramkę.

import scala.annotation.tailrec

object Main {
  @tailrec
  def sumTo(n: Int, acc: Long = 0): Long =
    if (n == 0) acc else sumTo(n - 1, acc + n)

  def main(args: Array[String]): Unit = {
    println(sumTo(1000000))
  }
}

tailrec wymaga metody finalnej lub lokalnej

Aby można było zastosować @tailrec, metoda nie może być przesłanialna: musi być private, final albo lokalna/zagnieżdżona. Otwarta metoda mogłaby zostać przesłonięta, co przerwałoby optymalizację, dlatego kompilator ją odrzuca.

Ograniczenie rekurencji wzajemnej

@tailrec optymalizuje wyłącznie funkcję wywołującą samą siebie. Dwie funkcje wywołujące się wzajemnie (rekurencja wzajemna) nie mogą zostać bezpośrednio zoptymalizowane ogonowo przez JVM; potrzebne jest do tego trampolinowanie, omówione później.

Szybki test

Proszę sprawdzić swoje rozumienie @tailrec.

Odpowiedz w interaktywnej lekcji

Podsumowanie

Poznali Państwo adnotację @tailrec:

Wywołanie w pozycji ogonowej można zoptymalizować do postaci pętli.
@tailrec zapewnia gwarancję bezpieczeństwa stosu w czasie kompilacji.
Metoda musi być final, private albo lokalna.
Adnotacja obejmuje tylko rekurencję własną, a nie wzajemną.

Bezpłatny start

Ucz się Scala dzięki korepetycjom AI — za darmo

Pisz i uruchamiaj kod w przeglądarce, otrzymuj natychmiastową pomoc od korepetytora AI dostępnego 24/7 i kontynuuj naukę w sieci lub w aplikacji.

Kursy: 39
Lekcje: 143

Zacznij naukę bezpłatnie Wyświetl pełny kurs

Często zadawane pytania

Czy lekcja „Adnotacja tailrec” jest bezpłatna?

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

Gwarantowana optymalizacja Ć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 2 z 4.

Ile czasu zajmuje lekcja „Adnotacja 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 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