Trampolining
Recursión segura para la pila
Trampolining es una lección gratuita de Scala for Backend Engineering & Functional Programming en CoddyKit. Esta es la lección 4 de 4. Puedes leer la lección completa abajo gratuitamente — luego la practicas en el navegador con un editor de código integrado y un tutor de IA 24/7. Forma parte de la ruta de aprendizaje de Scala for Backend Engineering & Functional Programming, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de Scala for Backend Engineering & Functional Programming incluye 4 lecciones en total.
El límite de @tailrec
@tailrec solo optimiza una función que se llama directamente a sí misma. No puede ayudar con la recursión mutua (dos funciones que se llaman entre sí), que sigue haciendo crecer la pila. El trampolín resuelve este problema.
El problema de la recursión mutua
Considere isEven y isOdd, definidas en función la una de la otra. Con un número grande se desborda la pila y ninguna de las dos puede marcarse con @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))
}
}¿Qué es un trampolín?
Un trampolín convierte las llamadas recursivas en datos. En lugar de llamarse a sí misma, una función devuelve una descripción del paso siguiente. Un bucle controlador ejecuta estos pasos repetidamente y mantiene plana la pila.
TailRec en la biblioteca estándar
Scala proporciona scala.util.control.TailCalls con el tipo TailRec. Utilice done(x) para indicar un resultado final y tailcall(...) para posponer la llamada siguiente.
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 y tailcall
Los dos componentes básicos:
done(value)envuelve una respuesta final.tailcall(expr)pospone una llamada que devuelve unTailRec.
Al llamar a .result se ejecuta el bucle del trampolín y se obtiene el valor.
Seguridad frente al desbordamiento de pila
Como cada tailcall devuelve el control al bucle controlador en lugar de anidar una llamada de Java, la pila de la JVM nunca crece con la profundidad de la recursión. El ejemplo anterior gestiona 100 000 pasos sin desbordarse.
Trampolines para la autorrecursión
Los trampolines también funcionan con la autorrecursión profunda habitual cuando no resulta fácil utilizar un acumulador. Aquí una cuenta atrás profunda mantiene la seguridad frente al desbordamiento de pila.
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)
}
}Combinar resultados con flatMap
TailRec admite map y flatMap, por lo que puede realizar trabajo después de una llamada pospuesta sin perder la seguridad frente al desbordamiento de pila.
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)
}
}Cómo funciona el bucle controlador
Conceptualmente, .result ejecuta un bucle: toma el paso actual; si es done, devuelve su valor; si es una llamada pospuesta, evalúa un nivel y continúa. Todo ello utilizando un espacio de pila constante.
Trampolines en las bibliotecas de efectos
Bibliotecas como Cats Effect y ZIO aplican trampolines internamente a sus cadenas de flatMap, por lo que puede construir programas de efectos profundamente anidados sin desbordar la pila. Los trampolines son la base de los efectos funcionales seguros frente al desbordamiento de pila.
Cuándo utilizar un trampolín
Utilice un trampolín cuando:
- Tenga una recursión mutua que no pueda convertirse en una única función recursiva de cola.
- La recursión sea demasiado profunda para la pila y no sea posible utilizar un acumulador.
Para una autorrecursión sencilla, prefiera primero @tailrec con un acumulador.
Comprobación rápida
Compruebe su comprensión de los trampolines.
Resumen
Ha aprendido los trampolines:
- Hacen que la recursión mutua y la recursión muy profunda sean seguras frente al desbordamiento de pila.
- Utilice
TailCalls:done(x)ytailcall(...), seguidos de.result. TailRecadmitemap/flatMap.- Son la base de las bibliotecas de efectos seguras frente al desbordamiento de pila.
Preguntas frecuentes
¿La lección «Trampolining» es gratis?
Sí — el texto completo de «Trampolining» es gratis para leer aquí en la web. Para practicarla de forma interactiva (editor de código integrado y tutor de IA 24/7) y desbloquear el resto del curso de Scala for Backend Engineering & Functional Programming, actualiza a CoddyKit PRO. El curso de Scala for Backend Engineering & Functional Programming incluye 4 lecciones en total.
¿Qué aprenderé en «Trampolining»?
Recursión segura para la pila Practicas Scala for Backend Engineering & Functional Programming con código real que ejecutas directamente en el navegador, y un tutor de IA 24/7 responde tus preguntas mientras trabajas en la lección.
¿Necesito experiencia previa para empezar Scala for Backend Engineering & Functional Programming?
No se requiere experiencia previa. Scala for Backend Engineering & Functional Programming en CoddyKit está estructurado para principiantes hasta estudiantes avanzados, así que puedes empezar aquí o desde el inicio y avanzar a tu ritmo. Esta es la lección 4 de 4.
¿Cuánto tiempo toma la lección «Trampolining»?
La mayoría de las lecciones de CoddyKit toman alrededor de 5–10 minutos. Cada una es compacta e interactiva, así que avanzas constantemente y retomas exactamente por donde dejaste en la web y la app.
¿Puedo escribir y ejecutar código en esta lección de Scala for Backend Engineering & Functional Programming?
Sí. Cada lección de Scala for Backend Engineering & Functional Programming incluye un editor de código integrado, así que escribes y ejecutas código real directamente en tu navegador y obtienes retroalimentación instantánea de IA — sin configuración local necesaria.