C# Recursão

Em Métodos você viu que um método pode chamar outro. E se ele chamar a si mesmo? Isso se chama recursão, e é um jeito de resolver um problema grande dividindo-o numa versão um pouco menor dele mesmo, até chegar numa tão pequena que a resposta é óbvia. Nesta aula você vai escrever métodos recursivos, acompanhar passo a passo o que acontece por dentro e ver, com a mensagem real do .NET, o que acontece quando a recursão não tem fim.

Você vai aprender

O que é recursão e as duas partes de todo método recursivo: o caso base e o passo recursivo.
A contagem regressiva e o fatorial, linha por linha.
A pilha de chamadas: por que cada chamada tem o seu próprio n.
O que acontece sem caso base: o Stack overflow. real, com o código de saída 134.
Por que o Fibonacci recursivo fica lento, e quando um laço é melhor.
Onde a recursão brilha: estruturas que têm partes iguais ao todo, como pastas dentro de pastas.

Todos os programas desta aula rodaram na máquina fictícia da Ana, na pasta ~/cs, com o .NET 10 e o comando dotnet run arquivo.cs.

A ideia: a fila do pão

A Ana está numa fila enorme e quer saber em que posição está. Ela não consegue ver o começo. Então pergunta para a pessoa da frente: "qual é a sua posição?". Essa pessoa também não sabe, e faz a mesma pergunta para a da frente dela. E assim por diante, até chegar em quem está no balcão, que responde sem perguntar nada: "eu sou a primeira". A resposta volta pela fila: "então eu sou a segunda", "então eu sou a terceira"… até chegar na Ana.

Na fila	Na recursão	Nome técnico
Quem está no balcão responde direto: "sou a primeira"	Um caso tão pequeno que a resposta é imediata, sem chamar ninguém	caso base
Os outros perguntam à pessoa da frente e somam 1	O método chama a si mesmo com um problema menor e usa a resposta	passo recursivo
A resposta volta pela fila	Cada chamada termina e devolve o resultado para quem a chamou	o retorno das chamadas

As duas partes são obrigatórias. Sem o caso base, ninguém responde e a pergunta nunca para de andar. Sem o problema ficar menor a cada passo, o caso base nunca chega.

1. A contagem regressiva

Contar(3);

void Contar(int n)
{
    if (n == 0)
    {
        Console.WriteLine("Já!");
        return;
    }
    Console.WriteLine(n);
    Contar(n - 1);
}

$ dotnet run contagem.cs
3
2
1
Já!

if (n == 0) { … return; }: O caso base: quando chegar a zero, mostra Já! e para, sem chamar mais ninguém. É ele que garante o fim.
Console.WriteLine(n);: O trabalho desta chamada: mostrar o próprio número.
Contar(n - 1);: O passo recursivo: o resto da contagem é "a mesma coisa, começando de um número a menos". O n - 1 faz o problema diminuir a cada chamada, até chegar no caso base.

Repare que não há laço nenhum, e mesmo assim a contagem se repete. Quem faz a repetição são as chamadas: Contar(3) chama Contar(2), que chama Contar(1), que chama Contar(0), que mostra Já! e para.

2. Recursão que devolve um valor: o fatorial

O fatorial de um número, escrito 4!, é a multiplicação de todos os inteiros de 1 até ele: 4! = 4 × 3 × 2 × 1 = 24. Repare numa coisa: 4 × 3 × 2 × 1 é 4 × (3 × 2 × 1), ou seja, 4 × 3!. O fatorial de um número é ele vezes o fatorial do anterior. Isso é uma definição recursiva, e vira código quase palavra por palavra:

Console.WriteLine(Fatorial(4));
Console.WriteLine(Fatorial(10));

long Fatorial(int n)
{
    if (n <= 1)
    {
        return 1;
    }
    return n * Fatorial(n - 1);
}

$ dotnet run fatorial.cs
24
3628800

if (n <= 1) return 1;: Caso base: 1! = 1 (e, por definição, 0! = 1). O <= no lugar de == também protege contra um 0.
return n * Fatorial(n - 1);: Passo recursivo: "n vezes o fatorial do anterior". Para calcular esta conta, o C# precisa primeiro do resultado de Fatorial(n - 1); esta chamada fica esperando a outra terminar.
long: O fatorial cresce muito rápido: 10! já passa de três milhões, e 13! não cabe num int. Por isso o retorno é long (Inteiros).

