DCC003: Algoritmos e Estruturas de Dados I
2013/1

Exercícios 7: Recursividade

Exercício 1. A sequência de Fibonacci, com elementos denotados F0, F1, F2, F3, etc., começa com

F0 = 0 e

F1 = 1.

Os demais números da sequência são definidos recursivamente:

Fi = Fi-1 + Fi-2.

Implemente uma função recursiva para gerar o i-ésimo número da sequência de Fibonacci. Verifique sua função para os primeiros números de Fibonacci: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55.

Verifique o tempo que sua função leva para gerar o milésimo número da sequência (F1000) (dica: sua função provavelmente não terminará de rodar este século). Discuta por que sua função recursiva é lenta. Implemente uma função iterativa para calcular o í-ésimo número da sequência de Fibonacci (por exemplo usando um for).