---
title: "Tailrec em Kotlin: O que É e Como Funciona | Kotlin Brasil"
url: "https://kotlin.dev.br/glossario/tailrec/"
markdown_url: "https://kotlin.dev.br/glossario/tailrec.MD"
description: "Aprenda o que é tailrec em Kotlin, como usar a palavra-chave para recursão de cauda, sintaxe, exemplos práticos e erros comuns ao aplicar tail recursion."
date: "2025-08-10"
author: "Karina Melo"
---

# Tailrec em Kotlin: O que É e Como Funciona | Kotlin Brasil

Aprenda o que é tailrec em Kotlin, como usar a palavra-chave para recursão de cauda, sintaxe, exemplos práticos e erros comuns ao aplicar tail recursion.


## O que é `tailrec` em Kotlin?

A palavra-chave `tailrec` em Kotlin instrui o compilador a otimizar uma função recursiva transformando-a em um loop iterativo nos bastidores. Isso elimina o risco de estouro de pilha (StackOverflowError) que funções recursivas tradicionais apresentam quando processam grandes volumes de dados.

Recursão de cauda (tail recursion) acontece quando a chamada recursiva é a ultima operação executada pela função. Nesse cenário, o compilador não precisa manter o stack frame anterior, pois não há mais nenhum calculo pendente apos o retorno da chamada recursiva. O modificador `tailrec` garante que o compilador Kotlin realize essa otimização e, caso a função não seja elegivel, emite um aviso em tempo de compilação.

## Sintaxe básica

A sintaxe para declarar uma função com `tailrec` e direta. Basta adicionar o modificador antes da palavra `fun`:

```kotlin
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 técnica e fundamental para transformar uma recursão comum em recursão de cauda.

### Comparação com recursão tradicional

Uma implementação recursiva clássica do fatorial seria:

```kotlin
fun fatorialClassico(n: Long): Long {
    if (n <= 1) return 1
    return n * fatorialClassico(n - 1) // multiplicacao APOS a chamada recursiva
}
```

Nessa versão, a multiplicacao `n * fatorialClassico(n - 1)` acontece depois do retorno da chamada recursiva. Isso impede a otimização de cauda porque o compilador precisa manter cada frame na pilha para realizar a multiplicacao pendente. Com números grandes, isso causa StackOverflowError.

## Exemplos práticos

### Soma de uma lista

```kotlin
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

```kotlin
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

```kotlin
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)

```kotlin
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 código

Quando você marca uma função com `tailrec`, o compilador Kotlin gera bytecode equivalente a um loop `while`. O fatorial com `tailrec`, por exemplo, e compilado para algo semelhante a:

```kotlin
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 recursão no bytecode final, garantindo performance constante em termos de uso de pilha independentemente da profundidade da recursão.

## 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 recursão pode ultrapassar o limite da pilha da JVM.
- **Substituicao de loops complexos** onde a lógica recursiva e mais legivel que a iterativa equivalente.
- **Programação funcional** quando você adota um estilo funcional e quer evitar mutação de estado sem sacrificar performance.

### Quando não usar

Nem toda função recursiva pode ser convertida para tail recursion. Nao use `tailrec` quando:

- A chamada recursiva não e a ultima operação da função.
- Ha mais de uma chamada recursiva no corpo da função (como na versão clássica de Fibonacci sem acumulador).
- A função usa blocos try/catch envolvendo a chamada recursiva.
- A simplicidade do loop iterativo torna a recursão desnecessaria.

## Casos de Uso no Mundo Real

1. **Parsers e interpretadores de linguagens**: compiladores e interpretadores frequentemente usam `tailrec` para percorrer arvores sintaticas e avaliar expressoes recursivamente. Como a profundidade da arvore pode ser grande em arquivos de código extensos, a otimização de cauda evita estouros de pilha durante a analise.

2. **Processamento de estruturas de dados encadeadas**: aplicações que manipulam listas encadeadas, arvores ou grafos usam `tailrec` para percorrer nodos sequencialmente. Isso e comum em bibliotecas de estruturas de dados funcionais e em algoritmos de busca em profundidade iterativa.

