# LeetCode 509: Fibonacci Number

## Problem Restatement

The Fibonacci sequence is defined as:

- `F(0) = 0`
- `F(1) = 1`

For all `n > 1`:

$$
F(n)=F(n-1)+F(n-2)
$$

We are given an integer `n`.

We need to return the value of `F(n)`.

The official problem asks us to compute the `n`th Fibonacci number using the standard recurrence definition.

## Input and Output

| Item | Meaning |
|---|---|
| Input | An integer `n` |
| Output | The `n`th Fibonacci number |
| Base cases | `F(0) = 0`, `F(1) = 1` |

Function shape:

```python
class Solution:
    def fib(self, n: int) -> int:
        ...
```

## Examples

Example 1:

```python
n = 2
```

Using the recurrence:

```text
F(2) = F(1) + F(0)
     = 1 + 0
     = 1
```

So the answer is:

```python
1
```

Example 2:

```python
n = 3
```

```text
F(3) = F(2) + F(1)
     = 1 + 1
     = 2
```

So the answer is:

```python
2
```

Example 3:

```python
n = 4
```

```text
F(4) = F(3) + F(2)
     = 2 + 1
     = 3
```

So the answer is:

```python
3
```

## First Thought: Direct Recursion

The definition itself naturally suggests recursion.

```python
def fib(n):
    if n <= 1:
        return n

    return fib(n - 1) + fib(n - 2)
```

This directly follows the recurrence relation.

However, it recomputes the same values many times.

For example:

```text
fib(5)
├── fib(4)
│   ├── fib(3)
│   └── fib(2)
└── fib(3)
```

The subtree `fib(3)` appears repeatedly.

## Problem With Recursive Recalculation

The recursive solution performs overlapping work.

The same Fibonacci values are recomputed many times.

The running time grows exponentially:

```text
O(2^n)
```

This becomes inefficient even for moderate values of `n`.

We need to reuse already computed results.

## Key Insight

Each Fibonacci number depends only on the previous two numbers.

So instead of storing the entire sequence, we only need two variables:

| Variable | Meaning |
|---|---|
| `a` | Previous Fibonacci number |
| `b` | Current Fibonacci number |

At each step:

```text
next = a + b
```

Then shift forward:

```text
a = b
b = next
```

This is dynamic programming with constant memory.

## Algorithm

Handle small values first:

```python
if n <= 1:
    return n
```

Initialize:

```python
a = 0
b = 1
```

These represent:

```text
F(0), F(1)
```

Then repeat from `2` to `n`:

1. Compute the next Fibonacci value.
2. Shift the window forward.

Finally, return `b`.

## Correctness

Initially:

```text
a = F(0)
b = F(1)
```

At each iteration, the algorithm computes:

```text
next = a + b
```

By the Fibonacci recurrence, this equals the next Fibonacci number.

Then the variables are updated:

```text
a becomes the old b
b becomes the new Fibonacci number
```

So after every iteration:

```text
a = F(i-1)
b = F(i)
```

When the loop finishes, `b` equals `F(n)`.

Therefore the algorithm returns the correct Fibonacci number.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | One loop iteration per Fibonacci step |
| Space | `O(1)` | Only two variables are stored |

## Implementation

```python
class Solution:
    def fib(self, n: int) -> int:
        if n <= 1:
            return n

        a = 0
        b = 1

        for _ in range(2, n + 1):
            a, b = b, a + b

        return b
```

## Code Explanation

Small inputs are handled immediately:

```python
if n <= 1:
    return n
```

Initialize the first two Fibonacci values:

```python
a = 0
b = 1
```

Each iteration computes the next Fibonacci number:

```python
a, b = b, a + b
```

This simultaneously updates both variables.

After the update:

```text
a becomes the old current value
b becomes the next Fibonacci value
```

The loop continues until reaching `F(n)`.

Finally:

```python
return b
```

returns the answer.

## Testing

```python
def test_fib():
    s = Solution()

    assert s.fib(0) == 0
    assert s.fib(1) == 1
    assert s.fib(2) == 1
    assert s.fib(3) == 2
    assert s.fib(4) == 3
    assert s.fib(10) == 55

    print("all tests passed")
```

Test meaning:

| Test | Why |
|---|---|
| `0` | First base case |
| `1` | Second base case |
| `2` | First recursive combination |
| `3` | Small transition case |
| `4` | Multiple iterations |
| `10` | Larger standard Fibonacci value |