Introdução à recursividade

Recursão resolve um problema por versões menores dele mesmo

Recursão acontece quando uma função participa da própria solução chamando a si mesma, direta ou indiretamente. A nova chamada recebe uma versão menor do problema; o processo continua até chegar a uma situação simples que pode ser respondida sem outra chamada.

Considere a soma dos inteiros de 1 até n. Para n = 4, queremos:

4 + 3 + 2 + 1 = 10

O problema pode ser decomposto assim:

somarAté(4) = 4 + somarAté(3)
somarAté(3) = 3 + somarAté(2)
somarAté(2) = 2 + somarAté(1)
somarAté(1) = 1 + somarAté(0)
somarAté(0) = 0

A definição recursiva em pseudocódigo fica curta:

FUNÇÃO somarAté(n): INTEIRO
  SE n = 0 ENTÃO
    RETORNAR 0
  FIM SE

  RETORNAR n + somarAté(n - 1)
FIM FUNÇÃO

Essa função pressupõe que n seja um inteiro não negativo. O contrato de entrada precisa ser validado antes ou incorporado à implementação. Recursão não substitui validação; ela descreve como resolver entradas válidas.

Identifique as três partes do contrato recursivo

Uma solução recursiva segura possui três elementos que trabalham juntos:

1. caso-base: responde diretamente e interrompe novas chamadas;
2. caso recursivo: reduz o problema e chama a mesma função;
3. progresso: garante que cada chamada se aproxima do caso-base.

Em somarAté, o caso-base é n = 0. O caso recursivo devolve n + somarAté(n - 1). A medida de progresso é o próprio n, que diminui uma unidade em cada chamada.

Ver apenas um if de parada no código não basta. Pergunte também:

• o argumento realmente muda?
• muda na direção correta?
• pode ultrapassar o caso-base sem coincidir com ele?
• todas as entradas aceitas alcançam a condição de parada?

Essas perguntas fazem para a recursão o mesmo trabalho que uma condição de parada faz para um laço.

Acompanhe primeiro a descida das chamadas

Ao executar somarAté(4), a primeira chamada ainda não sabe o resultado final. Ela precisa esperar somarAté(3):

Chamada ativa	Expressão que fica pendente	Próxima chamada
somarAté(4)	4 + ?	somarAté(3)
somarAté(3)	3 + ?	somarAté(2)
somarAté(2)	2 + ?	somarAté(1)
somarAté(1)	1 + ?	somarAté(0)
somarAté(0)	nenhuma	caso-base retorna 0

Cada chamada fica pendente enquanto a chamada menor trabalha. É útil imaginar uma pilha de cartões: cada cartão registra o valor local de n e o cálculo que ainda precisa terminar.

Isso se conecta diretamente ao escopo de variáveis. Os cinco parâmetros chamados n não formam uma única variável sendo diminuída. Cada chamada possui seu próprio n: 4, 3, 2, 1 ou 0.

Depois do caso-base, os resultados retornam

Quando somarAté(0) retorna 0, a descida termina. As expressões pendentes podem ser concluídas na ordem inversa:

somarAté(0) retorna 0
somarAté(1) retorna 1 + 0 = 1
somarAté(2) retorna 2 + 1 = 3
somarAté(3) retorna 3 + 3 = 6
somarAté(4) retorna 4 + 6 = 10

O return não salta diretamente do caso-base para o primeiro chamador. Cada chamada devolve um resultado para a chamada imediatamente anterior. Por isso, dominar retorno de valores é essencial para ler uma expressão recursiva.

Transforme a definição em JavaScript sem esconder o domínio

Uma implementação pode validar o contrato antes de iniciar ou a cada entrada da função. Nesta versão introdutória, a própria função rejeita valores que não sejam inteiros não negativos:

function somarAte(n) {
  if (!Number.isInteger(n) || n < 0) {
    throw new RangeError("n deve ser um inteiro não negativo");
  }

  if (n === 0) {
    return 0;
  }

  return n + somarAte(n - 1);
}

console.log(somarAte(4)); // 10

A ordem é deliberada:

1. rejeitar entradas fora do domínio;
2. responder ao caso-base;
3. formular o caso recursivo somente para valores restantes.

Usar n <= 0 como caso-base também faria números negativos retornarem zero, mas isso misturaria uma entrada inválida com uma resposta legítima. A condição deve refletir o contrato, não apenas impedir o erro de pilha.

Um caso-base inalcançável continua sendo uma falha

Esta função contém uma condição para n === 0, mas caminha na direção errada:

function somarAte(n) {
  if (n === 0) {
    return 0;
  }

  return n + somarAte(n + 1); // afasta-se de zero
}

Para somarAte(4), os argumentos seriam 4, 5, 6, 7 e assim por diante. O caso-base existe no arquivo, porém nunca é alcançado.

Também pode ocorrer oscilação. Se uma chamada troca 2 por 3 e a seguinte troca 3 por 2, o argumento muda sem progredir. Registre uma medida simples — tamanho restante, distância até zero ou quantidade de elementos ainda não processados — e confirme que ela diminui a cada passo válido.

A pilha de chamadas possui limite

Enquanto a base não retorna, cada chamada precisa preservar informações para continuar depois. Ambientes de execução limitam quantas chamadas podem permanecer pendentes.

