CSCI 3212 Lab 1

Due Sunday, 01/28/2024, by midnight (23:59, EST)

Announcements

The goals for this lab assignment are:

Implement and analyze two different methods for computing the nth Fibonacci number, where 0 < n ≤ 200.

Iterative Method:
1. Implement a function fibonacciIterative(n) that calculates the nth Fibonacci number using an iterative approach.
2. Ensure your solution handles edge cases (e.g., n = 1 or 2).
Recursive Method:
1. Implement a function fibonacciRecursive(n) that calculates the nth Fibonacci number using a recursive approach.
2. Consider using memoization to optimize the recursive solution. Optionally, implement a function fibonacciRecursiveMemoized(n) for this.

Time and Space Complexity:
1. Analyze and explain the time and space complexity of both your iterative and recursive implementations. How do these complexities change with the value of n?
2. For the memoized version, discuss how memoization impacts the time and space complexity.
Performance Comparison:
1. Compare the performance of your iterative, recursive, and memoized recursive solutions. You may use empirical data by measuring the execution time of each method for different values of n.
2. Discuss the benefits of using recursion with memoization over the simple recursive approach.

Research and write a brief explanation about how the Fibonacci sequence is used in real-world applications. This could include examples from nature, art, computer science, or other fields.

Ensure your code is well-documented, explaining the logic behind your implementation.
Write test cases for your functions, ensuring they handle various scenarios correctly, including edge cases.

Explore tail recursion and its benefits. Can you modify your recursive solution to be a tail-recursive function? Explain the differences and benefits in terms of performance.

Each student only submits one file, lab_1_lastname.zip(file size less than 5 M), including
1. A Code folder for your Java code files, including all the programming tasks mentioned above.
2. Notes_lab_1_lastname.txt for your notes, including all the writing tasks mentioned above.