"Para entender recursão, primeiro você deve entender recursão." — provérbio clássico de programação
Recursão é quando uma função chama a si mesma para resolver versões menores do mesmo problema — até chegar num caso simples o suficiente para resolver direto.
function sumTo(n) { if (n <= 1) return n; return n + sumTo(n - 1);} sumTo(5); // 15Neste guia da série 33 Conceitos JS — projeto open source criado por Leonardo Maldonado — você vai aprender:
Pré-requisitos: Call Stack e Map, Reduce & Filter — recursão e HOFs combinam em travessias elegantes.
// metadados do artigo
{
"tag": "functional programming",
"readTime": "22 min",
"author": "Vanderlei José Alamino",
"source": "33jsconcepts.com",
"series": "33 Conceitos JS",
"part": {
"current": 28,
"total": 38
}
}Fonte de referência
Conteúdo adaptado a partir do guia original em inglês.
seção
Cada boneca contém uma menor. Você abre até a menor — que não abre mais (caso base). Depois fecha de volta, devolvendo valores pela cadeia.
Abrir = chamada recursiva (problema menor)Menor = caso base (parar)Fechar = retornos subindo pela stackNa recursão, cada chamada espera a de cima retornar antes de concluir seu próprio cálculo.
seção
function solve(problem) { if (problem is simple enough) { return solution directly; // CASO BASE } return solve(smaller problem); // CASO RECURSIVO}function sumTo(n) { if (n <= 1) return n; return n + sumTo(n - 1);} sumTo(5); // 5 + sumTo(4) + ... + 1 = 15A pergunta "soma de 1 a 5?" vira "5 + soma de 1 a 4" — até n === 1.
seção
Cada chamada empilha um contexto de execução. A função espera a recursiva retornar antes de terminar.
sumTo(3) → sumTo(2) → sumTo(1) retorna 1 ← 2+1=3 ← 3+3=6function sumTo(n) { console.log(`Chamado sumTo(${n})`); if (n === 1) { console.log(" Caso base! Retornando 1"); return 1; } const result = n + sumTo(n - 1); console.log(` sumTo(${n}) retornando ${result}`); return result;}Cada chamada tem seu próprio n — não interferem. Veja Call Stack para o fundamento completo.
seção
Exemplos assumem inteiros não negativos; em produção valide inputs.
function factorial(n) { if (n <= 1) return 1; return n * factorial(n - 1);} factorial(5); // 120factorial(4) = 4 * 3 * 2 * 1 = 24function fibonacci(n) { if (n === 0) return 0; if (n === 1) return 1; return fibonacci(n - 1) + fibonacci(n - 2);} fibonacci(10); // 55fibonacci(40); // >300M chamadas — evite sem memofunction power(x, n) { if (n === 0) return 1; return x * power(x, n - 1);} function powerFast(x, n) { if (n === 0) return 1; if (n % 2 === 0) { const half = powerFast(x, n / 2); return half * half; } return x * powerFast(x, n - 1);}function reverse(str) { if (str.length <= 1) return str; return str[str.length - 1] + reverse(str.slice(0, -1));} reverse("hello"); // "olleh"seção
Recursão brilha em estruturas aninhadas ou em árvore.
function findAllCounts(obj) { let total = 0; for (const key in obj) { if (key === "count") total += obj[key]; else if (typeof obj[key] === "object" && obj[key] !== null) { total += findAllCounts(obj[key]); } } return total;}function flatten(arr) { let result = []; for (const item of arr) { if (Array.isArray(item)) result = result.concat(flatten(item)); else result.push(item); } return result;} flatten([1, [2, [3, 4]], 5]); // [1, 2, 3, 4, 5]// Ou arr.flat(Infinity)function walkDOM(node, callback) { callback(node); for (const child of node.children) { walkDOM(child, callback); }}Combina recursão com Higher-Order Functions. Veja também DOM.
function sumList(node) { if (node === null) return 0; return node.value + sumList(node.next);} function printReverse(node) { if (node === null) return; printReverse(node.next); console.log(node.value);}function getTotalSize(node) { if (node.type === "file") return node.size; return node.children.reduce((t, c) => t + getTotalSize(c), 0);}seção
| Aspecto | Recursão | Iteração |
|---|---|---|
| Legibilidade | Ótima em árvores | Simples em linear |
| Memória | O(n) na stack | O(1) típico |
| Performance | Overhead de chamada | Geralmente mais rápida |
| Risco | Stack overflow (~10k+) | Sem risco de stack |
// Recursivofunction factorial(n) { if (n <= 1) return 1; return n * factorial(n - 1);} // Iterativofunction factorialIter(n) { let result = 1; for (let i = 2; i <= n; i++) result *= i; return result;}Use recursão: árvores, DOM, JSON, divide-and-conquer, clareza. Use loops: contagem linear, hot paths, profundidade > ~10.000.
seção
function countdown(n) { console.log(n); countdown(n - 1); // CRASH infinito}// RangeError: Maximum call stack size exceeded function countdownOk(n) { if (n < 0) return; console.log(n); countdownOk(n - 1);}// ❌ n===0 nunca alcançado se decremento de 2 a partir de ímparif (n === 0) return;countdown(n - 2); // ✓if (n <= 0) return;function sum(n) { if (n === 1) return 1; sum(n - 1) + n; // undefined!} return sum(n - 1) + n; // ✓// ❌ count globallet count = 0;function countNodes(node) { if (!node) return; count++; countNodes(node.left); countNodes(node.right);} // ✓ retorne valoresfunction countNodes(node) { if (!node) return 0; return 1 + countNodes(node.left) + countNodes(node.right);}Subproblemas sobrepostos → O(2^n). Corrija com memoização.
seção
function fibonacci(n, memo = {}) { if (n in memo) return memo[n]; if (n <= 1) return n; memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo); return memo[n];} fibonacci(100); // instantâneo — O(n)// Não tail: multiplica DEPOIS da chamadafunction factorial(n) { if (n <= 1) return 1; return n * factorial(n - 1);} // Tail: última operação é a chamadafunction factorialTail(n, acc = 1) { if (n <= 1) return acc; return factorialTail(n - 1, acc * n);}TCO (Tail Call Optimization) reutilizaria o frame — mas V8/Node e Firefox não implementam TCO na prática; Safari (JavaScriptCore) sim. Não conte com TCO para evitar stack overflow na maioria dos ambientes.
function sumTreeIterative(root) { if (!root) return 0; let sum = 0; const stack = [root]; while (stack.length) { const node = stack.pop(); sum += node.value; if (node.right) stack.push(node.right); if (node.left) stack.push(node.left); } return sum;}Heap (array) em vez de call stack — profundidade ilimitada na prática.
seção
seção
seção
Você completou o quarto pilar da trilha Functional Programming. O último conceito é Currying & Composition — padrões avançados para compor funções puras.
Revise Call Stack se a stack ainda parecer abstrata.
→ Currying & Composition — montando funções como LEGO
Fonte de referência: 33jsconcepts.com/concepts/recursion ⬀