Matheus

Posted on Oct 8, 2023 • Edited on Dec 17, 2023

Entendendo a complexidade de algoritmos recursivos x não recursivos

Introdução

Se você estuda programação há algum tempo, com certeza já se deparou com o tema: Recorrência ou Recursividade principalmente ao estudar algoritmos para cálculo de fibonacci ou cálculo de fatorial. Esses são casos clássicos onde a recursividade nos permite desenvolver soluções para esses problemas de uma forma elegante, utilizando poucas linhas de código.

Por outro lado, há casos onde essa simplicidade pode trazer consequências negativas, principalmente se tratando da performance do nosso algoritmo. Vamos analisar os casos abaixo:

Fibonacci recursivo

def fibonacci(number):
    if number <= 1: 
        return number 

    return fibonacci(number - 1) + fibonacci(number - 2)

Aqui temos uma implementação simples de uma função recursiva que fará o cálculo de fibonnacci, vamos analisar a sua complexidade.

Considerando que para cada vez que essa função for executada, ela será executada mais duas vezes, podemos dizer que essa implementação cresce de forma exponencial conforme passamos valores maiores para o parâmetro number

Analisando de perto o caso-recursivo do nosso algoritmo podemos entender em notação Big O da seguinte maneira:

return fibonacci(number - 1) + fibonacci(number - 2) # O(n) + O(n)

Onde simplificando O(n) + O(n) teríamos a complexidade 2 * O(n) e tirando a constante "2", podemos concluir que esse algoritmo possui complexidade O(n)

Em termos de tempo total para execução desse algoritmo utilizando uma máquina com um processador core i5-10210U + 16gb de RAM 2666mhz obtive os seguintes resultados:

Valor de entrada: 5 / Tempo de execução: 0.137 Segundos

Valor de entrada: 20 / Tempo de execução: 0.143 Segundos

Valor de entrada: 40 / Tempo de execução: 20.76 Segundos

Valor de entrada: 80 / Tempo de execução: 7.208 Segundos (Interrupção forçada depois de mais de 1 hora rodando)

Obs: Tempo de execução médio

Fibonacci não recursivo

def fibonacci(n):
  if n == 0:
    return 0

  f_ant = 0
  f_atual = 1

  for i in range(1, n):
    f_prox = f_atual + f_ant
    f_ant = f_atual
    f_atual = f_prox

  return f_atual

Agora vamos analisar essa implementação para cálculo de fibonacci sem o uso de recursão.

Se observarmos de perto o nosso algoritmo, podemos ver que basicamente substituímos a recursão por um laço repetição for que será executado "n" vezes a depender do valor de entrada que passamos por parâmetro, logo podemos concluir que esse é um algoritmo de tempo linear com a complexidade O(n)

for i in range(1, n): # O(n)
    f_prox = f_atual + f_ant # O(1) 
    f_ant = f_atual # O(1) 
    f_atual = f_prox # O(1)

Falando sobre o tempo total de execução desse algoritmo, esses foram os resultados alcançados:

Valor de entrada: 5 / Tempo de execução: 0.135 Segundos

Valor de entrada: 20 / Tempo de execução: 0.15 Segundos

Valor de entrada: 40 / Tempo de execução: 0.159 Segundos

Valor de entrada: 80 / Tempo de execução: 0.160 Segundos

Obs: Tempo de execução médio

Fibonacci recursivo x Não recursivo

Após analisarmos os resultados, podemos concluir que tanto a abordagem recursiva, quanto a comum possuem tempo de execução semelhantes quando utilizamos valores de entrada menores além de possuirem a mesma complexidade em notação Big O.

No entanto podemos ver uma diferença clara no tempo de execução quando utilizamos valores maiores ou iguais a 40 em ambos os algoritmos.

Se utilizarmos por exemplo 40 como valor de entrada para compararmos, esse seria o nosso resultado médio de tempo de execução:

Recursivo: 20.76 Segundos
Não recursivo: 0.159 Segundos

Ou seja, a implementação não recursiva vence com uma diferença de aproximadamente 20.60 segundos mais rápido.

Torre de Hanoi recursivo

Outro problema muito conhecido e possível de ser solucionado com recursividade são as Torres de Hanoi, esse problema consiste em mover todos os discos para outra torre, de forma que você só mova um disco por vez e em hipótese alguma, coloque um um disco maior sobre um disco menor.

Vamos analisar a implementação recursiva abaixo para solucionarmos esse tipo de problema:

def exibeMensagemEtapa(numeroDisco, torreDeOrigem, torreDeDestino):
    print("Mova o disco",numeroDisco,"da origem",torreDeOrigem,"para o destino",torreDeDestino)

