We are all familiar with Fn = F(n-1) + F(n-2)

**Non-Dynamic Way: Recursion**

public static long fibonacci(long number) { if ((number == 0) || (number == 1)) // base cases return number; else // recursion step return fibonacci(number - 1) + fibonacci(number - 2); }

Above, is the recursive non-Dynamic Programming way. As you can see above, The Function "fibonacci()", is called Twice on the return line . This ends up being extremely costly as both functions will eventually be calling the **same values multiple times** as it goes down in a "tree like fashion" because each time the function is called it splits into 2 peices.

To show what I mean here -- Take a look a the pictures below for the the calls of **fibonacci(6)** .

As you can see each number gets split up -- It becomes **costly in memory and time** when we get near the bottom. As in, the higher your Fibonacci Number is, it will take **exponentially **longer to compute,

On a recursive Fibonacci(6)

F(5) is seen once.

F(4) is seen 2 times

F(3) is seen 3 Times

F(2) is seen 5 Times

F(1) is seen 8 Times

F(0) is seen 5 Times.

A total of 18 Repeates for such a low value of N . The number of repeats grows extremely fast your starting N gets larger.

**Summary**:

- Calculating Fibonacci becomes Excessively Slow if you need to have a large Fibonacci Number.
- This is because calculating it this way, creates a Tree like structure

- You are
**repeating previous calculated values**, which is wasteful

**To eliminate Repeats, which results in a Linear solution -- we will use Memoization, which in other words means , Store Previous Values in a list, that can be recalled in the Next cycle.**

public static void DynamicFib(int n) { // We are creating an Array for Storage/Memoization // This will allow us to call previous calculated values without // Having to go into a tree-costly spiral int[] T = new int[n]; // Linearly -- Build the Array with Values for (int i=0;i<n;i++) { // Base-Case if (i <=1) T[i] = i; else { // Store value with T[i-1] (which is calling T's previous value from last cycle) T[i] = T[i-1] + T[i-2]; } } // We can print out the sequence if we like since we built hte values for (int i=0;i<T.length;i++) { System.out.println(i+1 + ": " + T[i]); } }

So as I stated above, the idea is store values that we've already calculated to be used in the next sequence.

If we ran this program with N = 10 then the array would be filled with the following.

T[0] = 0 T[1] = 1 T[2] = 1 T[3] = 2 T[4] = 3 T[5] = 5 T[6] = 8 T[7] = 13 T[8] = 21 T[9] = 34

** Summary:**

**Use Array's to store previous values for the next interation to use****In order set the value of T[6], we simply add T[5] and T[4] together, which is 5 +3 = 8.****Since the operation is only calling a previously stored value, the calculation is extremely fast.****This is a ground-up approach , so you have to start at the T[0] , or the basecase. This is because higher N values need the previous minimum values when creating the table.**