Trampolining
Stackveilige recursie
Trampolining is een gratis Scala voor backend-engineering en functioneel programmeren-les op CoddyKit. Dit is les 4 van 4. Je kunt de volledige les hieronder gratis lezen en daarna in de browser praktisch oefenen met een ingebouwde code-editor en een AI-begeleider die 24/7 beschikbaar is. Deze les maakt deel uit van het leertraject Scala voor backend-engineering en functioneel programmeren. Je voortgang wordt gesynchroniseerd op het web en in de CoddyKit-app. De cursus Scala voor backend-engineering en functioneel programmeren bevat in totaal 4 lessen.
De beperking van @tailrec
@tailrec optimaliseert alleen een functie die rechtstreeks zichzelf aanroept. De annotatie helpt niet bij wederzijdse recursie (twee functies die elkaar aanroepen), waarbij de stack blijft groeien. Trampolines lossen dit op.
Het probleem met wederzijdse recursie
Bekijk isEven en isOdd, die in termen van elkaar zijn gedefinieerd. Bij een groot getal loopt dit over de stack, en geen van beide functies kan worden gemarkeerd met @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))
}
}Wat is een trampoline
Een trampoline zet recursieve aanroepen om in gegevens. In plaats van zichzelf aan te roepen, retourneert een functie een beschrijving van de volgende stap. Een lus voert deze stappen herhaaldelijk uit, zodat de stack vlak blijft.
TailRec in de standaardbibliotheek
Scala biedt scala.util.control.TailCalls met het type TailRec. Gebruik done(x) voor een eindresultaat en tailcall(...) om de volgende aanroep uit te stellen.
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 en tailcall
De twee bouwstenen:
done(value)verpakt een definitief antwoord.tailcall(expr)stelt een aanroep uit die eenTailRecretourneert.
Een aanroep van .result voert de trampoline-lus uit en produceert de waarde.
Stackveiligheid
Omdat elke tailcall de controle teruggeeft aan de lus in plaats van een Java-aanroep te nesten, groeit de JVM-stack niet mee met de recursiediepte. Het bovenstaande voorbeeld verwerkt 100.000 stappen zonder overloop.
Zelfrecursie met trampolines
Trampolines werken ook voor gewone diepe zelfrecursie wanneer je niet eenvoudig een accumulator kunt gebruiken. Hier blijft een diepe aftelling stackveilig.
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)
}
}Resultaten combineren met flatMap
TailRec ondersteunt map en flatMap, zodat je na een uitgestelde aanroep werk kunt uitvoeren en toch stackveilig blijft.
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)
}
}Hoe de lus in de driver werkt
Conceptueel voert .result een lus uit: neem de huidige stap; als dit done is, retourneer dan de waarde; als het een uitgestelde aanroep is, evalueer dan één laag en ga verder. Dit gebeurt allemaal met een constante hoeveelheid stackruimte.
Trampolines in effectbibliotheken
Bibliotheken zoals Cats Effect en ZIO voorzien hun flatMap-ketens intern van trampolines. Daarom kun je diep geneste effectprogramma's bouwen zonder stackoverloop. Trampolines vormen de basis van stackveilige functionele effecten.
Wanneer gebruik je een trampoline
Gebruik een trampoline wanneer:
- je wederzijdse recursie hebt die niet in één staartrecursieve functie kan worden ondergebracht.
- de recursie te diep is voor de stack en een accumulator niet past.
Geef bij eenvoudige zelfrecursie eerst de voorkeur aan @tailrec met een accumulator.
Korte controle
Test je begrip van trampolines.
Samenvatting
Je hebt trampolines geleerd:
- Ze maken wederzijdse en zeer diepe recursie stackveilig.
- Gebruik
TailCalls:done(x)entailcall(...), gevolgd door.result. TailRecondersteuntmap/flatMap.- Ze vormen de basis voor stackveilige bibliotheken voor effecten.
Leer Scala met een AI-tutor — gratis
Schrijf echte code en voer die uit in je browser, krijg direct hulp van een AI-tutor die 24/7 beschikbaar is en ga verder waar je gebleven bent op het web of in de app.
- Cursussen
- 39
- Lessen
- 143
Veelgestelde vragen
Is de les “Trampolining” gratis?
Ja — de volledige tekst van “Trampolining” kun je hier gratis op het web lezen. Als je interactief wilt oefenen met een ingebouwde code-editor en een AI-begeleider die 24/7 beschikbaar is, en de rest van de cursus Scala voor backend-engineering en functioneel programmeren wilt ontgrendelen, kun je upgraden naar CoddyKit PRO. De cursus Scala voor backend-engineering en functioneel programmeren bevat in totaal 4 lessen.
Wat leer ik in “Trampolining”?
Stackveilige recursie Je oefent met Scala voor backend-engineering en functioneel programmeren door code rechtstreeks in de browser uit te voeren. Een AI-begeleider die 24/7 beschikbaar is beantwoordt je vragen terwijl je de les doorwerkt.
Heb ik ervaring nodig om met Scala voor backend-engineering en functioneel programmeren te beginnen?
Ervaring vooraf is niet nodig. Scala voor backend-engineering en functioneel programmeren op CoddyKit is opgebouwd voor beginners tot gevorderden, zodat je hier of bij het begin kunt starten en in je eigen tempo kunt leren. Dit is les 4 van 4.
Hoe lang duurt de les “Trampolining”?
De meeste lessen van CoddyKit duren ongeveer 5–10 minuten. Elke les is kort en interactief, zodat je gestaag vooruitgaat en op het web en in de app precies verdergaat waar je was gebleven.
Kan ik code schrijven en uitvoeren in deze les over Scala voor backend-engineering en functioneel programmeren?
Ja. Elke les over Scala voor backend-engineering en functioneel programmeren bevat een ingebouwde code-editor, zodat je rechtstreeks in je browser echte code kunt schrijven en uitvoeren en direct feedback van AI krijgt — lokale installatie is niet nodig.