. Fibonacci Redux:

1. Compare Prof. Neville's recursive version of the Fibonacci function to retrieve the nth Fibonacci term (e.g. recfib()) to his iterative version (itfib()) by showing the series of average RecFib timings for all numbers in the range [5 ... 35] -- and the series of average itFib timings for evenly-spaced numbers (e.g. every 500?) from [10,000...100,000] -- in two separate graphs. Explain the reason for the different graph-shapes in a short paragraph.

2. Implement your own version of RecFib() that recursively calls itself twice (i.e. builds a binary tree of function-calls, similar to Neville's original RecFib() ), yet takes about the same time (i.e. has the same execution-time growth-rate) as Neville's iterative itFib() version. (Note: reimplementing the iterative function in a recursive-function's clothing is not acceptable here. Your recursive-call structure should form a binary tree of calls that is smaller than Neville's was, by adding some additional lines and/or variables to Neville's code, that allow you to "remember" the solutions to problems already solved)

Create a single graph now showing both your new recursive function's average timings (e.g. for all numbers from [100 1000] in steps of 100), and itFib's performance on that range. Include the code for your function in your report, and explain how your function avoided all the redundant work Neville's original recFib() function allowed

Note:- It must be in python