A recursão é uma técnica fundamental em programação onde uma função chama a si mesma para resolver um problema dividindo-o em subproblemas menores. Em JavaScript, essa abordagem é amplamente utilizada em algoritmos de busca, ordenação, processamento de árvores e em problemas matemáticos. Compreender a recursão é essencial para escrever código elegante e para pensar de forma algorítmica.

Nesta aula, vamos mergulhar no funcionamento da recursão em JavaScript, explorando seus componentes essenciais, como a recursão utiliza a pilha de chamadas e quais são os limites práticos dessa técnica. Ao final, você terá uma base sólida para aplicar recursão em seus próprios projetos com confiança.

Conceito

Recursão é um método de resolução de problemas que envolve quebrar um problema em instâncias menores do mesmo problema. Em programação, isso se traduz em uma função que chama a si mesma durante sua execução. Cada chamada recursiva resolve uma versão menor do problema original, até atingir um caso trivial que pode ser resolvido diretamente.

Um exemplo clássico é o cálculo do fatorial de um número. O fatorial de n (representado como n!) é o produto de todos os inteiros positivos de 1 até n. Podemos definir matematicamente como: n! = n * (n-1)! e 0! = 1. Essa definição é naturalmente recursiva, pois o fatorial de n depende do fatorial de n-1.

function fatorial(n) {
  if (n === 0) return 1; // caso base
  return n * fatorial(n - 1); // passo recursivo
}

console.log(fatorial(5)); // 120

A recursão oferece uma maneira clara e concisa de expressar algoritmos que possuem uma estrutura repetitiva, mas nem sempre é a mais eficiente em termos de desempenho. É importante saber quando usá-la e quando optar por abordagens iterativas.

Caso base

O caso base é a condição que interrompe a recursão. Sem ele, a função continuaria a chamar a si mesma infinitamente, causando um estouro de pilha. O caso base define a menor instância do problema que pode ser resolvida diretamente, sem novas chamadas recursivas.

No exemplo do fatorial, o caso base é n === 0, que retorna 1. Em outros algoritmos, o caso base pode ser um valor específico, uma condição de contorno ou quando uma estrutura de dados está vazia. É crucial que toda recursão tenha pelo menos um caso base bem definido.

function contagemRegressiva(n) {
  console.log(n);
  if (n > 0) { // condição para continuar
    contagemRegressiva(n - 1);
  }
  // quando n é 0, a função encerra sem chamar a si mesma
}

contagemRegressiva(3);
// Saída: 3, 2, 1, 0

Observe que o caso base não precisa ser uma única condição; pode haver múltiplos casos base, dependendo do problema. Por exemplo, em algoritmos que percorrem árvores, o caso base ocorre quando o nó é nulo.

Pilha de chamadas

Para entender a recursão em profundidade, é essencial compreender a pilha de chamadas (call stack). Em JavaScript, cada chamada de função cria um novo contexto de execução que é empilhado sobre o anterior. Quando uma função chama a si mesma, um novo quadro é adicionado à pilha, contendo os parâmetros, variáveis locais e o ponto de retorno.

Conforme a recursão avança, a pilha cresce. Quando o caso base é atingido, as funções começam a retornar, desempilhando os quadros em ordem inversa. Esse processo é conhecido como "desenrolar" da recursão. Vamos visualizar com o exemplo do fatorial de 4:

fatorial(4)
  -> 4 * fatorial(3)
    -> 3 * fatorial(2)
      -> 2 * fatorial(1)
        -> 1 * fatorial(0)
          -> retorna 1
        -> retorna 1 * 1 = 1
      -> retorna 2 * 1 = 2
    -> retorna 3 * 2 = 6
  -> retorna 4 * 6 = 24

A pilha de chamadas tem tamanho limitado. Se a recursão for muito profunda (por exemplo, tentar calcular o fatorial de 10000), o navegador ou o Node.js lançará um erro de "RangeError: Maximum call stack size exceeded". Esse é um dos principais limites da recursão.

Exemplos clássicos e limites

Vamos explorar alguns exemplos clássicos de recursão e os limites práticos que encontramos.

Sequência de Fibonacci

A sequência de Fibonacci é definida como: F(0) = 0, F(1) = 1 e F(n) = F(n-1) + F(n-2) para n > 1. Essa definição é diretamente recursiva, mas a implementação ingênua é extremamente ineficiente, pois recalcula os mesmos valores muitas vezes.

function fibonacci(n) {
  if (n < 2) return n; // casos base: F(0)=0, F(1)=1
  return fibonacci(n - 1) + fibonacci(n - 2);
}

console.log(fibonacci(10)); // 55

