# Fibonacci Number: From recursion to memoization and ultimately space-optimized solution

Let’s evaluate the Classic Dynamic Programming problem, `Fibonacci Number` in a crispy way.

We will start solving the problem from a recursive solution and later step by step we will use memoization and space optimization.

The `Fibonacci Number` or `Fibonacci Sequence` is as follows,

0, 1, 1, 2, 3, 5, 8, 13 and so on.

After the first two numbers, each number is the sum of the previous two numbers.

### Recursive Solution

So, the constant part of the base case of the sequence is first two numbers are always 0 and 1. To calculate the rest of the numbers we will consider,

```javascript
f(n) = f(n - 1) + f(n - 2)
```

With the base case and driven formula, our recursive solution will be,

```typescript
function fibonacciNumber(n: number): number {
    const dp = new Array(n + 1).fill(-1);
    const helper = (step) => {
        if (dp[step] !== -1) {
            return dp[step];
        }

        if (step === 0 || step === 1) {
            return step;
        }

        const first = helper(step - 1);
        const second = helper(step - 2);

        dp[step] = first + second;
        
        return dp[step];
    }

    return helper(n);
};
```

This is a bottom-up approach. However, if we go to a tabulation format, we can design a top-to-bottom approach.

### Memoization

We are maintaining an array `dp` where we are keeping the sequence number. After the first two values, the next one is the sum of the previous two values. In a more simplified way, we can say,

```typescript
dp[n] = dp[n - 1] + dp[n - 2]
```

Now, the first two values are known and we will update these two values initially. Then with a simple loop we will calculate the rest of the sequence.

```typescript
function fibonacciNumber(n: number): number {
    const dp = new Array(n + 1);
    dp[0] = 0;
    dp[1] = 1;

    for (let i = 2; i <= n; i += 1) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    return dp[n];
};
```

With the implementation, we can see the space complexity is `O(n)`. With this in mind, can we do more space optimization?

### Space Optimization

Since each of the values just depends on the previous two values, we can just keep these previous two values and calculate the current one.

```typescript
function fibonacciNumber(n: number): number {
	 if (n < 2) {
        return n;
    }
    let prev1 = 0;
    let prev2 = 1;

    for (let i = 2; i <= n; i += 1) {
        const temp = prev2;
        prev2 = prev1 + prev2;
        prev1 = temp;
    }

    return prev2;
};
```

With these constant values, now, we can now optimize the space to `O(n)`