Manual da Recursão JavaScript & Tail Call Optimization

---

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

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:

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.

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.

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á:

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)

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.

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:

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.

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

• Tail Call Optimization in ES6 (2ality)

• ES6 Compatibility Table (Kangax)

• Async recursion in JavaScript (Scott Logic)