Nth Fibonacci Number

Problem Compute the nth Fibonacci number. Give a recursive solution, an iterative solution, and then optimise the recursion with memoization.

Input / Output

• Input: a non-negative integer n.
• Output: F(n), where F(0)=0, F(1)=1, and F(n)=F(n-1)+F(n-2).

Constraints

• n >= 0; handle F(0) and F(1) as base cases.
• Fibonacci grows exponentially — F(93) already overflows a signed 64-bit integer, so for large n either a modulus or big integers must be discussed.
• The interviewer wants all three variants and their complexities, not just the fastest one.

Example

• n = 6 → 8 (the sequence runs 0, 1, 1, 2, 3, 5, 8).
• n = 0 → 0 and n = 1 → 1 — the base cases that off-by-one implementations trip over.