A pilha de chamadas, passo a passo

Para ver a espera acontecendo, esta versão recebe também o nivel de profundidade e escreve com recuo quando cada chamada começa e quando devolve:

Console.WriteLine($"Resultado: {Fatorial(4, 0)}");

long Fatorial(int n, int nivel)
{
    string recuo = new string(' ', nivel * 2);
    Console.WriteLine($"{recuo}Fatorial({n}) começou");
    if (n <= 1)
    {
        Console.WriteLine($"{recuo}Fatorial({n}) devolve 1");
        return 1;
    }
    long resultado = n * Fatorial(n - 1, nivel + 1);
    Console.WriteLine($"{recuo}Fatorial({n}) devolve {resultado}");
    return resultado;
}

$ dotnet run rastro.cs
Fatorial(4) começou
  Fatorial(3) começou
    Fatorial(2) começou
      Fatorial(1) começou                « caso base: ninguém mais é chamado
      Fatorial(1) devolve 1
    Fatorial(2) devolve 2                « 2 × 1
  Fatorial(3) devolve 6                  « 3 × 2
Fatorial(4) devolve 24                   « 4 × 6
Resultado: 24

A descida (as linhas "começou") empilha quatro chamadas, cada uma esperando a de baixo. Quando o caso base responde, as respostas sobem, e cada chamada termina a sua conta. O .NET guarda as chamadas que estão esperando numa área da memória chamada pilha de chamadas (call stack), como pratos empilhados: o último que entrou é o primeiro que sai.

Cada chamada tem o seu próprio n

Na pilha acima existem, ao mesmo tempo, quatro variáveis chamadas n, valendo 4, 3, 2 e 1. Elas não se misturam: como você viu em Escopo, cada chamada cria as suas próprias variáveis e parâmetros. É por isso que, quando Fatorial(2) termina, Fatorial(3) ainda sabe que o seu n é 3.

Experimente: troque Fatorial(4, 0) por Fatorial(6, 0) e veja a pilha crescer. Depois troque o caso base para n <= 3 (e o return 1 para return 6): a descida para mais cedo, e o resultado é o mesmo.

Console.WriteLine($"Resultado: {Fatorial(4, 0)}");

long Fatorial(int n, int nivel)
{
    string recuo = new string(' ', nivel * 2);
    Console.WriteLine($"{recuo}Fatorial({n}) começou");
    if (n <= 1)
    {
        Console.WriteLine($"{recuo}Fatorial({n}) devolve 1");
        return 1;
    }
    long resultado = n * Fatorial(n - 1, nivel + 1);
    Console.WriteLine($"{recuo}Fatorial({n}) devolve {resultado}");
    return resultado;
}

Missão: escreva o método recursivo int Potencia(int b, int e), que calcula b elevado a e. Caso base: qualquer número elevado a 0 é 1. Passo recursivo: b^e = b × b^e-1. Não use laços nem Math.Pow. A saída deve ser:

8
1
81

Console.WriteLine(Potencia(2, 3));
Console.WriteLine(Potencia(5, 0));
Console.WriteLine(Potencia(3, 4));

// escreva aqui o método Potencia

Console.WriteLine(Potencia(2, 3));
Console.WriteLine(Potencia(5, 0));
Console.WriteLine(Potencia(3, 4));

int Potencia(int b, int e)
{
    if (e == 0)
    {
        return 1;
    }
    return b * Potencia(b, e - 1);
}

3. Sem caso base: `Stack overflow.`

Tire o caso base do fatorial e veja o que acontece:

Console.WriteLine(Fatorial(4));

long Fatorial(int n)
{
    return n * Fatorial(n - 1);
}

$ dotnet run infinito2.cs
Stack overflow.
Repeated 174627 times:
--------------------------------
   at Program.<<Main>$>g__Fatorial|0_0(Int32)
--------------------------------
   at Program.<Main>$(System.String[])
$ echo $?
134

