Nth Fibonacci Number (Recursive, Iterative, Memoized)

Problem: Write code to compute the nth Fibonacci number. Provide a recursive solution, an iterative solution, and then optimize the recursive solution using memoization.

Constraints: n >= 0; Fibonacci sequence defined as F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2).

Example: n = 6 -> 8 (sequence: 0,1,1,2,3,5,8).

Approach:

• Recursive (naive): F(n) = F(n-1) + F(n-2), base cases F(0)=0, F(1)=1. O(2^n) time due to repeated subproblems.
• Iterative: keep two running variables (prev, curr) and loop up to n, O(n) time, O(1) space.
• Memoized recursion: cache computed F(n) values in an array/map so each subproblem is computed once, reducing to O(n) time, O(n) space.