Recursividade no C#

 

A recursividade é um conceito de programação em que uma função chama a si mesma para resolver um problema, dividindo-o em subproblemas menores. A recursividade é útil para problemas que podem ser divididos em subproblemas de forma semelhante ao problema original.

Como Funciona a Recursividade em C#

Em C#, a recursividade segue a estrutura básica:

1. Caso Base: O ponto de parada para a recursão, onde a função não faz mais chamadas recursivas e começa a retornar valores.
2. Caso Recursivo: A parte da função que chama a si mesma, normalmente com uma versão mais simples do problema.

Estrutura de uma Função Recursiva

Aqui está a estrutura básica de uma função recursiva:

return tipo NomeDaFuncao(parâmetros)
{
    // Caso base: quando a recursão deve parar
    if (condição de parada)
    {
        return valor;
    }

    // Caso recursivo: a função chama a si mesma com novos parâmetros
    return NomeDaFuncao(parâmetros modificados);
}

Exemplos de Recursividade

1. Fatorial de um Número

O cálculo do fatorial de um número é um exemplo clássico de recursividade. O fatorial de n (denotado por n!) é o produto de todos os números inteiros de n até 1.

A fórmula é:

• n! = n * (n-1)!, com o caso base sendo 1! = 1.

Exemplo de Implementação de Fatorial:

using System;

class Programa
{
    public static void Main()
    {
        int numero = 5;
        int resultado = Fatorial(numero);
        Console.WriteLine($"Fatorial de {numero} é {resultado}");
    }

    // Função recursiva para calcular o fatorial
    public static int Fatorial(int n)
    {
        // Caso base: se n for 1 ou 0, o fatorial é 1
        if (n == 1 || n == 0)
        {
            return 1;
        }
        
        // Caso recursivo: n! = n * (n-1)!
        return n * Fatorial(n - 1);
    }
}

Saída:

Fatorial de 5 é 120

Neste exemplo:

• Caso Base: Quando n é 1 ou 0, a função retorna 1.
• Caso Recursivo: A função chama a si mesma com n - 1, multiplicando o valor retornado por n.

2. Sequência de Fibonacci

A sequência de Fibonacci é outra aplicação clássica de recursividade. A sequência é definida por:

• F(0) = 0
• F(1) = 1
• F(n) = F(n-1) + F(n-2) para n >= 2

Exemplo de Implementação de Fibonacci:

using System;

class Programa
{
    public static void Main()
    {
        int n = 6;
        int resultado = Fibonacci(n);
        Console.WriteLine($"Fibonacci de {n} é {resultado}");
    }

    // Função recursiva para calcular Fibonacci
    public static int Fibonacci(int n)
    {
        // Caso base: F(0) = 0 e F(1) = 1
        if (n == 0)
        {
            return 0;
        }
        else if (n == 1)
        {
            return 1;
        }
        
        // Caso recursivo: F(n) = F(n-1) + F(n-2)
        return Fibonacci(n - 1) + Fibonacci(n - 2);
    }
}

Saída:

Fibonacci de 6 é 8

Neste exemplo:

• Caso Base: Quando n é 0 ou 1, retornamos n.
• Caso Recursivo: A função chama a si mesma para n-1 e n-2, somando os resultados.

3. Busca Binária (Recursiva)

A busca binária é um algoritmo eficiente para encontrar um elemento em um array ordenado. Ele divide o array ao meio, descartando metade a cada comparação.

Exemplo de Implementação de Busca Binária Recursiva:

using System;

class Programa
{
    public static void Main()
    {
        int[] array = { 1, 3, 5, 7, 9, 11, 13, 15 };
        int chave = 7;
        int resultado = BuscaBinaria(array, chave, 0, array.Length - 1);
        Console.WriteLine($"Elemento encontrado no índice: {resultado}");
    }

    // Função recursiva para busca binária
    public static int BuscaBinaria(int[] arr, int chave, int esquerda, int direita)
    {
        // Caso base: quando o intervalo é inválido, o elemento não está no array
        if (esquerda > direita)
        {
            return -1; // Elemento não encontrado
        }

        // Encontrar o meio do array
        int meio = (esquerda + direita) / 2;

        // Caso base: se a chave for igual ao meio, encontramos o elemento
        if (arr[meio] == chave)
        {
            return meio; // Retorna o índice onde o elemento foi encontrado
        }

        // Caso recursivo: se a chave for menor que o valor do meio, procuramos na metade esquerda
        if (chave < arr[meio])
        {
            return BuscaBinaria(arr, chave, esquerda, meio - 1);
        }
        else
        {
            // Caso recursivo: se a chave for maior, procuramos na metade direita
            return BuscaBinaria(arr, chave, meio + 1, direita);
        }
    }
}

Saída:

Elemento encontrado no índice: 3

Neste exemplo:

• Caso Base: Se o intervalo de pesquisa for inválido (esquerda > direita), retornamos -1, indicando que o elemento não foi encontrado.
• Caso Recursivo: A função chama a si mesma, ajustando os limites de pesquisa para a metade do array onde o elemento pode estar.

Dicas Importantes para Recursividade

• Sempre defina um caso base para evitar chamadas recursivas infinitas, o que pode causar um estouro da pilha (stack overflow).
• Evite problemas de desempenho: em algoritmos recursivos como o de Fibonacci, que podem recalcular os mesmos valores várias vezes. Nestes casos, técnicas como memoização podem ser usadas para armazenar os resultados de subproblemas já resolvidos.
• Cuidado com a profundidade da recursão: A recursão pode ser ineficiente se o número de chamadas for muito grande, pois o sistema de execução pode não ser otimizado para chamadas profundas. Em alguns casos, uma solução iterativa pode ser mais eficiente.

Conclusão

A recursividade em C# é uma ferramenta poderosa para resolver problemas que podem ser quebrados em subproblemas semelhantes. Quando usada corretamente, pode tornar o código mais limpo e conciso. No entanto, é importante garantir que a recursão tenha um caso base bem definido e que a profundidade da recursão não ultrapasse os limites do sistema.