O programa compilou sem um aviso sequer, mas quebrou ao rodar. Fatorial(4) chamou Fatorial(3), que chamou Fatorial(2), depois 1, 0, -1, -2… sem nunca parar. Cada chamada que espera ocupa um pedaço da pilha, e a pilha tem tamanho limitado (alguns megabytes). Quando ela enche, acontece o estouro de pilha.

Stack overflow.: "Estouro de pilha". É a System.StackOverflowException, mas o .NET nem chega a escrever o nome completo, como faz com as outras exceções: ele mostra essa linha e mata o programa.
Repeated 174627 times:: "Repetido 174.627 vezes": o caminho entre as linhas tracejadas se repetiu esse tanto antes de a pilha encher. Foram mais de 170 mil chamadas a Fatorial esperando ao mesmo tempo. O número muda um pouco de uma execução para outra (no laboratório já saiu 174.576 e 174.624), porque depende de quanto da pilha já estava ocupado.
g__Fatorial|0_0(Int32): A função local Fatorial, com um parâmetro int (o nome que o .NET dá ao int é Int32). Repare que, aqui, não aparece o número da linha.
at Program.<Main>$(System.String[]): Quem fez a primeira chamada: o programa principal.
134: O código de saída. É o mesmo de uma exceção não tratada no Linux: o processo foi abortado.

O try/catch não salva

A maioria das exceções pode ser "pega" com try/catch e tratada (aula try e catch). A StackOverflowException, não: o .NET encerra o programa na hora, sem passar pelo catch. Este programa tenta, e não consegue:

try
{
    Afundar(1);
}
catch (Exception e)
{
    Console.WriteLine($"Peguei: {e.GetType().Name}");
}

void Afundar(int n)
{
    Afundar(n + 1);
}

$ dotnet run trycatchso.cs
Stack overflow.
Repeated 261746 times:
--------------------------------
   at Program.<<Main>$>g__Afundar|0_0(Int32)
--------------------------------
   at Program.<Main>$(System.String[])
$ echo $?
134

A linha Peguei: nunca aparece. A única defesa é escrever o caso base certo.

No editor do guia

O editor também mostra o Stack overflow., o bloco repetido, o Main e o código 134. Só o número do Repeated … times: é outro (perto de 999), porque o .NET do editor roda dentro do navegador, com uma pilha bem menor que a do Linux. Como esse número muda de uma máquina para outra, nenhuma missão depende dele.

Os enganos que levam a uma recursão sem fim são sempre um destes três:

Engano	Exemplo	Conserto
Esqueceu o caso base	`return n * Fatorial(n - 1);` sozinho	`if (n <= 1) return 1;` antes
O problema não diminui	`Fatorial(n)` no lugar de `Fatorial(n - 1)`	Confira se cada chamada fica mais perto do caso base
O caso base nunca é alcançado	`if (n == 0)` e a chamada pula de 2 em 2 começando de um ímpar (`n - 2` a partir de 5: 5, 3, 1, -1…)	Use `<=` no caso base

4. Recursão nem sempre é a melhor escolha

A sequência de Fibonacci começa com 0 e 1, e cada número seguinte é a soma dos dois anteriores: 0, 1, 1, 2, 3, 5, 8, 13… A definição é recursiva (Fib(n) = Fib(n-1) + Fib(n-2)), e o código também. Mas este programa conta quantas chamadas acontecem:

long chamadas = 0;
for (int n = 10; n <= 30; n += 10)
{
    chamadas = 0;
    long f = Fib(n);
    Console.WriteLine($"Fib({n}) = {f}, com {chamadas:N0} chamadas");
}

long Fib(int n)
{
    chamadas++;
    if (n < 2) return n;
    return Fib(n - 1) + Fib(n - 2);
}

$ dotnet run fib.cs
Fib(10) = 55, com 177 chamadas
Fib(20) = 6765, com 21.891 chamadas
Fib(30) = 832040, com 2.692.537 chamadas

Para o Fib(30), quase 2,7 milhões de chamadas. Cada chamada se divide em duas, e as duas recalculam as mesmas coisas: Fib(30) calcula Fib(28) pelo caminho de Fib(29) e, de novo, por conta própria. A cada 10 a mais no n, o trabalho fica mais de cem vezes maior. Um laço simples, que guarda os dois últimos números, faz o mesmo com 30 voltas:

