# Fibonacci Number
**Difficulty:** EASY
[External](https://leetcode.com/problems/fibonacci-number)
Canonical: https://scaleengineer.com/dsa/problems/fibonacci-number
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Recursion](https://scaleengineer.com/dsa/patterns/recursion), [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Memoization](https://scaleengineer.com/dsa/patterns/memoization)
**Companies:** [Accenture](https://scaleengineer.com/companies/accenture), [Capgemini](https://scaleengineer.com/companies/capgemini), [Cognizant](https://scaleengineer.com/companies/cognizant), [EY](https://scaleengineer.com/companies/ey), [Infosys](https://scaleengineer.com/companies/infosys), [J.P. Morgan](https://scaleengineer.com/companies/j.p.-morgan), [Nvidia](https://scaleengineer.com/companies/nvidia), [SAP](https://scaleengineer.com/companies/sap), [tcs](https://scaleengineer.com/companies/tcs), [Zoox](https://scaleengineer.com/companies/zoox)
---
## Problem
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`

# Approaches
## Brute-Force Recursion
This approach directly translates the mathematical definition of the Fibonacci sequence, `F(n) = F(n - 1) + F(n - 2)`, into a recursive function. The function calls itself for `n-1` and `n-2` and returns their sum. The base cases are `F(0) = 0` and `F(1) = 1`.
**Time:** O(2^n). For each call to `fib(n)`, we make two more calls, leading to a call tree that grows exponentially. This is very slow. · **Space:** O(n). The space complexity is determined by the maximum depth of the recursion stack, which is proportional to `n`.
**Pros:** Very simple to write and understand.; Directly mirrors the mathematical formula.
**Cons:** Extremely inefficient due to redundant computations.; Will result in a 'Time Limit Exceeded' error for `n` greater than around 40.
### Explanation
The algorithm follows the recurrence relation `F(n) = F(n-1) + F(n-2)`. We define a function `fib(n)`. If `n` is 0 or 1, we return `n` as these are the base cases. Otherwise, we make two recursive calls: `fib(n-1)` and `fib(n-2)` and return their sum. This method is simple to understand but highly inefficient because it recomputes the same Fibonacci numbers multiple times. For example, to calculate `fib(5)`, both `fib(4)` and `fib(3)` are called. `fib(4)` in turn calls `fib(3)` and `fib(2)`. The value of `fib(3)` is computed twice, leading to an exponential number of calls.

```java
class Solution {
    public int fib(int n) {
        if (n <= 1) {
            return n;
        }
        return fib(n - 1) + fib(n - 2);
    }
}
```
### Algorithm
- Base Case: If `n` is 0 or 1, return `n`.
- Recursive Step: Otherwise, return `fib(n - 1) + fib(n - 2)`.

## Top-Down Dynamic Programming (Memoization)
This approach optimizes the brute-force recursion by using a technique called memoization. We store the results of expensive function calls (in this case, `fib(k)`) in a cache (like an array or hash map) and return the cached result when the same input occurs again. This avoids recomputing the same Fibonacci numbers over and over.
**Time:** O(n). Each Fibonacci number from 2 to `n` is computed exactly once. The lookups and stores in the memoization table take constant time. · **Space:** O(n). We use an array of size `n+1` for the cache, and the recursion stack can also go up to a depth of `n`.
**Pros:** Drastically improves time complexity compared to brute-force recursion.; Guarantees that each subproblem is solved only once.; Maintains a top-down, recursive structure that is often intuitive.
**Cons:** Uses O(n) space for the cache.; Has the overhead of recursive function calls, which can be slightly less performant than a purely iterative solution.
### Explanation
We use an auxiliary array, say `memo`, of size `n+1` to store computed Fibonacci values. We initialize it with a sentinel value (like 0, since Fibonacci numbers are non-negative) to indicate that a value has not been computed yet. The recursive function first checks if the result for `n` is already in the cache. If it is, it returns the cached value immediately. If not, it computes the value recursively, stores it in the cache, and then returns it. This ensures that each Fibonacci number from 0 to `n` is computed only once.

```java
class Solution {
    int[] memo;
    public int fib(int n) {
        if (n <= 1) {
            return n;
        }
        // Initialize memoization array. 0 can be used as a sentinel
        // because fib(k) > 0 for k > 1.
        memo = new int[n + 1];
        return fib_memo(n);
    }

    private int fib_memo(int n) {
        if (n <= 1) {
            return n;
        }
        // Check if the value is already computed
        if (memo[n] != 0) {
            return memo[n];
        }
        // Compute and store the value
        memo[n] = fib_memo(n - 1) + fib_memo(n - 2);
        return memo[n];
    }
}
```
### Algorithm
- Create a cache array `memo` of size `n+1`.
- Define a recursive helper function `fib_memo(k)`.
- Base Case: If `k <= 1`, return `k`.
- Memoization Check: If `memo[k]` has been computed, return it.
- Recursive Step: Otherwise, compute `fib_memo(k-1) + fib_memo(k-2)`, store the result in `memo[k]`, and then return it.

## Bottom-Up Dynamic Programming (Tabulation)
This approach, also known as tabulation, avoids recursion and computes the Fibonacci numbers iteratively from the bottom up. We use an array to store the Fibonacci numbers as we compute them, starting from `F(0)` and `F(1)`. Each subsequent Fibonacci number `F(i)` is calculated by summing the two preceding values `F(i-1)` and `F(i-2)` which are already available in the array.
**Time:** O(n). We iterate from 2 to `n` once, performing a constant number of operations at each step. · **Space:** O(n). We allocate an array of size `n+1` to store the intermediate Fibonacci values.
**Pros:** Efficient O(n) time complexity.; Avoids recursion overhead, making it slightly faster than memoization in practice.; Conceptually straightforward.
**Cons:** Uses O(n) space, which is not optimal for this problem.
### Explanation
We create a DP array, say `dp`, of size `n+1` to store the sequence. We seed the array with the base cases: `dp[0] = 0` and `dp[1] = 1`. Then, we iterate from `i = 2` up to `n`. In each step of the loop, we fill `dp[i]` with the sum of the previous two elements, `dp[i-1] + dp[i-2]`. The final answer is the value at `dp[n]`. This approach is generally more efficient in practice than memoization because it eliminates the overhead associated with recursive function calls.

```java
class Solution {
    public int fib(int n) {
        if (n <= 1) {
            return n;
        }
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
}
```
### Algorithm
- Handle base cases: if `n <= 1`, return `n`.
- Create an array `dp` of size `n+1`.
- Initialize the first two values: `dp[0] = 0` and `dp[1] = 1`.
- Loop from `i = 2` to `n`.
- In each iteration, calculate `dp[i] = dp[i-1] + dp[i-2]`.
- Return the last element of the array, `dp[n]`.

## Space-Optimized Iterative Approach
This is the most optimized version of the bottom-up approach. We notice that to calculate the current Fibonacci number `F(i)`, we only need the two preceding numbers, `F(i-1)` and `F(i-2)`. There is no need to store the entire sequence in an array. We can simply use two variables to keep track of the last two values and iterate `n` times to get the final result.
**Time:** O(n). We iterate from 2 to `n` once, performing constant time operations in each iteration. · **Space:** O(1). We only use a few variables to store the previous two Fibonacci numbers, regardless of the input `n`.
**Pros:** Optimal O(1) space complexity.; Efficient O(n) time complexity.; No recursion overhead.; Simple and clean implementation.
**Cons:** None for the given constraints. This is the optimal solution in terms of both time and space for this problem.
### Explanation
This approach refines the bottom-up strategy by reducing the space complexity to constant. We start with two variables, `a = 0` (representing `F(0)`) and `b = 1` (representing `F(1)`). We then loop from `i = 2` to `n`. In each iteration, we calculate the current Fibonacci number, `sum = a + b`. Then, we update our variables to slide the window forward for the next iteration: `a` takes the value of `b`, and `b` takes the value of `sum`. After the loop completes, `b` will hold the value of `F(n)`. This is the most common and practical solution for this problem.

```java
class Solution {
    public int fib(int n) {
        if (n <= 1) {
            return n;
        }
        int a = 0; // Represents F(i-2)
        int b = 1; // Represents F(i-1)
        for (int i = 2; i <= n; i++) {
            int sum = a + b; // Represents F(i)
            a = b;
            b = sum;
        }
        return b; // b now holds F(n)
    }
}
```
### Algorithm
- Handle base cases: if `n <= 1`, return `n`.
- Initialize two variables to represent the first two Fibonacci numbers: `a = 0` and `b = 1`.
- Loop from `i = 2` to `n`.
- In each iteration, calculate the next Fibonacci number: `sum = a + b`.
- Update the two variables for the next iteration: `a = b` and `b = sum`.
- After the loop, `b` will hold the value of `F(n)`, so return `b`.

# Solutions
### Java

```java
class Solution {
public
  int fib(int n) {
    int a = 0, b = 1;
    while (n-- > 0) {
      int c = a + b;
      a = b;
      b = c;
    }
    return a;
  }
}

```

### JavaScript

```javascript
/** * @param {number} n * @return {number} */ var fib = function (n) {
  let a = 0;
  let b = 1;
  while (n--) {
    const c = a + b;
    a = b;
    b = c;
  }
  return a;
};

```

### CPP

```cpp
class Solution {
public:
  int fib(int n) {
    int a = 0, b = 1;
    while (n--) {
      int c = a + b;
      a = b;
      b = c;
    }
    return a;
  }
};

```

### Python

```python
class Solution:
    def fib(self, n: int) -> int: a, b = 0, 1 for _ in range(n): a, b = b, a + b return a

```