6Recursion 8, 21, 34, 55, 89 ... ]: The Fibonacci sequence is the series of integers 0, 1, 1, 2, 3, 5, See the pattern? Each element in the series is the sum of the preceding two items. There is a...

Extracted text: 6Recursion 8, 21, 34, 55, 89 ... ]: The Fibonacci sequence is the series of integers 0, 1, 1, 2, 3, 5, See the pattern? Each element in the series is the sum of the preceding two items. There is a recursive formula for calculating the nh number of the sequence (the 0th number if Fib(0) = 0): N, if N =0 or 1 Fib(N) = %3D Fib(N- 2) +Fib(N -1) if N>1 1. Write a recursive version of the function Fibonacci. 2. Write a non-recursive version of the function Fibonacci. 3. Compare the recursive and iterative versions for efficiency. 4. Can you think of a way to make the recursive version more efficient? If so, discuss your solution in detail.