3. **Algoritmos matematicos e criptograficos**: calculos como MDC (maximo divisor comum), exponenciacao modular e geracoes de sequencias matematicas (Fibonacci, Collatz) se beneficiam de `tailrec` por serem naturalmente recursivos e potencialmente profundos para valores grandes.

4. **Maquinas de estado e protocolos de comunicação**: implementacoes de maquinas de estado que transitam entre estados através de chamadas recursivas usam `tailrec` para garantir que longas sequencias de transicoes não esgotem a pilha. Isso e relevante em protocolos de rede e processamento de eventos.

## Boas Praticas

- Sempre use um parametro acumulador para carregar o resultado parcial entre chamadas recursivas. Essa e a tecnica fundamental para transformar recursao comum em recursao de cauda.
- Preste atencao nos avisos do compilador. Se o Kotlin emitir "A function is marked as tail-recursive but no tail calls are found", revise a função para garantir que a chamada recursiva e realmente a ultima operação.
- Prefira `tailrec` a loops quando a lógica recursiva for mais clara e expressiva que a iterativa equivalente. Nao force o uso de `tailrec` se um simples `for` ou `while` resolve o problema com mais clareza.
- Evite envolver a chamada recursiva em blocos `try-catch`, pois isso impede a otimização de cauda. Trate erros antes da chamada recursiva ou use um wrapper externo.
- Escreva testes com valores grandes (por exemplo, `n = 100_000`) para confirmar que a otimização esta funcionando. Se a função lanca `StackOverflowError` com valores altos, a recursao de cauda não esta sendo aplicada corretamente.

## Perguntas Frequentes

**P: O que acontece se eu marcar uma função com `tailrec` mas ela não for elegivel para otimização?**
R: O compilador Kotlin emite um aviso em tempo de compilação informando que nenhuma chamada de cauda foi encontrada. A função compila e executa normalmente, mas sem a otimização -- ou seja, ela ainda pode causar `StackOverflowError` com recursoes profundas.

**P: O `tailrec` funciona com funções que tem mais de um branch recursivo?**
R: Cada branch individual pode ser uma chamada de cauda válida. O problema ocorre quando um branch realiza uma operação apos a chamada recursiva. Se todos os branches recursivos tem a chamada como ultima operação, a otimização funciona. Se apenas alguns branches sao de cauda, o compilador emite aviso e não otimiza.

**P: Existe diferenca de performance entre `tailrec` e um loop `while` escrito manualmente?**
R: Nao. O compilador transforma a função `tailrec` em um loop no bytecode, gerando código equivalente a um `while`. A performance em tempo de execução e identica. A escolha entre `tailrec` e loop manual e uma questao de legibilidade e estilo de programacao.

**P: Posso usar `tailrec` em funções suspensas (suspend functions)?**
R: Nao. O modificador `tailrec` não e compativel com funções `suspend` em Kotlin. funções suspensas tem um mecanismo de continuacao que impede a otimização de cauda pelo compilador. Para recursao em funções suspensas, considere usar loops iterativos ou `sequence`.

## Erros comuns

### Recursão que não e de cauda

```kotlin
// 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 função compila, mas sem a otimização desejada.

### Correção com acumulador

```kotlin
// CORRETO: recursão 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 função dentro de expressoes

```kotlin
// 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 válida. O branch com concatenacao impede a otimização completa.

### Uso com funções de extensao

O `tailrec` também funciona com funções de extensao, desde que a chamada recursiva siga as regras de cauda:

```kotlin
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

- **Recursão**: técnica onde uma função chama a si mesma para resolver subproblemas menores.
- **Stack overflow**: erro que ocorre quando a pilha de execução excede seu limite por excesso de chamadas empilhadas.
- **Função de ordem superior**: funções que recebem ou retornam outras funções, frequentemente combinadas com recursão.
- **Programação funcional**: paradigma que favorece imutabilidade e recursão sobre loops e estado mutavel.
- **inline**: modificador que instrui o compilador a copiar o corpo da função no ponto de chamada, outra forma de otimização em Kotlin.
- **Sequence**: tipo lazy de Kotlin que pode substituir recursão para processamento de coleções grandes.

## Conclusão

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 operação da função, utilizando parametros acumuladores quando necessário. Com essa técnica, você combina a elegancia da recursão com a eficiencia de um loop iterativo.