Loops vs Recursividade

Muita das vezes já nos perguntamos quando é a melhor opção entre recursividade e um ciclo de repetição ou loops.
Isso é muito comum, visto que na faculdade aprendemos sobre recursividade mas muita vezes resolvemos com loops invés de colocar uma função recursiva. Ou podemos pensar ao contrário e colocar funções recursivas invés de loop.

E caímos na questão onde devemos usar um ou outro e qual é a complexidade de tempo de um e outro.

Loops ou Estrutura de Repetições

Estrutura de repetição é uma lógica que permite que determinadas instruções dentro dessa estrutura repitam-se até uma determinada condição.
Essas estruturas assim como estruturas de condições são muito importantes para termos um código mais performático e organizado visto que muitas coisas as vezes são repetitivas.

Existem algumas variações da estrutura de repetição em algumas linguagens tais como: for, do...while, while e o foeach.

A complexidade de tempo ou Big O para uma estrutura de repetição depende do número de iterações que realiza esse número é denominado N em que coloca a complexidade de tempo em O(N), se tiveres uma estrutura de repetição dentro de outra torna ela em O(N^2) sendo o quadrado de iterações.

Dependendo muito dessa características podemos ter uma ideia se o nosso esta a ser performático

Recursividade

Recursividade é um termo que pode ser usado para descrever a repetição de um objecto de forma similar à que já foi mostrada. Em outras palavras é chamar a mesma função dentro dela mesma. Esta função é constituída por casos bases e chamadas da própria função que com uma logica especifica que se quer resolver um problema afim de chegar no caso base. Poderemos ver um exemplo mais abaixo.

Loops Vs Recursividade

Para mostrar a diferenças entre loops e recursividade iremos implementar soluções para encontrar números de Fibonacci:

Números de Fibonacci ou também chamado de Sequência de Fibonacci, é uma sequência de números inteiros infinitos, começando normalmente em 0 e 1, na qual o número sucessor corresponde à soma dos dois anteriores, exemplo: 0, 1, 1, 2, 3, 5, 8, 13, 21..

Os códigos foram implementados em c-sharp, console application

• Implementação usando um For loop

Console.WriteLine("Digite um numero:");
var numCont = Convert.ToInt16(Console.ReadLine());

int prev1 = 1;
int prev2 = 0;

Console.Write(prev2 + " ");
Console.Write(prev1 + " ");

for (int i = 0; i < numCont; i++)
{
    int newNumber = prev1 + prev2;
    Console.Write(newNumber + " ");
    prev2 = prev1;
    prev1 = newNumber;
}

Criamos duas variáveis para conter os dois números de Fibonacci anteriores e dentro de um loop executamos numCont vezes. Isso faz com que a quanto maior for o número que a sequência irá mostrar mais interações ele vai precisar.

1. Implementação usando recursividade

public static partial class Program
{
    static int numCont;
    static int count = 2;
    public static void Main(String[] args)
    {
        Console.WriteLine("Digite um numero:");
        numCont = Convert.ToInt16(Console.ReadLine());


        Console.Write(0 + " ");
        Console.Write(1 + " ");
        Fibonacci(1, 0);
    }

    static void Fibonacci(int prev1, int prev2)
    {
        if (count <= numCont)
        {
            int newNum = prev1 + prev2;
            Console.Write(newNum + " ");
            prev2 = prev1;
            prev1 = newNum;
            count += 1;
            Fibonacci(prev1, prev2);
        }
        else
        {
            return;
        }
    }
}

Como vimos no código acima a nossa função primeiro calcula o newNum, que é a soma entre os dois sucessores, depois disso ele faz novas atribuições aos antecessores, prev1 passa a ser o actual newNum e chama a função novamente com os novos dados e esta processo só termina quano a condição count <= numCont for falsa.

Mas se desejamos encontrar um numero em questão, com recursividade iremos aplicar a mesma fórmula que diz que o F(n) = F(n-1) + F(n - 2). Isso se queremos obter o 50º termo temos que calcular a soma entre o 48º e o 49º.

public static partial class Program
{
    static int numCont;
    public static void Main(String[] args)
    {
        Console.WriteLine("Digite o termo que desejas saber:");
        numCont = Convert.ToInt16(Console.ReadLine());

        Console.WriteLine("o numero é " +  Fibonacci(numCont));
    }

    static int Fibonacci(int num)
    {
        if (num <= 1) return num;
        else return Fibonacci(num - 1) + Fibonacci(num - 2);
    }
}

Nota que a função Fibonacci é chamada duas vezes, e sempre que ele entrará nela mesma ela será chamada mais duas vezes possível. Para cálculos com valores inferiores não se verá tanta diferença, mas isso será um grande problema para cálculos com valores grandes fazendo com que cada instrução tenha o dobro do tempo que ela será processado.

O custo será a dobrar porque as funções recursivas terão que chegar no caso base e isso leva uma quantidade de instruções depois disso as funções acima terão que esperar resultados dessas funções e elas irão tratamento novamente.

Em partes o código esta organizado e simples mais isso leva muito tempo para executar o que é uma desvantagem visto que queremos performar e beleza no código.

Conclusão

Podemos resolver um problema com diferentes algoritmos e com vários conceitos seja ele loops ou Recursividade, mas devemos saber o que esperar deste código no nosso projecto visto que pode ter um impacto significativo, tanto de performance quanto de estética.

A recursividade e loops são duas técnicas diferentes que podem ser usadas em algoritmos diferentes. Mas agora já sabemos quem é mais performático.

Referências:
W3Schools