Fundamentos da recursão
Funções recursivas.
Fundamentos da recursão é 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 é recursão?
Recursão ocorre quando uma função chama a si mesma para resolver uma versão menor do mesmo problema. Ela se adapta naturalmente à programação funcional, substituindo muitos laços por definições autorreferentes.
Duas partes essenciais
Toda função recursiva correta precisa de:
- Um caso-base que interrompa a recursão.
- Um caso recursivo que avance em direção ao caso-base.
Sem um caso-base alcançável, a recursão será executada indefinidamente.
Fatorial
O exemplo clássico: n! = n * (n-1)!, com 0! = 1 como caso-base.
object Main {
def factorial(n: Int): Int =
if (n <= 1) 1
else n * factorial(n - 1)
def main(args: Array[String]): Unit = {
println(factorial(5))
}
}Rastreando as Chamadas
Cada chamada recursiva pausa e aguarda o resultado interno. factorial(3) se expande para 3 * (2 * (1)). As multiplicações acontecem à medida que as chamadas retornam.
object Main {
def factorial(n: Int): Int = {
println(s"entering factorial($n)")
if (n <= 1) 1 else n * factorial(n - 1)
}
def main(args: Array[String]): Unit = {
println("result = " + factorial(3))
}
}Soma de uma Lista
Recursão sobre uma lista: a soma é a cabeça mais a soma da cauda, sendo que a soma da lista vazia é zero.
object Main {
def sum(xs: List[Int]): Int = xs match {
case Nil => 0
case h :: t => h + sum(t)
}
def main(args: Array[String]): Unit = {
println(sum(List(1, 2, 3, 4)))
}
}Comprimento de uma Lista
O mesmo padrão calcula o comprimento: a lista vazia tem comprimento 0; caso contrário, é 1 mais o comprimento da cauda.
object Main {
def length[A](xs: List[A]): Int = xs match {
case Nil => 0
case _ :: t => 1 + length(t)
}
def main(args: Array[String]): Unit = {
println(length(List("a", "b", "c")))
}
}A Pilha de Chamadas
Cada chamada recursiva pendente usa um quadro de pilha. Uma recursão profunda acumula muitos quadros. Para entradas muito grandes, isso pode esgotar a pilha e lançar um StackOverflowError.
Fibonacci
Alguns problemas se ramificam em várias chamadas recursivas. Fibonacci chama a si mesmo duas vezes, o que é elegante, mas tem custo exponencial.
object Main {
def fib(n: Int): Int =
if (n < 2) n
else fib(n - 1) + fib(n - 2)
def main(args: Array[String]): Unit = {
println(fib(10))
}
}Invertendo uma Lista
A recursão pode construir novas estruturas: reverse acrescenta a cabeça depois de inverter a cauda.
object Main {
def reverse[A](xs: List[A]): List[A] = xs match {
case Nil => Nil
case h :: t => reverse(t) :+ h
}
def main(args: Array[String]): Unit = {
println(reverse(List(1, 2, 3)))
}
}Recursão versus Iteração
Os laços alteram um contador; a recursão expressa o problema de forma declarativa. Ambas são abordagens válidas. A recursão é especialmente adequada para dados em forma de árvore e para dividir e conquistar, mas a recursão ingênua pode causar estouro de pilha em entradas lineares grandes.
Máximo Divisor Comum
O algoritmo de Euclides é naturalmente recursivo e converge rapidamente.
object Main {
def gcd(a: Int, b: Int): Int =
if (b == 0) a else gcd(b, a % b)
def main(args: Array[String]): Unit = {
println(gcd(48, 18))
}
}Verificação Rápida
Teste seus conhecimentos fundamentais sobre recursão.
Recapitulação
Você aprendeu os fundamentos da recursão:
- Toda função recursiva precisa de um caso-base e de um caso recursivo.
- Cada chamada pendente usa um quadro de pilha; uma recursão profunda pode causar estouro.
- A recursão expressa naturalmente algoritmos para listas e árvores.
A seguir, você tornará a recursão segura para a pilha com a anotação @tailrec.
Perguntas Frequentes
A aula “Fundamentos da recursão” é grátis?
Sim — o texto completo de “Fundamentos da recursão” é 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 “Fundamentos da recursão”?
Funções 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 “Fundamentos da recursão”?
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
- Fundamentos da recursão
- A anotação tailrec
- Padrão acumulador
- Trampolim