1. Calculating Fibonacci Numbers
In mathematical terms, the sequence of Fibonacci numbers is defined by the recur-
rence relation Fn=Fn−1+Fn−2,where F0= 0 andF1= 1 .
First think about how to recursively determine the values of specific Fibonacci
numbers. You are required to construct a class called Fibonacci that reads in anumber n and outputs the n-th Fibonacci numberFn.
2.More Efficient Fibonacci Calculation
In order to calculate Fn, you need to recursively calculate Fn−1 and Fn-2. Then, to aclculateF n−1, we needFn−2(again!) andFn−3. This means that many Fibonaccinumbers may be calculated multiple times.Reproduce yourFibonacciclass in another class called EfficientFibonacci.
Make this class efficient by storing calculated numbers. The recursive function should not be called for a number that has already been calculated.