Recursão (Opcional)

Quando estamos escrevendo funções, normalmente pensamos em resolver um problema com passos diretos: fazemos um cálculo, chamamos outra função, repetimos algo com um for ou while, e seguimos em frente. Mas existe um outro jeito, muitas vezes mais elegante e natural, de resolver certos tipos de problemas: é quando uma função chama a si mesma. Essa técnica tem nome — recursão — e embora pareça estranha à primeira vista, ela é uma ferramenta poderosa, especialmente útil quando lidamos com problemas que possuem estrutura repetitiva ou hierárquica.

Vamos começar com a definição: recursão é quando uma função chama a si mesma como parte de sua execução, geralmente com uma entrada ligeiramente diferente da anterior. Esse processo continua até que a função atinja uma condição de parada, que é o momento em que ela não se chama mais.

Um bom jeito de entender a recursão é com um exemplo cotidiano: imagine uma caixa que contém outra caixa, que contém outra caixa, e assim por diante. Como você abriria todas elas? Uma maneira natural seria: "Abra a caixa atual, veja se há outra dentro. Se houver, abra a próxima da mesma forma." Isso é recursão.

Outro exemplo bem conhecido é o cálculo do fatorial de um número, que pode ser definido de forma recursiva:

• fatorial(1) é 1 (caso base)
• fatorial(n) é n * fatorial(n - 1) (caso recursivo)

Vamos transformar isso em código:

function fatorial(n: number): number {
  if (n === 1) {
    return 1; // caso base
  }
  return n * fatorial(n - 1); // chamada recursiva
}

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

Esse exemplo é simples, mas mostra muito bem o funcionamento da recursão. A função vai chamando a si mesma com n - 1, até que n seja igual a 1. Nesse ponto, ela para de se chamar, e o retorno começa a “subir” por toda a cadeia de chamadas anteriores.

Para deixar ainda mais claro, veja como as chamadas acontecem, uma por uma:

fatorial(5) → 5 * fatorial(4)
fatorial(4) → 4 * fatorial(3)
fatorial(3) → 3 * fatorial(2)
fatorial(2) → 2 * fatorial(1)
fatorial(1) → 1

Substituindo de trás para frente:

fatorial(2) → 2 * 1 = 2
fatorial(3) → 3 * 2 = 6
fatorial(4) → 4 * 6 = 24
fatorial(5) → 5 * 24 = 120

Ou podemos visualizar assim:

fatorial(5) -> aguardando fatorial(4)
  fatorial(4) -> aguardando fatorial(3)
    fatorial(3) -> aguardando fatorial(2)
      fatorial(2) -> aguardando fatorial(1)
        fatorial(1) -> retorna 1
      fatorial(2) -> retorna 2 * 1 = 2
    fatorial(3) -> retorna 3 * 2 = 6
  fatorial(4) -> retorna 4 * 6 = 24
fatorial(5) -> retorna 5 * 24 = 120

Esse tipo de funcionamento é chamado de pilha de chamadas. Cada vez que uma função é chamada, o JavaScript coloca essa chamada em uma pilha (stack), e só sai de lá quando o resultado está pronto. É por isso que a recursão precisa sempre ter um ponto de parada, ou seja, um caso base bem definido — senão, o programa entra em loop infinito e trava.

Estrutura de uma Função Recursiva

Toda função recursiva precisa de dois elementos:

1. Caso Base: Uma condição que encerra a recursão, impedindo um loop infinito.
2. Chamada Recursiva: O ponto onde a função chama a si mesma, geralmente com uma entrada modificada que se aproxima do caso base.

Recursão vs. Laços

Qualquer problema recursivo pode ser resolvido com um laço (for, while), e vice-versa. A recursão brilha em problemas com estrutura naturalmente hierárquica, como navegar em árvores de dados ou sistemas de arquivos, pois o código tende a ser mais limpo e expressivo.

Contagem com Laço:

function contarAteComLoop(n: number): void {
  for (let i = 1; i <= n; i++) {
    console.log(i);
  }
}

Contagem com Recursão:

function contarAteComRecursao(n: number, atual: number = 1): void {
  if (atual > n) {
    return; // Caso base
  }
  console.log(atual);
  contarAteComRecursao(n, atual + 1); // Chamada recursiva
}

Note que a versão recursiva é um pouco mais difícil de entender à primeira vista, mas ela segue o mesmo princípio: imprime um número, e chama a si mesma com o próximo.

Recursão com retorno acumulado

Além de imprimir coisas ou executar ações, funções recursivas também podem acumular valores e retornar um resultado composto. Isso é muito comum em problemas que envolvem soma, multiplicação, contagem ou construção de textos e estruturas.

Exemplo: somar todos os números de 1 até n.

function somar(n: number): number {
  if (n === 1) {
    return 1;
  }
  return n + somar(n - 1);
}

console.log(somar(4)); // 10 → 4 + 3 + 2 + 1

Esse padrão é muito parecido com o do fatorial, mas usamos soma em vez de multiplicação. O raciocínio é sempre o mesmo: reduzir o problema a uma versão menor dele mesmo e confiar que a função sabe resolver essa versão menor.

Quando (não) usar recursão

Apesar de suas vantagens, a recursão não é a melhor escolha para todos os casos. Ela pode ser mais elegante em alguns contextos, mas usa mais memória que um loop tradicional, já que cada chamada fica armazenada na pilha de execução.

Use recursão quando:

• O problema tem uma estrutura naturalmente recursiva
• A solução com loop seria extremamente complexa ou feia
• Você precisa navegar em profundidade por dados aninhados

Evite recursão quando:

• A profundidade das chamadas for muito grande (pode estourar a pilha)
• A lógica puder ser feita de forma simples com um loop
• O desempenho for crítico e você quiser economizar memória

Para praticar

Vamos usar a recursão para um problema clássico: a sequência de Fibonacci.

Cenário: A sequência de Fibonacci começa com 0 e 1, e cada número subsequente é a soma dos dois anteriores (0, 1, 1, 2, 3, 5, 8...). Crie uma função recursiva que encontre o n-ésimo número da sequência.

Requisitos:

1. Crie uma função fibonacci(n: number): number.
2. Defina os casos base: se n for 0 ou 1.
3. Para qualquer outro n, retorne a soma de fibonacci(n - 1) e fibonacci(n - 2).
4. Teste a função com fibonacci(7) para ver se o resultado é 13.

function fibonacci(n: number): number {
  // Casos base
  if (n === 0) {
    return 0;
  }
  if (n === 1) {
    return 1;
  }

  // Chamada recursiva
  return fibonacci(n - 1) + fibonacci(n - 2);
}

console.log(fibonacci(7)); // 13

Recursão é um conceito poderoso. Ao aprendê-la, você amplia sua capacidade de resolver problemas de forma mais expressiva. Na próxima seção, vamos começar a trabalhar com estruturas de dados em TypeScript, começando com arrays.