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
Referências:
https://www.ime.usp.br/~cris/aulas/19_2_5711/slides/aula09.pdf
https://www.ime.usp.br/~am/5711/aulas/aula09h.pdf
https://pt.wikipedia.org/wiki/Sequ%C3%AAncia_de_Fibonacci
https://www.ime.usp.br/~leo/mac/mac122/introducao_recursividade.html
https://www.geeksforgeeks.org/python-program-for-tower-of-hanoi/
https://pt.khanacademy.org/computing/computer-science/algorithms/towers-of-hanoi/a/towers-of-hanoi
http://wiki.icmc.usp.br/images/d/de/Analise_complexidade.pdf
https://www.tabnews.com.br/ritacarolina/analise-do-tempo-de-execucao-de-algoritmos-para-iniciantes
https://www.youtube.com/watch?v=zXBaLEGv0iM&ab_channel=Pontoev%C3%ADrgula
https://www.youtube.com/watch?v=GLKDo13920k&ab_channel=LucasMontano
Top comments (0)