Trampolim
Recursão segura para a pilha.
Trampolim é uma aula grátis de Scala for Backend Engineering & Functional Programming no CoddyKit. Esta é a aula 4 de 4. Você pode ler a aula completa abaixo gratuitamente — depois pratica ao vivo no navegador com um editor de código integrado e um tutor de IA 24/7. Faz parte do caminho de aprendizado de Scala for Backend Engineering & Functional Programming, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de Scala for Backend Engineering & Functional Programming inclui 4 aulas no total.
O Limite de @tailrec
@tailrec só otimiza uma função que chama diretamente a si mesma. Ela não ajuda com a recursão mútua (duas funções que chamam uma à outra), que continua aumentando a pilha. O trampolim resolve esse problema.
O Problema da Recursão Mútua
Considere isEven e isOdd definidos um em termos do outro. Para um número grande, isso causa estouro de pilha, e nenhum dos dois pode ser marcado com @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))
}
}O que é um Trampolim?
Um trampolim transforma chamadas recursivas em dados. Em vez de chamar a si mesma, uma função retorna uma descrição da próxima etapa. Um laço controlador executa essas etapas repetidamente, mantendo a pilha estável.
TailRec na Biblioteca Padrão
Scala oferece scala.util.control.TailCalls com o tipo TailRec. Use done(x) para um resultado final e tailcall(...) para adiar a próxima chamada.
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 e tailcall
Os dois blocos de construção:
done(value)envolve uma resposta final.tailcall(expr)adia uma chamada que retorna umTailRec.
Chamar .result executa o laço do trampolim e produz o valor.
Segurança para a Pilha
Como cada tailcall devolve o controle ao laço controlador em vez de aninhar uma chamada Java, a pilha da JVM nunca cresce com a profundidade da recursão. O exemplo acima processa 100.000 etapas sem causar estouro.
Aplicando Trampolim à Autorrecursão
Os trampolins também funcionam com autorrecursão profunda comum quando não é fácil usar um acumulador. Aqui, uma contagem regressiva profunda permanece segura para a pilha.
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)
}
}Combinando Resultados com flatMap
TailRec oferece suporte a map e flatMap, permitindo realizar trabalho depois de uma chamada adiada sem perder a segurança da pilha.
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)
}
}Como Funciona o Laço Controlador
Conceitualmente, .result executa um laço: obtém a etapa atual; se ela for done, retorna seu valor; se for uma chamada adiada, avalia uma camada e continua. Tudo isso usando espaço de pilha constante.
Trampolins em Bibliotecas de Efeitos
Bibliotecas como Cats Effect e ZIO aplicam trampolins internamente às suas cadeias de flatMap; por isso, você pode construir programas de efeitos profundamente aninhados sem causar estouro de pilha. O uso de trampolins é a base dos efeitos funcionais seguros para a pilha.
Quando Usar um Trampolim
Use um trampolim quando:
- Você tiver recursão mútua que não possa ser transformada em uma única função recursiva de cauda.
- A recursão for profunda demais para a pilha e um acumulador não for adequado.
Para autorrecursão simples, prefira primeiro @tailrec com um acumulador.
Verificação Rápida
Teste sua compreensão sobre trampolins.
Recapitulação
Você aprendeu sobre trampolins:
- Eles tornam a recursão mútua e a recursão muito profunda seguras para a pilha.
- Use
TailCalls:done(x)etailcall(...), seguidos de.result. TailRecoferece suporte amap/flatMap.- Essa técnica sustenta bibliotecas de efeitos seguras para a pilha.
Perguntas Frequentes
A aula “Trampolim” é grátis?
Sim — o texto completo de “Trampolim” é grátis para ler aqui na web. Para praticá-la interativamente (um editor de código integrado e um tutor de IA 24/7) e desbloquear o restante do curso de Scala for Backend Engineering & Functional Programming, atualize para CoddyKit PRO. O curso de Scala for Backend Engineering & Functional Programming inclui 4 aulas no total.
O que vou aprender em “Trampolim”?
Recursão segura para a pilha. Você pratica Scala for Backend Engineering & Functional Programming com código prático que executa diretamente no navegador, e um tutor de IA 24/7 responde suas dúvidas enquanto trabalha na aula.
Preciso ter experiência prévia para começar Scala for Backend Engineering & Functional Programming?
Nenhuma experiência prévia é necessária. Scala for Backend Engineering & Functional Programming no CoddyKit é estruturado para alunos iniciantes até avançados, então você pode começar aqui ou desde o início e aprender no seu ritmo. Esta é a aula 4 de 4.
Quanto tempo leva a aula “Trampolim”?
A maioria das aulas CoddyKit leva cerca de 5–10 minutos. Cada uma é compacta e interativa, então você faz progresso constante e retoma exatamente de onde parou entre web e app.
Posso escrever e executar código nesta aula de Scala for Backend Engineering & Functional Programming?
Sim. Cada aula de Scala for Backend Engineering & Functional Programming inclui um editor de código integrado, então você escreve e executa código real direto no navegador e recebe feedback de IA instantaneamente — nenhuma configuração local necessária.