Console.WriteLine(Fib(30));
Console.WriteLine(Fib(90));

long Fib(int n)
{
    long anterior = 0, atual = 1;
    for (int i = 0; i < n; i++)
    {
        long proximo = anterior + atual;
        anterior = atual;
        atual = proximo;
    }
    return anterior;
}

$ dotnet run fibloop.cs
832040
2880067194370816120

O Fib(90) saiu na hora. Na versão recursiva, seriam uns 9 quintilhões de chamadas: mesmo a um bilhão de chamadas por segundo, quase 300 anos.

O fatorial também tem limite

Com long, o maior fatorial que cabe é o de 20. O de 21 passa do limite, e o C# não avisa: o número "dá a volta" e vira negativo (o estouro de Inteiros):

$ dotnet run fat21.cs                « Fatorial(20) e Fatorial(21)
2432902008176640000
-4249290049419214848

5. Onde a recursão brilha: pastas dentro de pastas

A recursão é natural quando a estrutura do problema é recursiva: uma coisa que contém coisas do mesmo tipo. Uma pasta contém arquivos e outras pastas, que contêm arquivos e outras pastas… Para listar tudo, o método lista a pasta e chama a si mesmo para cada subpasta. O caso base é implícito: uma pasta sem subpastas não chama ninguém.

Directory.CreateDirectory("loja/2026/janeiro");
Directory.CreateDirectory("loja/2026/fevereiro");
Directory.CreateDirectory("loja/fotos");
File.WriteAllText("loja/2026/janeiro/vendas.txt", "");
File.WriteAllText("loja/fotos/caderno.png", "");
Listar("loja", 0);

void Listar(string pasta, int nivel)
{
    Console.WriteLine($"{new string(' ', nivel * 2)}{Path.GetFileName(pasta)}/");
    foreach (string arquivo in Directory.GetFiles(pasta).Order())
    {
        Console.WriteLine($"{new string(' ', nivel * 2 + 2)}{Path.GetFileName(arquivo)}");
    }
    foreach (string sub in Directory.GetDirectories(pasta).Order())
    {
        Listar(sub, nivel + 1);
    }
}

$ dotnet run pastas.cs
loja/
  2026/
    fevereiro/
    janeiro/
      vendas.txt
  fotos/
    caderno.png

As cinco primeiras linhas só criam as pastas e arquivos de exemplo (aula Pastas e Caminhos). O Listar não sabe quantos níveis existem, e não precisa saber: cada chamada cuida de uma pasta e entrega as subpastas para "outra cópia de si mesma". Com um laço, você teria de controlar à mão a lista de pastas que faltam visitar. Árvores, menus dentro de menus e expressões com parênteses dentro de parênteses são outros casos assim.

Formas diferentes: recursão × laço

Todo problema recursivo pode ser escrito com um laço, e vice-versa. O fatorial com for:

Console.WriteLine(Fatorial(4));
Console.WriteLine(Fatorial(10));

long Fatorial(int n)
{
    long resultado = 1;
    for (int i = 2; i <= n; i++)
    {
        resultado *= i;
    }
    return resultado;
}

$ dotnet run fatloop.cs
24
3628800

	Recursão	Laço
Leitura	Fica parecida com a definição ("n vezes o fatorial do anterior")	Mostra o passo a passo
Memória	Cada chamada ocupa a pilha; muitas chamadas estouram	Usa só as variáveis do laço
Limite	De dezenas a centenas de milhares de níveis, conforme o método	Nenhum
Melhor para	Estruturas que se repetem dentro de si (pastas, árvores)	Contagens, somas, sequências

Regra do guia

Em C#, use um laço quando ele for simples (fatorial, somas, Fibonacci). Use recursão quando o problema tiver partes iguais ao todo e a profundidade for pequena (uma árvore de pastas raramente passa de algumas dezenas de níveis). E, ao escrever um método recursivo, escreva primeiro o caso base.

Uma recursão também pode ser escrita na forma com classe (static long Fatorial(int n)), e funções locais podem ser recursivas, como todas desta aula. Em Funções Locais você vai ver uma função local recursiva dentro de outro método.

Quando dá errado

Stack overflow. e código de saída 134

O que significa: a recursão não parou, e a pilha de chamadas encheu. O compilador não avisa: o erro só aparece ao rodar.

