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).