7.4 Coelhos de Fibonacci

Entre suas contribuições mais importantes está o “algoritmo de Dijkstra” sobre o

“problema do caminho mínimo”. Atualmente, o prêmio Dijkstra é concedido a artigos

de relevância no campo da computação distribuída.

 

Figura 7.8 Edsger W. Dijkstra. Fonte: Hamilton Richards | Wikimedia.org.

 

7.4 COELHOS DE FIBONACCI

Um problema clássico resolvido recursivamente é o de calcular a série de Fibonacci.

A série surgiu de uma questão de criação de coelhos: em 12 meses, quantos pares de coelhos haverá em uma criação se admitirmos as seguintes regras simplificadoras:

1. Começamos com um casal de coelhos.

2. Cada casal demora um mês para amadurecer sexualmente.

3. Depois de um mês, a partir do amadurecimento, um casal

gera um novo casal de coelhinhos.

4. Pelo menos durante o experimento, os coelhos não morrem.

Usando essas regras:

1. Ao final do primeiro mês temos um único par de coelhos.

2. Ao final do segundo mês, nasce mais um casal. Temos agora

2 pares.

3. Ao final do mês 3, nasce mais um par do casal original. O

casal que nasceu no mês 2 amadurece e temos 3 casais.

4. Ao final do mês 4, nascem mais 2 casais: um do par original e

outro do casal que nasceu no mês 2. Temos 5 casais.

5. E o processo continua...

Assim, o número total de pares é sempre a soma dos pares

existentes nos dois últimos meses.

 

Figura 7.9 Coelhos de Fibonacci. A cada mês o número de pares de

coelhos é igual à soma dos dois últimos meses.

 

A partir deste problema, Fibonacci, no século XIII, definiu a

sequência que depois levou seu nome: Se n = 0, então o número de Fibonacci é igual a 0. Se n é igual a 1, o número de Fibonacci é igual a 1; senão, ele é igual à soma dos dois números anteriores. Na realidade, a série original de Fibonacci começa com 1, pois na sua época o zero nem era considerado um algarismo, mas usar o zero como início da série facilita nosso propósito. Matematicamente:

 

Então, a série é a sequência: 0 1 1 2 3 5 8 13.

O mais fácil desta série é que sua própria definição já é recursiva. A simplicidade de Python permite que uma função que forneça o n-ésimo termo da série seja praticamente uma tradução direta da definição:

def fib(n):

“““Calcula n-

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

if n == 0:

return 0

elif n == 1:

return 1

else:

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

 

print(fib(9))

 

■ Programa 7.2: Cálculo do n-ésimo termo da série de

Fibonacci.

 

O Programa 7.2 foi escrito para ser a tradução exata da definição, mas podemos fazer um pouco melhor, percebendo que poderíamos colocar uma condição composta no teste inicial e retornando n:

if n == 0 or n == 1:

return n

que pode ser simplificado ainda mais em:

def fib(n):

“““Calcula n-

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

if n < 2:

return n

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

 

print(fib(8))

 

■ Programa 7.3: Cálculo do n-ésimo termo da série de

Fibonacci (Nova versão).

 

Nessa última versão, além de testar se o número é menor que 2,

em vez de fazer dois testes, também foi simplificado o else, que não é necessário, pois a execução somente chega a esse ponto se o teste do if não for executado. De toda maneira, qualquer das opções não fará muita diferença em termos de desempenho. Você escolhe se quer usar a definição diretamente, ou fazer menos testes.

O Programa 7.4 acrescenta impressões da evolução do

programa para você acompanhar o que está acontecendo.

def fib(n):

“““Calcula n-

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

print(‘Função chamada com’,n);

if n < 2:

print(‘Retornando’,n)

return n

resul = fib(n-1) + fib(n-2)

print(‘Retornando soma’,resul);

return resul

 

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

■ Programa 7.4: Cálculo do n-ésimo termo da série de

Fibonacci com impressão dos passos.

 

O resultado é:

Função chamada com 4

Função chamada com 3

Função chamada com 2

Função chamada com 1

Retornando 1

Função chamada com 0

Retornando 0

Retornando soma 1

Função chamada com 1

Retornando 1

Retornando soma 2

Função chamada com 2

Função chamada com 1

Retornando 1

Função chamada com 0

Retornando 0

Retornando soma 1

Retornando soma 3

3

Repare que há 9 chamadas à função. Deve haver, consequentemente, 9 retornos. Cada chamada salva seu estado na pilha e cada retorno tira o estado da função da pilha.

 

EXERCÍCIO 7.4

 

Escreva uma função que calcule o fatorial de um número. O fatorial pode ser

de nido como: