Fibonacci Series

Problem Compute the nth Fibonacci number (F0 = 0, F1 = 1, Fn = Fn−1 + Fn−2). Walk from the naive recursion to an optimized solution.

Input / Output

• Input: int n. Output: Fn.

Constraints

• Naive recursion is O(φ^n) — demonstrate you know why (recomputed overlapping subproblems) and fix it.

Example

• n = 10 → 55.

Expected approach

• Progression the interviewer wants: (1) naive recursion, exponential; (2) memoization — cache results, O(n) time / O(n) space; (3) bottom-up DP with two rolling variables — O(n) time, O(1) space; (4) mention fast doubling / matrix exponentiation for O(log n) if pushed. Also: overflow (Fn grows fast — long or BigInteger) and iterative vs recursive stack safety.