Trampolining
Stack-sikker rekursion
Trampolining er en gratis Scala til backendudvikling og funktionel programmering-lektion på CoddyKit. Dette er lektion 4 af 4. Du kan læse hele lektionen gratis nedenfor — og derefter øve dig praktisk i browseren med en indbygget kodeeditor og en AI-vejleder, der er tilgængelig døgnet rundt. Den er en del af læringsforløbet i Scala til backendudvikling og funktionel programmering, og dine fremskridt synkroniseres på tværs af nettet og CoddyKit-appen. Scala til backendudvikling og funktionel programmering-kurset indeholder 4 lektioner i alt.
Begrænsningen ved @tailrec
@tailrec optimerer kun en funktion, der direkte kalder sig selv. Den kan ikke hjælpe med gensidig rekursion (to funktioner, der kalder hinanden), som stadig vokser på stakken. Trampolining løser dette.
Problemet med gensidig rekursion
Overvej isEven og isOdd, der er defineret ud fra hinanden. For et stort tal giver dette stakoverløb, og ingen af dem kan markeres med @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))
}
}Hvad er en trampoline?
En trampoline omdanner rekursive kald til data. I stedet for at kalde sig selv returnerer en funktion en beskrivelse af det næste trin. En driverløkke kører gentagne gange disse trin og holder stakken flad.
TailRec i standardbiblioteket
Scala leverer scala.util.control.TailCalls med typen TailRec. Brug done(x) til et endeligt resultat og tailcall(...) til at udskyde det næste kald.
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 og tailcall
De to byggesten:
done(value)indpakker et endeligt svar.tailcall(expr)udskyder et kald, der returnerer enTailRec.
Et kald til .result kører trampoline-løkken og frembringer værdien.
Sikkerhed mod stakoverløb
Fordi hvert tailcall giver kontrollen tilbage til driverløkken i stedet for at indlejre et Java-kald, vokser JVM-stakken aldrig med rekursionsdybden. Eksemplet ovenfor håndterer 100.000 trin uden stakoverløb.
Trampolining af selvrekursion
Trampoliner fungerer også for almindelig dyb selvrekursion, når du ikke nemt kan bruge en akkumulator. Her forbliver en dyb nedtælling sikker for stakken.
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)
}
}Kombination af resultater med flatMap
TailRec understøtter map og flatMap, så du kan udføre arbejde efter et udskudt kald og stadig være sikker for stakken.
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)
}
}Sådan fungerer driverløkken
Konceptuelt kører .result en løkke: hent det aktuelle trin; hvis det er done, returnér dets værdi; hvis det er et udskudt kald, evaluer ét lag og fortsæt. Alt sammen med konstant stakplads.
Trampolining i effektbiblioteker
Biblioteker som Cats Effect og ZIO trampolinerer deres flatMap-kæder internt. Derfor kan du opbygge dybt indlejrede effektprogrammer uden stakoverløb. Trampolining er grundlaget for staksikre funktionelle effekter.
Hvornår du bør bruge trampolining
Brug en trampoline når:
- Du har gensidig rekursion, som ikke kan være én enkelt hale-rekursiv funktion.
- Rekursionen er for dyb til stakken, og en accumulator ikke passer.
Ved simpel selvrekursion bør du først foretrække @tailrec med en accumulator.
Hurtigt tjek
Test din forståelse af trampolining.
Opsummering
Du har lært om trampolining:
- Det gør gensidig og meget dyb rekursion sikker for stakken.
- Brug
TailCalls:done(x)ogtailcall(...), og derefter.result. TailRecunderstøttermap/flatMap.- Det danner grundlaget for effektbiblioteker, der er sikre for stakken.
Lær Scala med en AI-underviser — gratis
Skriv og kør rigtig kode i din browser, få øjeblikkelig hjælp fra en AI-underviser døgnet rundt, og fortsæt, hvor du slap, på web eller i appen.
- Kurser
- 39
- Lektioner
- 143
Ofte stillede spørgsmål
Er lektionen “Trampolining” gratis?
Ja — hele teksten til “Trampolining” kan læses gratis her på nettet. Hvis du vil øve dig interaktivt med en indbygget kodeeditor og en AI-vejleder døgnet rundt og få adgang til resten af Scala til backendudvikling og funktionel programmering-kurset, skal du opgradere til CoddyKit PRO. Scala til backendudvikling og funktionel programmering-kurset indeholder 4 lektioner i alt.
Hvad lærer jeg i “Trampolining”?
Stack-sikker rekursion Du øver dig i Scala til backendudvikling og funktionel programmering med praktisk kode, som du kører direkte i browseren, og en AI-vejleder døgnet rundt besvarer dine spørgsmål, mens du arbejder dig gennem lektionen.
Skal jeg have erfaring for at begynde på Scala til backendudvikling og funktionel programmering?
Der kræves ingen tidligere erfaring. Scala til backendudvikling og funktionel programmering på CoddyKit er tilrettelagt for både begyndere og øvede, så du kan starte her eller fra begyndelsen og lære i dit eget tempo. Dette er lektion 4 af 4.
Hvor lang tid tager lektionen “Trampolining”?
De fleste CoddyKit-lektioner tager cirka 5–10 minutter. Hver lektion er kort og interaktiv, så du gør løbende fremskridt og kan fortsætte, hvor du slap – på både web og app.
Kan jeg skrive og køre kode i denne Scala til backendudvikling og funktionel programmering-lektion?
Ja. Alle Scala til backendudvikling og funktionel programmering-lektioner har en indbygget kodeeditor, så du kan skrive og køre rigtig kode direkte i din browser og få øjeblikkelig feedback fra AI – uden lokal opsætning.