> For the complete documentation index, see [llms.txt](https://leetcode.realtemirov.uz/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://leetcode.realtemirov.uz/problems/509.-fibonacci-number.md).

# 509. Fibonacci Number

🟩 Easy

The *Fibonacci numbers*, commonly denoted `F(n)` form a sequence, called the *Fibonacci sequence*, such that each number is the sum of the two preceding ones, starting from `0` and `1`. That is,

> F(0) = 0, F(1) = 1\
> F(n) = F(n - 1) + F(n - 2), for n > 1.

Given `n`, calculate `F(n)`.

## Example 1

> **Input**: n = 2\
> **Output**: 1\
> **Explanation**: F(2) = F(1) + F(0) = 1 + 0 = 1.

## Example 2

> **Input**: n = 3\
> **Output**: 2\
> **Explanation**: F(3) = F(2) + F(1) = 1 + 1 = 2.

## Example 3

> **Input**: n = 4\
> **Output**: 3\
> **Explanation**: F(4) = F(3) + F(2) = 2 + 1 = 3.

## Constraints

* `0 <= n <= 30`

## Solution

My Solution (Recursive)

```go
func fib(n int) int {
    if n <= 1 {
        return n
    }

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

Optimal Solution (Iterative with Space Optimization)

```go
func fib(n int) int {
    if n <= 1 {
        return n
    }
    
    // Only keep track of last two numbers
    prev2, prev1 := 0, 1
    
    // Build up to n iteratively
    for i := 2; i <= n; i++ {
        // Calculate current number and update previous two
        curr := prev1 + prev2
        prev2, prev1 = prev1, curr
    }
    
    return prev1
}
```

### Approach

This solution uses iterative approach with space optimization:

1. Key Insight:
   * Each Fibonacci number only depends on previous two
   * No need to store entire sequence
   * Can use variables instead of array
2. Implementation Strategy:
   * Keep track of only last two numbers
   * Update in each iteration
   * Use parallel assignment for clean swaps
3. Processing Rules:
   * Handle base cases (n ≤ 1) directly
   * Build sequence iteratively
   * Return last calculated number

### Complexity Analysis

#### Time Complexity: O(n)

* Single pass from 2 to n
* Each number calculated exactly once
* All operations are O(1)
* Linear growth with input size

#### Space Complexity: O(1)

* Only constant extra space used:
  * Two variables for previous numbers
  * One variable for current calculation
  * Loop counter

### Why it works

* Mathematical Properties:
  * F(n) = F(n-1) + F(n-2)
  * Only need previous two numbers
  * Sequence grows linearly
* Optimization Details:
  * No recursion overhead
  * No array allocation
  * Minimal variable usage
  * Clean variable swapping
* Key Improvements over Recursive:
  * No stack overflow risk
  * No duplicate calculations
  * Better space efficiency
  * Faster execution
* Alternative Approaches (Not Implemented):
  * Matrix exponentiation: O(log n) time
  * Closed form (Binet's formula)
  * Dynamic programming with array
  * Tail recursion
* Edge Cases Handled:
  * n = 0 returns 0
  * n = 1 returns 1
  * n = 2 first calculated case
  * Works up to n = 30 (constraint)

![result](/files/YJohT9phRjH88ECbMEqD)

Leetcode: [link](https://leetcode.com/problems/fibonacci-number/description/)