Funções tailrec
Otimize a recursão
Funções tailrec é uma aula grátis de Kotlin Academy no CoddyKit. Esta é a aula 3 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 Kotlin Academy, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de Kotlin Academy inclui 4 aulas no total.
O que é recursão de cauda
Uma função é recursiva de cauda quando sua chamada recursiva é a última operação. O Kotlin pode então otimizá-la como um laço, evitando o estouro da pilha.
tailrec fun countdown(n: Int) {
if (n < 0) return
println(n)
countdown(n - 1)
}
fun main() {
countdown(3)
}O modificador tailrec
Adicione o modificador tailrec para que o compilador reescreva a recursão como iteração, usando espaço constante na pilha.
tailrec fun sum(n: Int, acc: Int = 0): Int {
if (n == 0) return acc
return sum(n - 1, acc + n)
}
fun main() {
println(sum(100))
}O padrão do acumulador
Para transformar a recursão em recursão de cauda, mantenha os resultados em um parâmetro acumulador, para que nada reste a ser calculado depois da chamada.
tailrec fun factorial(n: Int, acc: Long = 1): Long {
if (n <= 1) return acc
return factorial(n - 1, acc * n)
}
fun main() {
println(factorial(10))
}Por que a chamada deve ser a última
Se algo acontecer depois da chamada recursiva, como multiplicar o resultado dela, a chamada não estará na posição de cauda e não poderá ser otimizada.
tailrec fun length(s: String, acc: Int = 0): Int {
if (s.isEmpty()) return acc
return length(s.drop(1), acc + 1)
}
fun main() {
println(length("hello"))
}Contraexemplo de recursão que não é de cauda
Este fatorial NOT é recursivo de cauda, porque a multiplicação ocorre depois que a chamada retorna. Marcá-lo com tailrec geraria um aviso.
fun badFactorial(n: Int): Long {
if (n <= 1) return 1
return n * badFactorial(n - 1)
}
fun main() {
println(badFactorial(5))
}Evitando o estouro da pilha
Uma recursão profunda sem tailrec pode causar uma falha. Com ele, até entradas grandes são executadas usando espaço constante na pilha.
tailrec fun count(n: Int, acc: Int = 0): Int {
if (n == 0) return acc
return count(n - 1, acc + 1)
}
fun main() {
println(count(100000))
}Verificação pelo compilador
Se você marcar uma função com tailrec, mas a chamada não estiver na posição de cauda, o compilador emitirá um aviso e não fará a otimização. Leve o aviso a sério.
tailrec fun gcd(a: Int, b: Int): Int {
if (b == 0) return a
return gcd(b, a % b)
}
fun main() {
println(gcd(48, 18))
}Recursão de cauda versus laço
Uma função tailrec é compilada aproximadamente no mesmo código que o laço equivalente, mas expressa o algoritmo de forma recursiva.
tailrec fun powerOfTwo(n: Int, acc: Long = 1): Long {
if (n == 0) return acc
return powerOfTwo(n - 1, acc * 2)
}
fun main() {
println(powerOfTwo(10))
}Vários parâmetros
As funções recursivas de cauda geralmente passam vários parâmetros de estado, todos atualizados na chamada recursiva.
tailrec fun fib(n: Int, a: Long = 0, b: Long = 1): Long {
if (n == 0) return a
return fib(n - 1, b, a + b)
}
fun main() {
println(fib(20))
}Invertendo com tailrec
Um acumulador pode construir um resultado como uma cadeia de caracteres invertida.
tailrec fun reverse(s: String, acc: String = ""): String {
if (s.isEmpty()) return acc
return reverse(s.drop(1), s.first() + acc)
}
fun main() {
println(reverse("kotlin"))
}Uma busca prática
As buscas iterativas se adaptam facilmente à recursão de cauda.
tailrec fun indexOf(list: List<Int>, target: Int, i: Int = 0): Int {
if (i >= list.size) return -1
if (list[i] == target) return i
return indexOf(list, target, i + 1)
}
fun main() {
println(indexOf(listOf(5, 6, 7), 7))
}Verificação rápida
Teste sua compreensão sobre funções tailrec.
Recapitulação
Você aprendeu sobre funções tailrec:
tailrectransforma a recursão na posição de cauda em um laço, evitando o estouro da pilha.- A chamada recursiva deve ser a última operação.
- Use um parâmetro acumulador para alcançar a forma de cauda.
- O compilador avisa quando uma função não pode ser otimizada.
tailrec fun sum(n: Int, acc: Int = 0): Int =
if (n == 0) acc else sum(n - 1, acc + n)
fun main() {
println(sum(50))
}Perguntas Frequentes
A aula “Funções tailrec” é grátis?
Sim — o texto completo de “Funções tailrec” é 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 Kotlin Academy, atualize para CoddyKit PRO. O curso de Kotlin Academy inclui 4 aulas no total.
O que vou aprender em “Funções tailrec”?
Otimize a recursão Você pratica Kotlin Academy 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 Kotlin Academy?
Nenhuma experiência prévia é necessária. Kotlin Academy 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 3 de 4.
Quanto tempo leva a aula “Funções tailrec”?
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 Kotlin Academy?
Sim. Cada aula de Kotlin Academy 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.