Fibonacci Number

Factorial

Maximum Subarray

Compute the zero-indexed Fibonacci number with an iterative recurrence.

Return the zero-indexed Fibonacci number `F(n)`, where `F(0)=0`, `F(1)=1`, and `F(n)=F(n-1)+F(n-2)`.

**Input / output**
- Input: `n: integer`
- Output: integer `F(n)`

**Examples**
1. `n = 2` returns `1`.
2. `n = 10` returns `55`.

**Constraints**
- `0 <= n <= 30`

**Follow-up**
Compare iteration, memoized recursion, fast doubling, and matrix exponentiation.

- Fibonacci starts with `F(0) = 0` and `F(1) = 1`.
- Every later value is the sum of the two previous values.
- The input `n` asks for the 0-indexed value `F(n)`.

Understand the Sequence

- The formula naturally translates into recursion.
- However, plain recursion recomputes the same values many times.
- That makes it exponential and too slow for larger `n`.

Recursive Definition

- To compute the next Fibonacci number, we only need the previous two.
- Store them as `a` and `b`, representing consecutive Fibonacci values.
- Repeatedly advance the pair until `a` reaches `F(n)`.

Keep Only the Last Two Values

- Start with `a = 0` and `b = 1`.
- Each loop moves from `(F(i), F(i+1))` to `(F(i+1), F(i+2))`.
- After `n` moves, `a` is the desired answer.

Iterate Up to n

- The iterative solution avoids repeated work.
- Time complexity is O(n).
- Space complexity is O(1) because it stores only two integers.