Pensando recursivamente
Casos-base e etapas recursivas.
Pensando recursivamente é uma aula grátis de Scala for Backend Engineering & Functional Programming no CoddyKit. Esta é a aula 1 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 que significa recursão
Recursão ocorre quando uma função chama a si mesma para resolver uma versão menor do mesmo problema.
No Scala, a recursão combina naturalmente com a programação funcional porque permite expressar laços sem variáveis mutáveis.
Toda função recursiva precisa de duas coisas: uma forma de parar e uma forma de reduzir o problema.
Primeiro, o caso-base
O caso-base é a entrada mais simples que a função consegue responder diretamente, sem fazer nova recursão.
Sem um caso-base, a função chamaria a si mesma para sempre e falharia por estouro da pilha.
Sempre defina o caso-base antes da etapa recursiva.
def countdown(n: Int): Unit =
if (n < 0) () // base case: stop
else {
println(n)
countdown(n - 1) // recursive step
}Uma primeira função recursiva
Aqui está um programa completo que soma os números de 1 a n.
O caso-base retorna 0; o caso recursivo adiciona n à soma de tudo que está abaixo dele.
def sum(n: Int): Int =
if (n == 0) 0
else n + sum(n - 1)
@main def run(): Unit =
println(sum(5)) // 15Rastreando as chamadas
Para entender a recursão, expanda as chamadas manualmente.
sum(3) se torna 3 + sum(2), que se torna 3 + 2 + sum(1), depois 3 + 2 + 1 + sum(0).
Somente quando sum(0) retorna 0 é que a cadeia volta a se reduzir a um único valor: 6.
// sum(3)
// = 3 + sum(2)
// = 3 + (2 + sum(1))
// = 3 + (2 + (1 + sum(0)))
// = 3 + (2 + (1 + 0))
// = 6Recursão em listas
As listas são recursivas por natureza: uma lista é vazia (Nil) ou tem uma cabeça seguida por uma cauda menor.
Essa estrutura corresponde diretamente às funções recursivas. A lista vazia é o caso-base; a cabeça mais a recursão sobre a cauda formam a etapa recursiva.
def length[A](xs: List[A]): Int = xs match {
case Nil => 0
case _ :: t => 1 + length(t)
}Correspondência de padrões na cauda
O padrão :: divide uma lista não vazia em sua cabeça e sua cauda.
Cada chamada recursiva trabalha com uma lista estritamente menor, garantindo o avanço em direção a Nil.
Essa é a forma canônica de percorrer uma lista recursivamente em Scala.
def sumList(xs: List[Int]): Int = xs match {
case Nil => 0
case h :: t => h + sumList(t)
}
@main def run(): Unit =
println(sumList(List(1, 2, 3, 4))) // 10Duas chamadas recursivas
Alguns problemas se ramificam em mais de uma chamada recursiva.
O exemplo clássico é Fibonacci, em que cada valor depende dos dois valores anteriores.
Esta versão ingênua é simples, mas lenta, porque recalcula os mesmos valores muitas vezes.
def fib(n: Int): Int =
if (n < 2) n
else fib(n - 1) + fib(n - 2)
@main def run(): Unit =
println(fib(7)) // 13O custo da pilha
Cada chamada recursiva adiciona um quadro à pilha de chamadas, que precisa esperar a chamada interna retornar.
Em uma recursão muito profunda, isso pode esgotar a pilha e lançar um StackOverflowError.
Contar a profundidade, e não apenas o tamanho, ajuda a prever esse risco.
// This would overflow the stack for large n:
// def deep(n: Int): Int =
// if (n == 0) 0 else 1 + deep(n - 1)
// deep(1000000) // StackOverflowErrorReduzindo em direção ao caso-base
O invariante fundamental da recursão é que cada chamada deve se aproximar do caso-base.
Se o argumento não ficar menor ou nunca alcançar a condição de parada, a recursão nunca termina.
Verifique isso antes de executar qualquer coisa.
def reverse[A](xs: List[A]): List[A] = xs match {
case Nil => Nil
case h :: t => reverse(t) :+ h // t is smaller than xs
}Recursão versus laços
O código imperativo usa laços while com contadores mutáveis; o código funcional usa recursão com valores imutáveis.
Ambos podem expressar os mesmos cálculos, mas a recursão descreve a estrutura dos dados de forma mais direta.
Em Scala, você frequentemente preferirá a recursão ou funções de ordem superior a laços simples.
// Imperative
var total = 0
for (i <- 1 to 5) total += i
// Recursive
def sum(n: Int): Int = if (n == 0) 0 else n + sum(n - 1)Projetando uma solução recursiva
Uma receita confiável: identifique o caso-base, suponha que a chamada recursiva já funcione com a entrada menor e depois combine a cabeça com esse resultado.
Esse salto de confiança é o coração do raciocínio recursivo. Você confia na chamada menor e trata apenas uma etapa.
def maxOf(xs: List[Int]): Int = xs match {
case h :: Nil => h
case h :: t => math.max(h, maxOf(t))
}
@main def run(): Unit =
println(maxOf(List(3, 9, 2, 7))) // 9Verificação rápida
Teste sua compreensão da estrutura recursiva.
Recapitulação
A recursão resolve um problema reduzindo-o a uma instância menor de si mesmo.
Toda função recursiva precisa de um caso-base para parar e de uma etapa recursiva que reduza a entrada em direção a esse caso-base.
As listas, com sua estrutura baseada em Nil, cabeça e cauda, são um ambiente ideal para praticar o raciocínio recursivo. Observe a profundidade da pilha em entradas muito grandes.
Aprenda Scala com um tutor de IA — grátis
Escreva e execute código real no seu navegador, obtenha ajuda instantânea de um tutor de IA 24/7 e continue de onde parou na web ou no app.
- Cursos
- 39
- Aulas
- 143
Perguntas Frequentes
A aula “Pensando recursivamente” é grátis?
Sim — o texto completo de “Pensando recursivamente” é 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 “Pensando recursivamente”?
Casos-base e etapas recursivas. 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 1 de 4.
Quanto tempo leva a aula “Pensando recursivamente”?
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.
Todas as aulas deste curso
- Pensando recursivamente
- Padrões de acumuladores
- foldLeft e foldRight
- reduce e agregação