def Hanoi(disco, torreDeOrigem, torreDeDestino, torreAuxiliar):
        if disco == 1:
                exibeMensagemEtapa(disco, torreDeOrigem, torreDeDestino)
                return

        Hanoi(disco - 1, torreDeOrigem, torreAuxiliar, torreDeDestino)
        exibeMensagemEtapa(disco, torreDeOrigem, torreDeDestino)
        Hanoi(disco - 1, torreAuxiliar, torreDeDestino, torreDeOrigem)

Considerando que a nossa função recursiva subtrai uma unidade dos nossos discos para cada execução, como teremos duas chamadas, podemos concluir que a cada nível nós dobramos o número de chamadas recursivas, essa estrutura resulta em uma complexidade exponencial de O(2^n)

Agora vamos analisar os resultados do tempo de execução total que conseguimos alcançar:

Valor de entrada: 4 discos / Tempo de execução: 0.376 Segundos

Valor de entrada: 8 discos / Tempo de execução: 0.409 Segundos

Valor de entrada: 20 discos / Tempo de execução: 67.124 Segundos

Valor de entrada: 40 discos / Tempo de execução: 1.678.413 Segundos (Interrupção forçada depois de aproximadamente 27 minutos rodando)

Obs: Tempo de execução médio

Torre de Hanoi não recursivo


def exibeMensagemEtapa(numeroDisco, torreDeOrigem, torreDeDestino):
        print("Mova o disco",numeroDisco,"da origem",torreDeOrigem,"para o destino",torreDeDestino)

def Hanoi(discos, torreDeOrigem, torreDeDestino, torreAuxiliar):
    pilha = []
    pilha.append((discos, torreDeOrigem, torreDeDestino, torreAuxiliar, True))

    while pilha:
        discos, origem, destino, auxiliar, emProgresso = pilha.pop()

        if emProgresso:
            if discos == 1:
                exibeMensagemEtapa(discos, origem, destino)
            else:
                pilha.append((discos - 1, origem, auxiliar, destino, True))
                pilha.append((1, origem, destino, auxiliar, False))
                pilha.append((discos - 1, auxiliar, destino, origem, True))
        else:
             exibeMensagemEtapa(discos, origem, destino)

Agora vamos analisar essa solução para a Torre de Hanoi sem o uso de recursão.

Nessa versão utilizamos um laço de repetição while para manipular a pilha de etapas, a pilha de etapas nos ajuda a rastrear os passos necessários para resolver a torre, como a cada iteração dentro do nosso while nós empilhamos três novas tuplas para as próximas etapas, o que leva a um crescimento exponencial e a uma complexidade O(2^n), uma vez que o número de iterações aumenta conforme adicionamos mais discos ao problema.

Agora vamos analisar os resultados do tempo de execução total que conseguimos alcançar:

Valor de entrada: 4 discos / Tempo de execução: 0.214 Segundos

Valor de entrada: 8 discos / Tempo de execução: 0.217 Segundos

Valor de entrada: 20 discos / Tempo de execução: 34.261 Segundos

Valor de entrada: 40 discos / Tempo de execução: 1.607.752 Segundos (Interrupção forçada depois de aproximadamente 25 minutos rodando)

Obs: Tempo de execução médio

Torre de Hanoi recursivo x Não recursivo

Após analisar os resultados, concluímos que tanto a abordagem recursiva, quanto a iterativa possuem tempo de execução com diferença média de 100 milisegundos quando utilizamos valores de entrada menores além de possuirem a mesma complexidade O(2^n).

Assim como no caso dos algoritmos de fibonacci, também podemos notar uma diferença clara no tempo de execução quando utilizamos valores maiores ou iguais a 20 em ambas as abordagens.

Se utilizarmos por exemplo 20 como valor de entrada para compararmos, esse seria o nosso resultado médio de tempo de execução:

Recursivo: 67.124 Segundos
Não recursivo: 34.261 Segundos

Ou seja, a implementação iterativa (não recursiva) vence com uma diferença aproximada de 32.863 segundos mais rápido.

Complexidade de forma visual

Conclusões finais

A comparação direta dos tempos de execução dos algoritmos nem sempre é a melhor maneira de avaliar o desempenho do nosso código,
uma vez que o tempo de execução pode ser influenciado por diversos fatores, como por exemplo, o hardware que está sendo utilizado ou até mesmo os programas que estão sendo utilizados em paralelo com a execução do seu algoritmo.

Por essa razão, medimos a complexidade dos nossos algoritmos através da notação Big O, ela nos permite descrever como o tempo de execução de um algoritmo pode aumentar em relação ao valor de entrada, independentemente de fatores específicos do hardware ou configuração. Se você leu até aqui e ainda não conhecia sobre a notação Big O, recomendo dar uma olhada nesses links.

Big O Notation: O Pesadelo do Programador Iniciante

Big-O Cheat Sheet