Para n = 40, essa função já leva um tempo considerável. Isso ocorre porque a árvore de chamadas tem complexidade exponencial. Uma alternativa é usar memoização (armazenar resultados já calculados) ou converter para iteração.

Recursão em estruturas de dados

Recursão é natural para percorrer estruturas como árvores. Por exemplo, para calcular a profundidade de uma árvore binária:

function profundidade(no) {
  if (no === null) return 0; // caso base
  return 1 + Math.max(profundidade(no.esquerda), profundidade(no.direita));
}

Esse tipo de algoritmo é difícil de implementar iterativamente sem uma pilha explícita, mostrando a elegância da recursão.

Limites da recursão

O principal limite é o estouro de pilha. Em JavaScript, o tamanho máximo da pilha varia conforme o ambiente (navegador, Node.js), mas geralmente fica na casa de dezenas de milhares de chamadas. Para evitar esse problema, podemos: 1) usar recursão de cauda (tail call optimization), que ainda não é amplamente suportado em todos os ambientes JavaScript; 2) reescrever o algoritmo de forma iterativa; 3) usar memoização para reduzir o número de chamadas; ou 4) usar uma pilha explícita para simular a recursão.

Outro limite é a legibilidade: recursão pode ser mais difícil de entender para problemas que não têm uma estrutura naturalmente recursiva. Sempre avalie se a recursão é a melhor escolha.

Boas práticas e observações finais

Ao usar recursão em JavaScript, siga estas boas práticas:

  • Defina claramente o caso base e garanta que ele seja alcançável em todas as execuções.
  • Teste com valores pequenos antes de aumentar a complexidade.
  • Considere o desempenho: para problemas com muita sobreposição de subproblemas, utilize memoização ou iteração.
  • Evite recursão profunda sem necessidade; se o problema exigir, pense em soluções alternativas.
  • Documente seu código recursivo com comentários explicando a lógica.

A recursão é uma ferramenta poderosa que, quando usada corretamente, pode tornar seu código mais limpo e expressivo. Ao dominar seus conceitos e limites, você estará apto a resolver uma ampla gama de problemas.

Exercícios

  1. Escreva uma função recursiva chamada somaPares que recebe um número n e retorna a soma de todos os números pares de 0 até n (inclusive). Por exemplo, somaPares(5) deve retornar 6 (2+4).

    2. ✓ Resposta:
    function somaPares(n) {
  if (n < 2) return 0; // caso base: nenhum par abaixo de 2
  if (n % 2 !== 0) return somaPares(n - 1); // se ímpar, ignora
  return n + somaPares(n - 2); // soma n e continua com n-2
}

console.log(somaPares(5)); // 6
console.log(somaPares(10)); // 30
  2. Implemente uma função recursiva inverterString que recebe uma string e retorna a mesma invertida. Por exemplo, inverterString("abc") deve retornar "cba".

    3. ✓ Resposta:
    function inverterString(str) {
  if (str === "") return ""; // caso base
  return inverterString(str.slice(1)) + str[0];
}

console.log(inverterString("abc")); // "cba"
  3. Crie uma função recursiva contarDigitos que recebe um número inteiro positivo e retorna a quantidade de dígitos. Exemplo: contarDigitos(12345) deve retornar 5.

    4. ✓ Resposta:
    function contarDigitos(num) {
  if (num < 10) return 1; // caso base: um dígito
  return 1 + contarDigitos(Math.floor(num / 10));
}

console.log(contarDigitos(12345)); // 5
  4. Escreva uma função recursiva palindromo que verifica se uma string é um palíndromo (lê-se igual de trás para frente), desconsiderando espaços e diferenças de maiúsculas/minúsculas. Exemplo: palindromo("A base do teto desaba") deve retornar true.

    5. ✓ Resposta:
    function palindromo(str) {
  // remove espaços e converte para minúsculas
  str = str.toLowerCase().replace(/\s/g, "");
  function verifica(s) {
    if (s.length <= 1) return true; // caso base
    if (s[0] !== s[s.length - 1]) return false;
    return verifica(s.slice(1, -1));
  }
  return verifica(str);
}

console.log(palindromo("A base do teto desaba")); // true
  5. Implemente uma função recursiva maiorElemento que recebe um array de números e retorna o maior valor. Use recursão e não métodos prontos como Math.max. Exemplo: maiorElemento([3, 7, 2, 9]) deve retornar 9.

    6. ✓ Resposta:
    function maiorElemento(arr) {
  if (arr.length === 1) return arr[0]; // caso base
  const subMaior = maiorElemento(arr.slice(1));
  return arr[0] > subMaior ? arr[0] : subMaior;
}

console.log(maiorElemento([3, 7, 2, 9])); // 9

Referências