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

## Table of contents

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,

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

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

```
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,

```
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.

```
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.

```
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)`