Em JavaScript, chamadas demais podem produzir mensagens como RangeError: Maximum call stack size exceeded ou “too much recursion”, dependendo do mecanismo. Python mantém um limite de profundidade para proteger a pilha do interpretador e pode lançar RecursionError. Em C#, uma pilha esgotada por chamadas muito profundas ou sem limite está associada a StackOverflowException.

Não dependa do número exato de chamadas: ele varia entre linguagem, ambiente, plataforma e formato da função. Aumentar limites não corrige um caso-base ausente. Mesmo uma recursão logicamente correta pode ser inadequada para entradas muito profundas.

Recursão e laço podem expressar a mesma repetição

A soma também pode ser escrita iterativamente:

function somarAteComLaco(n) {
  if (!Number.isInteger(n) || n < 0) {
    throw new RangeError("n deve ser um inteiro não negativo");
  }

  let total = 0;

  for (let atual = 1; atual <= n; atual += 1) {
    total += atual;
  }

  return total;
}

As duas versões produzem a mesma resposta para o domínio definido, mas organizam o estado de modos diferentes:

Critério	Recursão	Laço
progresso	aparece no argumento da próxima chamada	aparece na atualização do controle
estado pendente	mantido pelas chamadas	normalmente concentrado em variáveis locais
leitura natural	favorece problemas definidos por subproblemas semelhantes	favorece sequências lineares e contagens
profundidade	pode atingir o limite da pilha	não acumula uma chamada por iteração

Recursão não é uma versão “mais avançada” que deve substituir laços. Use-a quando a estrutura do problema fica mais clara ao repetir a mesma definição sobre uma parte menor — por exemplo, estruturas hierárquicas ou divisões sucessivas. Para uma contagem linear extensa, um laço costuma ser mais direto e previsível.

Também não suponha que toda linguagem otimizará uma chamada recursiva feita no final da função. Essa possibilidade depende da linguagem e da implementação. Projete considerando o comportamento documentado no ambiente real.

Evite repetir o mesmo subproblema sem perceber

Uma função recursiva pode criar mais de uma chamada por nível. A definição ingênua de Fibonacci é um exemplo conhecido:

fib(n) = fib(n - 1) + fib(n - 2)

Ao calcular fib(5), tanto fib(4) quanto fib(3) são chamados; dentro de fib(4), fib(3) aparece novamente. A árvore repete trabalho já realizado.

Nem toda ramificação é errada, mas o diagrama de chamadas precisa revelar quantos subproblemas são criados e se eles se repetem. Técnicas como memoização e programação dinâmica podem evitar recomputação, porém pertencem a um estudo posterior. Nesta introdução, escolha exemplos com uma chamada recursiva por nível para dominar primeiro descida, base e retorno.

Teste por profundidade e fronteiras

Para somarAte, uma matriz curta verifica comportamentos diferentes:

Entrada	Resultado esperado	O que verifica
0	0	caso-base imediato
1	1	um nível antes da base
4	10	descida e retorno em vários níveis
-1	erro de domínio	entrada que não deve iniciar a recursão
2.5	erro de domínio	tipo numérico fora do contrato inteiro

Além do resultado final, faça um teste de mesa com duas colunas:

• na descida, anote o argumento de cada nova chamada;
• no retorno, anote o valor entregue à chamada anterior.

Se a coluna de descida não se aproxima da base, interrompa o rastreamento e corrija a regra. Se o retorno não combina o resultado menor corretamente, a função pode terminar e ainda produzir uma resposta errada.

Pratique com potência inteira

Crie potencia(base, expoente) para expoentes inteiros não negativos. Use estas relações:

potencia(base, 0) = 1
potencia(base, expoente) = base * potencia(base, expoente - 1)

Execute o roteiro:

1. escreva a validação para expoente;
2. identifique o caso-base e justifique por que o retorno é 1;
3. mostre que expoente - 1 se aproxima da base;
4. rastreie a descida de potencia(2, 4);
5. rastreie os retornos 1, 2, 4, 8 e 16;
6. compare a solução com um laço que multiplica quatro vezes;
7. teste expoentes 0, 1, 4, -1 e 2.5.

O exercício está completo quando você consegue explicar não apenas que o resultado é 16, mas qual chamada produziu cada valor intermediário e por que o processo termina.

O que você deve guardar

Uma solução recursiva transforma um problema em uma versão menor do mesmo problema. Ela precisa de um caso-base que responda sem nova chamada, de um caso recursivo que avance de maneira mensurável e de uma regra que combine o resultado devolvido.

Leia a execução em duas fases: as chamadas descem e ficam pendentes; depois a base responde e os valores retornam em ordem inversa. Cada chamada possui parâmetros e variáveis locais próprios. Compare recursão e laço pelo formato do problema, pela clareza e pela profundidade possível — não por uma preferência universal. Com isso, o módulo de organização termina e a próxima etapa da trilha passa a trabalhar com vários valores relacionados em coleções.

Referências

• MDN Web Docs — Recursion. Acesso em 11 set. 2026.
• MDN Web Docs — InternalError: too much recursion. Acesso em 11 set. 2026.
• Python 3 Documentation — sys.getrecursionlimit() e sys.setrecursionlimit(). Acesso em 11 set. 2026.
• Python 3 Tutorial — Defining functions. Acesso em 11 set. 2026.
• Microsoft Learn — C# language specification: exceptions. Acesso em 11 set. 2026.