Como consertar: confira as três coisas: existe um caso base? Cada chamada fica mais perto dele? O caso base é alcançado para qualquer valor (prefira <= a ==)? Se a lógica está certa e mesmo assim estoura, a profundidade é grande demais para a pilha: troque por um laço.

O programa fica parado, sem mostrar nada

O que significa: provavelmente uma recursão como a do Fibonacci, que se divide em duas chamadas a cada passo: ela termina, mas só depois de bilhões de chamadas.

Como consertar: aperte Ctrl+C no terminal para interromper. Conte as chamadas (como no fib.cs) para confirmar e reescreva com um laço.

O resultado vira negativo ou estranho

O que significa: o valor passou do limite do tipo (21! num long). Não é erro da recursão, é estouro de inteiro.

Como consertar: limite o n, use um tipo maior (System.Numerics.BigInteger não tem limite) ou ligue a conferência com checked para virar uma exceção (Inteiros).

Referência rápida

Termo	O que é
Recursão	Um método que chama a si mesmo
Caso base	A situação em que o método responde direto, sem se chamar; garante o fim
Passo recursivo	A chamada a si mesmo com um problema menor
Pilha de chamadas	Onde o .NET guarda as chamadas que estão esperando; cada uma com as suas variáveis
`Stack overflow.`	A pilha encheu (recursão sem fim ou funda demais); o programa morre com código 134, sem `catch` possível

Exercícios

1. O nome da parte que para

Como se chama a parte do método recursivo que responde sem chamar a si mesmo? (duas palavras)

2. Quanto vale?

Com int S(int n) => n == 0 ? 0 : n + S(n - 1);, quanto vale S(4)?

3. O código de saída

Com que código de saída um programa termina no Linux depois de um Stack overflow.?

4. O que falta em int Contar(int n) { return Contar(n - 1); }?

O passo recursivo O caso base: nada faz a recursão parar Um laço for Nada: está correto

5. Um try/catch em volta de uma recursão infinita…

pega a StackOverflowException e o programa continua faz o compilador avisar do problema não adianta: o .NET encerra o programa sem passar pelo catch transforma a recursão num laço

6. Por que o Fibonacci recursivo de 30 fez 2,7 milhões de chamadas?

Porque cada chamada se divide em duas, e os mesmos valores são recalculados muitas vezes Porque faltou o caso base Porque long é lento Porque o laço for do programa rodou 2,7 milhões de vezes

Missão final: inverter um texto

Missão: escreva o método recursivo string Inverter(string texto). Caso base: um texto com 0 ou 1 letra já está invertido (devolva ele mesmo). Passo recursivo: o texto invertido é "o resto invertido" seguido da primeira letra, ou seja, Inverter(texto.Substring(1)) + texto[0]. Não use laços. A saída deve ser:

ahnijoL
ovo
[]

Console.WriteLine(Inverter("Lojinha"));
Console.WriteLine(Inverter("ovo"));
Console.WriteLine($"[{Inverter("")}]");

// escreva aqui o método Inverter

Console.WriteLine(Inverter("Lojinha"));
Console.WriteLine(Inverter("ovo"));
Console.WriteLine($"[{Inverter("")}]");

string Inverter(string texto)
{
    if (texto.Length <= 1)
    {
        return texto;
    }
    return Inverter(texto.Substring(1)) + texto[0];
}

A última chamada passa um texto vazio. Se o seu caso base fosse texto.Length == 1, o Substring(1) de um texto vazio daria ArgumentOutOfRangeException. Por isso o <= 1.

Resumo

Recursão: um método que chama a si mesmo, com um problema menor a cada vez.
Todo método recursivo tem um caso base (responde direto e para) e um passo recursivo (chama a si mesmo, mais perto do caso base). Escreva o caso base primeiro.
As chamadas que esperam ficam na pilha de chamadas, cada uma com as suas próprias variáveis.
Sem fim, a pilha enche: Stack overflow., código 134, e nenhum catch segura. O compilador não avisa.
Recursão que se divide em duas (Fibonacci) pode ficar lentíssima. Para contas simples, prefira um laço; a recursão brilha em estruturas que se repetem dentro de si, como pastas.