# Manual da Recursão JavaScript & Tail Call Optimization

---

Você já tentou escrever uma função recursiva em JavaScript e se deparou com o erro:

```plaintext
RangeError: Maximum call stack size exceeded
```

Isso acontece porque o JavaScript **não implementa Tail Call Optimization (TCO)** — um recurso previsto na especificação do ECMAScript 2015 (ES6), mas nunca adotado pelos principais motores.

Antes de entender o problema, vamos entender a base.

---

### O que é recursão?

**Recursão** acontece quando uma função chama a si mesma — direta ou indiretamente. Toda recursão precisa de duas partes:

* **Caso base (condição de saída)**: quando parar de chamar a si mesma;
    
* **Chamada recursiva**: onde a função se chama com um argumento diferente, normalmente em direção ao caso base.
    

### Exemplo clássico:

```plaintext
function countDown(n) {
  if (n === 0) return;
  console.log(n);
  countDown(n - 1); // chamada recursiva
}
```

Sem um caso base (`if (n === 0) return`), essa função entraria em loop infinito, até estourar a pilha de chamadas.

---

### Tipos comuns de recursão

Além da **recursão direta** (uma função chama a si mesma), existem:

* **Recursão indireta**: a função A chama B, que chama A novamente.
    

```plaintext
function isEven(n) {
  if (n === 0) return true;
  return isOdd(n - 1);
}

function isOdd(n) {
  if (n === 0) return false;
  return isEven(n - 1);
}
```

* **Recursão mútua**: dois ou mais métodos se chamam em um ciclo.
    

```plaintext
function A(n) {
  if (n <= 0) return;
  console.log("A", n);
  B(n - 1);
}

function B(n) {
  if (n <= 0) return;
  console.log("B", n);
  C(n - 1);
}

function C(n) {
  if (n <= 0) return;
  console.log("C", n);
  A(n - 1);
}
```

* **Recursão de cauda (tail recursion)**: a chamada recursiva é a última instrução da função.
    

Essa última é a mais importante para performance, pois é onde a **Tail Call Optimization** pode atuar.

---

### Como funciona a stack no JavaScript?

Quando você chama uma função em JavaScript, o motor de execução cria um **stack frame** (quadro de pilha) contendo:

* Onde retornar quando a função acabar;
    
* O escopo local da função;
    
* Parâmetros e variáveis locais.
    

Cada chamada recursiva empilha mais um frame. Quando a base do caso recursivo é finalmente atingida, o motor do JS começa a desempilhar tudo. Se houver muitas chamadas antes de atingir esse ponto, a pilha explode.

Se houver chamadas demais antes de chegar no fim, você verá:

```plaintext
RangeError: Maximum call stack size exceeded
```

### O que é Tail Call Optimization?

Tail Call Optimization é uma técnica em que o interpretador ou compilador percebe que **a última coisa que uma função precisa fazer antes de retornar é chamar outra função**. Em vez de adicionar um novo frame na pilha de chamadas (call stack), ele **reutiliza** o frame atual.

### Exemplo sem TCO (chamada recursiva tradicional)

```plaintext
function factorial(n) {
  if (n < 2) return 1;
  return n * factorial(n - 1); // NÃO é tail call
}
```

Essa função é recursiva, mas o valor de `factorial(n - 1)` ainda precisa ser multiplicado por `n` depois de resolvido. Logo, a chamada não está na **posição final** da função (tail position), e a stack cresce a cada chamada.

### Tail-recursive

Aqui, a última instrução da função `fact` é a chamada recursiva. Com TCO, seria possível rodar isso de forma tão eficiente quanto um `for` ou `while`, porque a pilha não cresceria.

```plaintext
function factorial(n) {
  function fact(n, acc) {
    if (n < 2) return acc;
    return fact(n - 1, n * acc); // <- chamada em posição de cauda
  }
  return fact(n, 1);
}
```

---

### A promessa do ES6 (e do ES8)

A especificação do ES6 prometia suporte a TCO. E mais: ela **exigia** que os motores JavaScript fizessem otimização de chamadas em tail position em modo *strict* (`'use strict'`).

Já o ES8 (2017) trouxe `async/await`, que ajudou a tratar recursões assíncronas — mas não resolveu o problema da pilha em recursões síncronas.

### Exemplo de recursão perigosa:

