Fibonacci

João Augusto

Trabalho de Matemática

Relação de Recorrência

2011

Relação de recorrência
Série de Fibonacci
Sendo uma sequência de números naturais, tem início pelo 0 e pelo 1, e o terceiro termo é a soma do primeiro com o segundo, ou seja, 0 + 1, sendo ele o número 1, o quarto termo é o número 2, pois somando os dois números anteriores temos como resultado o número 2. E assim é a série de Fibonacci, o próximo termo será sempre a soma dos dois termos anteriores a ele. Abaixo está a lista dos primeiros termos:

Termo
1 2 3 4 5 6 7 8 9 10 11 12

Soma
0 1 0+1 1+1 1+2 2+3 3+5 5+8 8 + 13 13 + 21 21 + 34 34 + 55

Resultado (Série)
0 1 1 2 3 5 8 13 21 34 55 89

Sua série é definida utilizando recursividade pela fórmula abaixo:

Pode-se explicar sua definição de tal modo, “n” é seu número do termo, podemos ver que se n = 0 então o termo da série será “0”, e quando for n = 1 o termo será 1. Se n > 1, temos então a parte principal da série, onde o F(n-1) é o número anterior ao escolhido, e F(n-2) é o segundo número anterior ao escolhido, e somando os dois teremos um termo da série.

Veja abaixo o algoritmo utilizado para calcular a Série de FIBONACCI, implementado em PYTHON, sem o uso de recursividade: # Criar uma relação de recorrência: # A relação de recorrência utilizada foi a série de "FIBONACCI". Essa série # tem solução. Seu uso sem recursividade é mais vantajoso por utilizar menos espaço # em memória, e por seu tempo de cálculo ser mais rápido. # Série de FIBONACCI: def fibonacci(n): if n in [1,2]: return 1 f1 = f2 = 1 for k in range(n-2): fib = f1 + f2 f1 = f2 f2 = fib return fib # fim fibonacci() # Programa Principal while True: n = int(input('Digite N para calcular a série de FIBONACCI: ')) print(fibonacci(n)) c = input('Deseja continuar? (S/N)') if c in ['n', 'N']: break # Fim algoritmo

Agora o mesmo algoritmo, mas implementado com o uso de recursividade: # Criar uma relação de recorrência: # A relação de recorrência utilizada foi