public class FibModule { public static long fib(int n) { //TODO : COMPLETE BODY OF RECURSIVE METHOD return 0; } public static long ifib(int n) { //TODO : COMPLETE BODY OF ITERATIVE METHOD return 0; } public static long mfib(int n) { //TODO : COMPLETE BODY OF MEMOIZATION METHOD return 0; } private static long memo(int n, int[] x) { //TODO : COMPLETE BODY OF MEMOIZATION HELPER METHOD return 0; } Task List:

1. Implement the recursive method fib(n) the nth Fibonacci number in the Fibonacci Sequence. This should be the general algorithm of the Fibonacci Sequence in its basic form.

2. The code in 1 may be inefficient, because it takes too many recursive calls. Write a new version of the Fibonacci method mfib(n) that is still recursive but is more efficient than the one in 1. Do this by creating a helper method memo that accepts an additional parameter, the storage for the previous Fibonacci numbers, that you can carry through and modify during each recursive call.

3. Write a new version of the Fibonacci method ifib(n) that uses iteration to generate the result for the nth value in the Fibonacci sequence.

4. Produce the results/output for all three methods for n = 21, 42 and 49. Use the checkLargeN methods to test your results. Where the results, as expected?