```plaintext
function pow(base, power) {
  if (power === 0) return 1;
  return pow(base, power - 1) * base;
}
pow(4, 84599); // Em inputs altos ele estoura 💥
```

### Mas… por que JavaScript ignorou a especificação?

Apesar de TCO estar na especificação do ECMAScript 2015 (ES6) — com a exigência de suporte em modo `'use strict'` — **nenhum dos principais motores de JavaScript modernos implementou**.

### Teorias e motivos:

1. **Compatibilidade com depuradores**  
     Ferramentas de debug como o Chrome DevTools se baseiam na pilha tradicional. Otimizar frames quebraria o rastreamento entre chamadas.
    
2. **Complexidade de implementação**  
     Motores como o V8 (Chrome e Node.js) foram otimizados para desempenho em outras áreas. Suportar TCO exigiria reestruturações profundas.
    
3. **Baixo uso prático**  
     Como loops são mais comuns no ecossistema JavaScript, o esforço para suportar TCO não se justifica.
    
4. **Efeito dominó de compatibilidade**  
     Se apenas um motor suportar TCO e os outros não, surgem inconsistências. Como nenhum quis ser o primeiro, nenhum implementou.
    

Atualmente, apenas o Safari (WebKit) chegou a oferecer algum suporte a TCO, mas até isso foi limitado e eventualmente descontinuado.

Em resumo: *JavaScript ignorou TCO porque isso traria mais problemas (e custos) do que soluções no ecossistema atual*.

---

### Recursão assíncrona com `async/await`

Recursão assíncrona contorna o problema de stack overflow porque **cada chamada aguarda o término da anterior** antes de continuar, liberando a stack.

```plaintext
async function processItems(items, index = 0) {
  if (index >= items.length) return;
  await doSomething(items[index]);
  return processItems(items, index + 1);
}
```

Essa abordagem é **segura para longas listas** ou processos de IO.

---

### Alternativas práticas

Se você precisa de segurança e performance:

* Use `for` ou `while` no lugar de recursão tradicional;
    
* Se for usar recursão, prefira a forma tail-recursive;
    
* Use `async/await` para recursão que lida com IO assíncrono;
    
* Evite recursões profundas em funções síncronas.
    

O livro *Eloquent JavaScript* já alerta:

> *“Em JavaScript, executar um loop simples é muito mais barato do que chamar uma função múltiplas vezes. A recursão eficiente exige suporte à eliminação de chamadas em cauda.”*

Em benchmarks, loops são **até 10x mais rápidos** do que recursão em JavaScript.

---

### Por que linguagens funcionais usam tanta recursão?

Embora loops (`for`, `while`) sejam frequentemente usados no lugar da recursão em linguagens como JavaScript por questões de performance e controle da stack, eles **não substituem a recursão conceitualmente** — apenas imitam certos comportamentos.

A recursão expressa um **paradigma funcional**, onde o fluxo do programa é descrito em termos de **chamadas de função**, e não de iteração explícita. Isso permite representar problemas complexos de forma mais declarativa, como árvores, grafos e algoritmos matemáticos elegantes. Substituir recursão por loops é, na prática, uma **mudança de paradigma de programação**, que pode reduzir clareza e expressividade dependendo do caso.

Linguagens como Haskell, Elixir ou Scheme evitam loops imperativos. Nelas, recursão é a forma natural de repetição.

E o principal: **elas implementam TCO de verdade**. Isso significa que chamadas recursivas são otimizadas pelo compilador, sem riscos de stack overflow.

### Conclusão

Recursão é poderosa, mas perigosa em JavaScript sem suporte a TCO. Linguagens funcionais mostram o potencial real da recursão com suporte de verdade do compilador. Até lá, o JavaScript exige cuidados extra especialmente se você estiver pensando em escrever sem uma boa razão.

Se precisar da performance e segurança de uma stack estável, prefira `for`, `while` ou `async/await`. E se for usar recursão, prefira sempre que possível a forma tail-recursive — ainda que o motor JS não otimize, seu código será mais claro, testável e portável.

---

### Referências

* [Eloquent JavaScript, 3rd Edition](https://eloquentjavascript.net/)
    
* Tail Call Optimization in ES6 (2ality)
    
* [ES6 Compatibility Table (Kangax)](https://kangax.github.io/compat-table/es6/)
    
* [Async recursion in JavaScript (Scott Logic)](https://blog.scottlogic.com/)