O que e tailrec em Kotlin?
A palavra-chave tailrec em Kotlin instrui o compilador a otimizar uma funcao recursiva transformando-a em um loop iterativo nos bastidores. Isso elimina o risco de estouro de pilha (StackOverflowError) que funcoes recursivas tradicionais apresentam quando processam grandes volumes de dados.
Recursao de cauda (tail recursion) acontece quando a chamada recursiva e a ultima operacao executada pela funcao. Nesse cenario, o compilador nao precisa manter o stack frame anterior, pois nao ha mais nenhum calculo pendente apos o retorno da chamada recursiva. O modificador tailrec garante que o compilador Kotlin realize essa otimizacao e, caso a funcao nao seja elegivel, emite um aviso em tempo de compilacao.
Sintaxe basica
A sintaxe para declarar uma funcao com tailrec e direta. Basta adicionar o modificador antes da palavra fun:
tailrec fun fatorial(n: Long, acumulador: Long = 1): Long {
if (n <= 1) return acumulador
return fatorial(n - 1, n * acumulador)
}
fun main() {
println(fatorial(20)) // 2432902008176640000
println(fatorial(50)) // funciona sem estouro de pilha
}
Observe que o parametro acumulador carrega o resultado parcial. Essa tecnica e fundamental para transformar uma recursao comum em recursao de cauda.
Comparacao com recursao tradicional
Uma implementacao recursiva classica do fatorial seria:
fun fatorialClassico(n: Long): Long {
if (n <= 1) return 1
return n * fatorialClassico(n - 1) // multiplicacao APOS a chamada recursiva
}
Nessa versao, a multiplicacao n * fatorialClassico(n - 1) acontece depois do retorno da chamada recursiva. Isso impede a otimizacao de cauda porque o compilador precisa manter cada frame na pilha para realizar a multiplicacao pendente. Com numeros grandes, isso causa StackOverflowError.
Exemplos praticos
Soma de uma lista
tailrec fun somaLista(lista: List<Int>, indice: Int = 0, acumulador: Long = 0): Long {
if (indice >= lista.size) return acumulador
return somaLista(lista, indice + 1, acumulador + lista[indice])
}
fun main() {
val numeros = (1..1_000_000).toList()
println(somaLista(numeros)) // 500000500000
}
Busca binaria recursiva
tailrec fun buscaBinaria(
lista: List<Int>,
alvo: Int,
inicio: Int = 0,
fim: Int = lista.size - 1
): Int {
if (inicio > fim) return -1
val meio = (inicio + fim) / 2
return when {
lista[meio] == alvo -> meio
lista[meio] < alvo -> buscaBinaria(lista, alvo, meio + 1, fim)
else -> buscaBinaria(lista, alvo, inicio, meio - 1)
}
}
fun main() {
val ordenada = (1..1_000_000).toList()
println(buscaBinaria(ordenada, 750_000)) // 749999
}
Fibonacci com tailrec
tailrec fun fibonacci(n: Int, a: Long = 0, b: Long = 1): Long {
if (n == 0) return a
return fibonacci(n - 1, b, a + b)
}
fun main() {
println(fibonacci(10)) // 55
println(fibonacci(50)) // 12586269025
println(fibonacci(90)) // 2880067194370816120
}
Maximo divisor comum (MDC)
tailrec fun mdc(a: Int, b: Int): Int {
if (b == 0) return a
return mdc(b, a % b)
}
fun main() {
println(mdc(48, 18)) // 6
println(mdc(1071, 462)) // 21
}
Como o compilador transforma o codigo
Quando voce marca uma funcao com tailrec, o compilador Kotlin gera bytecode equivalente a um loop while. O fatorial com tailrec, por exemplo, e compilado para algo semelhante a:
fun fatorialOtimizado(n: Long, acumulador: Long = 1): Long {
var nAtual = n
var acAtual = acumulador
while (true) {
if (nAtual <= 1) return acAtual
acAtual = nAtual * acAtual
nAtual = nAtual - 1
}
}
Essa transformacao elimina completamente a recursao no bytecode final, garantindo performance constante em termos de uso de pilha independentemente da profundidade da recursao.
Quando usar tailrec
O tailrec e indicado nas seguintes situacoes:
- Algoritmos naturalmente recursivos como travessia de arvores, busca binaria, calculo de sequencias matematicas e processamento de listas encadeadas.
- Processamento de grandes volumes de dados onde a profundidade da recursao pode ultrapassar o limite da pilha da JVM.
- Substituicao de loops complexos onde a logica recursiva e mais legivel que a iterativa equivalente.
- Programacao funcional quando voce adota um estilo funcional e quer evitar mutacao de estado sem sacrificar performance.
Quando nao usar
Nem toda funcao recursiva pode ser convertida para tail recursion. Nao use tailrec quando:
- A chamada recursiva nao e a ultima operacao da funcao.
- Ha mais de uma chamada recursiva no corpo da funcao (como na versao classica de Fibonacci sem acumulador).
- A funcao usa blocos try/catch envolvendo a chamada recursiva.
- A simplicidade do loop iterativo torna a recursao desnecessaria.
Erros comuns
Recursao que nao e de cauda
// ERRADO: o compilador emite aviso
tailrec fun somaAte(n: Int): Int {
if (n <= 0) return 0
return n + somaAte(n - 1) // operacao APOS a chamada recursiva
}
O compilador Kotlin emite o aviso: “A function is marked as tail-recursive but no tail calls are found.” A funcao compila, mas sem a otimizacao desejada.
Correcao com acumulador
// CORRETO: recursao de cauda com acumulador
tailrec fun somaAte(n: Int, acumulador: Int = 0): Int {
if (n <= 0) return acumulador
return somaAte(n - 1, acumulador + n)
}
Chamar a funcao dentro de expressoes
// ERRADO: chamada dentro de when com operacoes
tailrec fun processar(n: Int): String {
return when {
n <= 0 -> "fim"
n % 2 == 0 -> "par: " + processar(n - 1) // concatenacao apos chamada
else -> processar(n - 1)
}
}
Nesse caso, apenas o branch else e uma chamada de cauda valida. O branch com concatenacao impede a otimizacao completa.
Uso com funcoes de extensao
O tailrec tambem funciona com funcoes de extensao, desde que a chamada recursiva siga as regras de cauda:
tailrec fun List<Int>.somarElementos(indice: Int = 0, acumulador: Long = 0): Long {
if (indice >= this.size) return acumulador
return this.somarElementos(indice + 1, acumulador + this[indice])
}
Termos relacionados
- Recursao: tecnica onde uma funcao chama a si mesma para resolver subproblemas menores.
- Stack overflow: erro que ocorre quando a pilha de execucao excede seu limite por excesso de chamadas empilhadas.
- Funcao de ordem superior: funcoes que recebem ou retornam outras funcoes, frequentemente combinadas com recursao.
- Programacao funcional: paradigma que favorece imutabilidade e recursao sobre loops e estado mutavel.
- inline: modificador que instrui o compilador a copiar o corpo da funcao no ponto de chamada, outra forma de otimizacao em Kotlin.
- Sequence: tipo lazy de Kotlin que pode substituir recursao para processamento de colecoes grandes.
Conclusao
O modificador tailrec e uma ferramenta valiosa para quem escreve Kotlin em estilo funcional. Ele permite expressar algoritmos recursivos de forma clara e segura, sem risco de estouro de pilha. A chave para usa-lo corretamente e garantir que a chamada recursiva seja sempre a ultima operacao da funcao, utilizando parametros acumuladores quando necessario. Com essa tecnica, voce combina a elegancia da recursao com a eficiencia de um loop iterativo.