Fibonacci Series
Problem Compute the nth Fibonacci number (F0 = 0, F1 = 1, Fn = Fn−1 + Fn−2), progressing from the naive recursion to an optimized solution.
Input / Output
- Input: an integer n.
- Output: Fn.
Constraints
- Naive recursion is O(φ^n) — be ready to explain why (recomputed overlapping subproblems) and fix it.
- Fn grows fast; guard against overflow (use 64-bit or big integers).
Example
- n = 10 → 55.
asked …