7.5 Eficiência da Recursão

A recursão é um ótimo método para resolver certos problemas, mas acaba consumindo muita memória da pilha, e a sequência de chamadas pode ter um custo computacional muito alto. Quando falo de “custo” não estou falando de dinheiro, mas de tempo de processamento e de memória utilizada.

Apesar de ser uma solução elegante, a nossa versão do

programa que calcula a série de Fibonacci pode ser bem ineficiente, mesmo para cálculos de números da série relativamente pequenos. Veja o programa seguinte:

def fib(n):

“““Calcula n-

ésimo termo da série de Fibonacci.”””

if n == 0 or n == 1:

return n

else:

return fib(n-1) + fib(n-2)

for i in range(100):

print(‘fib(‘,i,’):’,fib(i))

■ Programa 7.5: Teste do cálculo do n-ésimo termo da série de

Fibonacci.

O Programa 7.5 simplesmente tem um laço e calcula cada termo

da série até o centésimo. Execute o programa e veja o resultado.

A resposta do programa estará correta, mas a partir de qual

número o programa começa a ficar muito lento?

Se você analisar o programa, vai perceber que podem ser feitas

muitas chamadas recursivas. Essas chamadas se multiplicam gerando um retardo na execução do cálculo. Muitos cálculos são efetuados diversas vezes. No caso do cálculo do quarto termo da série, que vimos neste capítulo, foi calculado três vezes o fatorial de 1. Quando o número da série que é desejado aumenta muito, inúmeros cálculos são efetuados diversas vezes, levando a uma degradação do desempenho.

Você imagina como podemos evitar chamar uma segunda vez um cálculo que já foi efetuado? Uma forma de evitar isto é guardando valores já calculados.

A ideia é a seguinte: se o valor já tiver sido calculado, a função não fará a chamada recursiva, irá retornar o valor já armazenado em uma tabela.

Agora vem a questão de como guardar esses valores calculados. Não use a primeira estrutura que lhe vem à cabeça. Justifique suas escolhas.

Podemos guardar os valores em um dicionário. Desse modo, os índices serão a ordem do número cujo termo da série pretendo calcular, e o conteúdo é seu valor. Veja o Programa 7.6.

fibonacci = {0:0, 1:1}

def fib(n):

“““Calcula n-

ésimo termo da série de Fibonacci.”””

if n not in fibonacci:

fibonacci[n] = fib(n-2) + fib(n-1)

return fibonacci[n]

for i in range(100):

print(‘fib’ + str(i) + ‘):’+ str(fib(i)))

■ Programa 7.6: Série de Fibonacci armazenando resultados

intermediários.

Execute o programa e observe se ficou mais rápido. Muito mais rápido, não? Esta técnica evita o cálculo duplicado dos valores. Com isso o cálculo fica bem rápido. O programa continua sendo recursivo, porém com a ajuda de uma estrutura de dados.

EXERCÍCIO 7.5