Programming Challenge: Fibonacci Finder (Jan 2, 2025)

[Jessica Brown]

Write a program that calculates the Nth Fibonacci number. The Fibonacci sequence is defined as follows:

• F(0) = 0
• F(1) = 1
• F(n) = F(n-1) + F(n-2) for n > 1

Requirements:

1. Allow the user to input the value of N.
2. Implement the program in two ways:
   • Using recursion.
   • Using iteration (for efficiency with larger N).
3. Optimize the recursive solution with memoization or dynamic programming to handle larger values of N.

Bonus:

• Print the time taken by both methods to compute the result for comparison.

Example Output:

For N = 10, the result should be 55.