# 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/)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://leetcode.realtemirov.uz/problems/509.-fibonacci-number.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.