Recursividade: a função que chama ela mesma

Recursividade acontece quando uma função resolve um problema chamando a si mesma com uma versão menor do problema. Para terminar, ela precisa de um caso base alcançável; cada chamada pendente ocupa espaço na pilha até a resposta voltar.

O exemplo será fatorial: 5! significa 5 × 4 × 3 × 2 × 1. A decomposição em funções já separa tarefas; recursão aplica a mesma tarefa a entradas progressivamente menores.

A última boneca russa salva todas as outras

Imagine bonecas encaixadas. Você abre uma e encontra uma menor, até chegar à que não abre. A menor é o caso base; depois você fecha na ordem inversa. O limite da analogia é que chamadas guardam parâmetros, variáveis e ponto de retorno, não objetos físicos.

O raciocínio pode ser escrito antes da sintaxe:

fatorial de n:
  se n é 0, devolver 1
  caso contrário, devolver n vezes fatorial de n - 1

As duas linhas respondem às perguntas essenciais: quando para e como diminui. Se o passo não aproxima a entrada do caso base, a descrição já anuncia o defeito.

Caso base encerra sem nova chamada

Por definição, 0! vale um. Essa resposta direta impede outra descida:

function fatorial(n) {
  if (n === 0) return 1;
  return n * fatorial(n - 1);
}

console.log(fatorial(0));
console.log(fatorial(1));
console.log(fatorial(5));

O caso base não é remendo para evitar erro; ele é parte matemática da definição. Para listas, pode ser lista vazia. Para árvore, pode ser nó ausente. Nomeie o estado que já possui resposta sem dividir mais.

Passo recursivo reduz o problema

fatorial(n - 1) preserva a forma e reduz a entrada. Compare os argumentos que serão chamados:

function argumentosAteBase(n) {
  const valores = [n];
  while (n > 0) {
    n -= 1;
    valores.push(n);
  }
  return valores;
}

console.log(argumentosAteBase(5));

Essa lista é uma previsão da ida. Antes de rodar uma recursão, escreva os primeiros argumentos e confirme que chegam ao caso base. É um teste de mesa focado na profundidade.

Fatorial de cinco, chamada por chamada

Indentação torna visíveis ida e volta:

function fatorial(n, nivel = 0) {
  const recuo = '  '.repeat(nivel);
  console.log(`${recuo}entra fatorial(${n})`);
  if (n === 0) {
    console.log(`${recuo}sai 1`);
    return 1;
  }
  const resultado = n * fatorial(n - 1, nivel + 1);
  console.log(`${recuo}sai ${resultado}`);
  return resultado;
}

fatorial(5);

Na ida, cada multiplicação fica pendente. Na volta, fatorial(0) entrega um para a chamada de um; depois surgem 2, 6, 24 e 120. Recursão tem duas direções temporais, mesmo que o código tenha poucas linhas.

A pilha guarda trabalho esperando resposta

Podemos registrar as multiplicações pendentes sem executar a recursão:

const pilha = [];
for (let n = 5; n > 0; n -= 1) pilha.push(n);

let resultado = 1;
while (pilha.length) {
  const n = pilha.pop();
  resultado *= n;
  console.log(n, resultado);
}

Essa versão usa uma pilha explícita. Ela mostra que recursão não elimina estado; transfere o controle para a pilha de chamadas do runtime.

Sem caso base, a pilha estoura

Este código foi executado no Node v26.3.0. O contador mede a profundidade atingida por esta forma exata da função nesta execução:

let chamadas = 0;
function semCasoBase() {
  chamadas += 1;
  return semCasoBase();
}

try {
  semCasoBase();
} catch (erro) {
  console.log(`chamadas=${chamadas}`);
  console.log(`${erro.name}: ${erro.message}`);
}

O número não é limite universal. Versão do runtime, plataforma e quantidade de estado por chamada influenciam a profundidade. A evidência que permanece é o padrão: chamadas crescem sem alcançar resposta direta e terminam em RangeError.

Entrada negativa também foge do caso base

Subtrair um número negativo nunca chega a zero. Valide o domínio antes de descer:

function fatorial(n) {
  if (!Number.isInteger(n) || n < 0) throw new RangeError('n deve ser inteiro não negativo');
  if (n === 0) return 1;
  return n * fatorial(n - 1);
}

try {
  fatorial(-1);
} catch (erro) {
  console.log(`${erro.name}: ${erro.message}`);
}

Caso base e validação são papéis distintos. Zero é uma entrada válida com resposta direta; menos um está fora do contrato.

A mesma tarefa com laço

Fatorial é linear e um laço evita pilha crescente:

function fatorialIterativo(n) {
  let resultado = 1;
  for (let fator = 2; fator <= n; fator += 1) resultado *= fator;
  return resultado;
}

console.log(fatorialIterativo(5));

Para uma sequência simples, o laço costuma ser mais previsível no Node. Recursão ganha clareza em estruturas naturalmente aninhadas, como árvore de pastas, desde que a profundidade seja controlada. Não escolha pela quantidade de caracteres.

Missão: somar uma lista sem laço

Defina caso base para lista vazia e reduza a lista em um elemento:

function somar(numeros) {
  if (numeros.length === 0) return 0;
  return numeros[0] + somar(numeros.slice(1));
}

console.log(somar([4, 7, 2, 9]));

Antes de considerar a missão pronta, estime custo de slice. Cada chamada cria uma nova lista, então o exemplo privilegia clareza didática, não eficiência para coleções grandes. Uma versão com índice evita cópias, mas acrescenta estado ao contrato. Compare somente depois de entender a árvore de chamadas.

Faça também um teste de profundidade segura. Uma lista pequena passa; uma lista enorme pode atingir o limite da pilha mesmo com caso base correto. Correção matemática e adequação ao runtime são critérios diferentes. Para entrada controlada e árvore rasa, recursão pode ser expressiva; para profundidade desconhecida, use pilha explícita ou laço.

Ao depurar, registre argumento na entrada e retorno na saída com indentação. Se os argumentos não se aproximam do caso base, corrija o passo. Se chegam ao caso base mas o retorno está errado, rastreie a operação na volta. Separar ida e volta reduz a aparente magia.

Por fim, valide domínio antes da primeira chamada recursiva. Um caso base não substitui rejeição de negativos, ciclos numa árvore ou referência repetida em grafo. Estruturas com ciclos exigem conjunto de visitados, caso contrário “problema menor” pode retornar a um estado anterior.

Desenhe a árvore para entradas pequenas antes de medir. Chamadas repetidas com o mesmo argumento revelam oportunidade de memoização; uma única cadeia profunda revela risco de pilha. A forma da árvore explica custo melhor que a quantidade de linhas da função.

O critério é prever as cinco chamadas e a ordem dos retornos. Depois compare custo na complexidade de algoritmo, resolva a versão iterativa nos exercícios de lógica, consulte o guia e siga a trilha.