Trampolining
Stakktrygg rekursjon
Trampolining er en gratis leksjon i Scala for backendutvikling og funksjonell programmering på CoddyKit. Dette er leksjon 4 av 4. Du kan lese hele leksjonen gratis nedenfor – og deretter øve praktisk i nettleseren med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt. Den er en del av læringsløpet i Scala for backendutvikling og funksjonell programmering, og fremdriften din synkroniseres mellom nettet og CoddyKit-appen. Kurset i Scala for backendutvikling og funksjonell programmering inneholder totalt 4 leksjoner.
Begrensningen til @tailrec
@tailrec optimaliserer bare en funksjon som kaller seg selv direkte. Den kan ikke hjelpe med gjensidig rekursjon (to funksjoner som kaller hverandre), som fortsatt bygger opp stakken. Trampolinisering løser dette.
Problemet med gjensidig rekursjon
Tenk på isEven og isOdd, som er definert ved hjelp av hverandre. For et stort tall tømmer dette stakken, og ingen av funksjonene kan merkes 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))
}
}Hva er en trampoline?
En trampoline gjør rekursive kall om til data. I stedet for å kalle seg selv returnerer funksjonen en beskrivelse av neste trinn. En driverløkke kjører disse trinnene gjentatte ganger og holder stakken flat.
TailRec i standardbiblioteket
Scala tilbyr scala.util.control.TailCalls med typen TailRec. Bruk done(x) for et endelig resultat og tailcall(...) for å utsette neste kall.
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 byggesteinene:
done(value)pakker inn et endelig svar.tailcall(expr)utsetter et kall som returnerer enTailRec.
Et kall til .result kjører trampolineløkken og produserer verdien.
Stakksikkerhet
Fordi hvert tailcall gir kontrollen tilbake til driverløkken i stedet for å nøste et Java-kall, vokser JVM-stakken aldri med rekursjonsdybden. Eksempelet ovenfor håndterer 100 000 trinn uten stack overflow.
Trampolinisering av selvrekursjon
Trampoliner fungerer også for vanlig dyp selvrekursjon når det er vanskelig å bruke en akkumulator. Her forblir en dyp nedtelling stakksikker.
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)
}
}Kombinere resultater med flatMap
TailRec støtter map og flatMap, slik at De kan utføre arbeid etter et utsatt kall og samtidig være stakksikker.
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)
}
}Slik fungerer driverløkken
Konseptuelt kjører .result en løkke: Hent det gjeldende trinnet; hvis det er done, returner verdien; hvis det er et utsatt kall, evaluer ett nivå og fortsett. Alt med konstant stakkplass.
Trampolinisering i effektbiblioteker
Biblioteker som Cats Effect og ZIO trampolinerer flatMap-kjedene sine internt. Derfor kan De bygge dypt nøstede effektprogrammer uten stack overflow. Trampolinisering er grunnlaget for stakksikre funksjonelle effekter.
Når bør De bruke trampolinisering
Bruk en trampoline når:
- De har gjensidig rekursjon som ikke kan uttrykkes som én halerekursiv funksjon.
- Rekursjonen er for dyp for stakken, og en akkumulator passer ikke.
For enkel selvrekursjon bør De først foretrekke @tailrec med en akkumulator.
Hurtigsjekk
Test forståelsen Deres av trampolining.
Oppsummering
De har lært om trampolining:
- Det gjør gjensidig og svært dyp rekursjon trygg for stakken.
- Bruk
TailCalls:done(x)ogtailcall(...), og deretter.result. TailRecstøttermap/flatMap.- Det danner grunnlaget for stakksikre effektbiblioteker.
Lær deg Scala med en AI-veileder – gratis
Skriv og kjør ekte kode i nettleseren, få umiddelbar hjelp fra en AI-veileder som er tilgjengelig døgnet rundt, og fortsett der du slapp – på nettet eller i appen.
- Kurs
- 39
- Leksjoner
- 143
Ofte stilte spørsmål
Er leksjonen «Trampolining» gratis?
Ja – hele teksten i «Trampolining» er gratis å lese her på nettet. For å øve interaktivt med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt, og for å låse opp resten av Scala for backendutvikling og funksjonell programmering-kurset, kan du oppgradere til CoddyKit PRO. Kurset i Scala for backendutvikling og funksjonell programmering inneholder totalt 4 leksjoner.
Hva lærer jeg i «Trampolining»?
Stakktrygg rekursjon Du øver på Scala for backendutvikling og funksjonell programmering med praktisk kode som du kjører direkte i nettleseren, mens en AI-veileder som er tilgjengelig døgnet rundt, svarer på spørsmålene dine mens du jobber deg gjennom leksjonen.
Trenger jeg erfaring for å begynne med Scala for backendutvikling og funksjonell programmering?
Ingen tidligere erfaring er nødvendig. Scala for backendutvikling og funksjonell programmering på CoddyKit er lagt opp for både nybegynnere og viderekomne, så De kan begynne her eller helt fra start og lære i Deres eget tempo. Dette er leksjon 4 av 4.
Hvor lang tid tar leksjonen «Trampolining»?
De fleste CoddyKit-leksjoner tar omtrent 5–10 minutter. Hver leksjon er kort og interaktiv, slik at De gjør jevne fremskritt og kan fortsette akkurat der De slapp – både på nettet og i appen.
Kan jeg skrive og kjøre kode i denne Scala for backendutvikling og funksjonell programmering-leksjonen?
Ja. Alle Scala for backendutvikling og funksjonell programmering-leksjoner har en innebygd kodeeditor, slik at De kan skrive og kjøre ekte kode direkte i nettleseren og få umiddelbar tilbakemelding fra AI – uten lokal konfigurering.