# Calculating Fibonacci Series using Dynamic Programming

*An alternative to calculating it via DAC recursion*

Defining a function to calculate the *Fibonacci *series is one of the many programs every to-be-developer has written at some point. Consider it a “Hello World” program to recursion if you will; they all have more or less written similar lines of code like this:

By the way, you can think of recursion as defining a problem in terms of a simpler version of itself. For instance, the first *Fibonacci *numbers are 0 and 1; the rest are defined as the sum of the previous 2 numbers in the series:

However, these lines of code are not the best or fastest way to get the *Fibonacci *numbers. To see why, lets visualize how the function calls are being made in the above code:

Viewing the tree above, you notice that lot of function calls to the same *Fibonacci *numbers are being called multiple times — this wastes time and space. Couldn’t we just *store *these results somewhere for future reference? Better yet, instead of branching out exponentially, why not simply go from *Fib(0) *to *Fib(1) *to *Fib(2) *and so on to *Fib(n) *in a linear, straight fashion?

These questions from the crux of **Dynamic Programming.**

**Dynamic Programming **is just a strategy to design code; one that involves:

· *Memorization : ***Storing previous solutions in memory**

· *Bottom-Up Approach : ***Solving the simplest problems first**

From these 2 axioms one can devise a function that is further optimized to calculate the *Fibonacci *series: **Start from the beginning of the series, and use those calculated Fibonacci numbers to calculate the next one ad nauseam.**

We know that the first 2 *Fibonacci *numbers are pre-defined, **0 **and **1**.

The next numbers in the series can be calculated by summing up the previous 2 numbers:

Fib(n) = Fib(n-1) + Fib(n-2)

if n >= 2

To calculate the numbers after them, we can initialize 2 variables:

Var0 = 0

Var1 = 1

These variables contain the values of the last 2 numbers in the series respectively; which right now is 0 and 1.

To calculate the next *Fibonacci *number **F3**:

Set Var0 to Var1

andVar1 to Var0 + Var1Var0 = 1

Var1 = 1

F3 = Var1 = 1

Voila! *Var1 *contains our desired result — **F3 **— and *Var0 *has **F2**. Now we can use them to calculate **F4**:

Var0 = Var1 = 1

Var1 = Var1 + Var0 = 1 + 1 = 2

F4 = 2

You can see the pattern forming here as we can get **Fn **by looping the above process, indicating we are formulating the series in a linear fashion.

The above process can be implemented quite readily:

For **F6, **you can observe how *Var0 *and *Var1 *change *(they start at 0 and 1 respectively)*:

Intuitively, observe that the loop runs **n-2 **times for **Fn.**

As stated above, the ** time complexity **will be

**O(n)**— linear.

Hopefully, more programmers-in-training will start learning about this more efficient way of calculating the *Fibonacci *series :)