1a. Write a function called, fib_iter(), that has one parameter, n, of type int, and it returns the nth Fibonacci number, Fn.

The Fibonacci Sequence is the series of numbers: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

The next number is found by adding up the two numbers before it:

• the 2 is found by adding the two numbers before it (1+1),
• the 3 is found by adding the two numbers before it (1+2),
• the 5 is (2+3),
• and so on!

In other words, F0 is 0, F1 is 1, F2 is 1, F3 is F1 + F2 = 1 + 1 = 2, F4 is F2 + F3 = 1 + 2 = 3, F5 is F3 + F4 = 2 + 3 = 5, F6 is F4 + F5 = 3 + 5 = 8, etc.

Fi+2 = Fi + Fi+1 for i = 2, 3, ; where F0 = 0 and F1 = 1

In the iterative function, you should use a loop to compute each Fibonacci number once on the way to the number requested and discard the numbers when they are no longer needed.

1b. Next, write a recursive function called, fib_recurs(), that also takes one parameter, n, of type int, and returns the nth Fibonacci number, Fn.

1c. Test out the two functions we just created. Print the 1st, 5th, 15th, 25th, and 45th Fibonacci numbers using both the iterative and recursive solutions. Did you notice the time difference between iteration and recursion? Write your observation down in the comments and explain why.