How I'm learning the basics of Dynamic Programming!
Published: 2022-04-12 00:38:34

Okay so I'm just at the start of my journey deep diving into dynamic programming. It turns out for me personally I needed to lean heavily on the visual aspect of dynamic programming for the concepts to really stick and even still I have trouble. To help me, I've leveraged the assistance of a tool for visualizing algorithms step by step. [AlgoViz](https://algoviz.io/), is the site in question. 

Now, what I want to go over briefly is the recursive Fibonacci algorithm. 

```
let fib = (n) => {
    if (n <= 2) return 1;
    return fib(n - 1) + fib(n- 2);
};
```

When I input this Algorithm into [AlgoViz](https://algoviz.io/), step by step we get the following, which I will attempt to explain for my understanding and yours!

```
1. fib(3) 
	* call function with integer 3 as an input

2. function declares n = 3

3. evaluate (n <= 2)
	* n is currently 3, which is not less than, or equal to 3
	
4. evaluate (n - 1)
	* n is 3, subtract 1 and n == 2

5. declare n = 2
	* now n has been reduced to 2 by previous evaluation 
	
6. evaluate (n <= 2)
	* n = 2, n is less than, or equal to 2

7. call fib(n - 1) 
	* n - 1 = 1
	n is now less than or equal to 2, this is base case
	now the recursive function will start to evaluate the -2 side of the return statement, at this point it will evaluate n at the value of 3 again.
	
8. evaluate (n - 2)
	* 3 - 2 = 1
	this is a base case
	
9. declare n = 1
	* function now receives 1 as input
	
10. evaluate (n <= 2) 
	* 1 is less than or equal to 2
 
11. call fib(n - 2) = 1
	* base case, no further work to be done
	
12. return 1 + 1 (return fib(n-1) + fib(n - 1))
	* the value that was left from evaluating the -1 side of the tree was 1, from step 7. The Value from evaluating the -2 side was also 1, from step 11. 1 + 1 = 2. 
```

A crude tree for this would be:

```
	       fib(3)  declaration (n = 3)									   
              /      \
         -1  /	      \   -2									  
            /          \									 
          (2)         (1) base									 
         /  	        
        /								 
      (1) base   
```
The return value is derived from adding the base cases. 1 + 1;
Here is how the tree would look with fib(4).

```
        	fib(4)  declaration (n = 4)									   
               /      \
         -1   /        \   -2
             /          \
            (3)         (1)
            / \								    
           /   \								   
          /     \								 
        (2)     (1)								 						     
         |
         |
        (1)

// 1+1+1 = 3
```
It was important for me to come to the understanding that the function evaluates the -1 (left) side of the tree first then moves on to the -2 side. You can see this once the base cases are hit at steps 7 and 11. 


This does not touch on memoization or any more advanced concepts as I'm still learning those and felt that as a newbie, the visual aspects help quite a bit. If you're a newbie, I suggest also starting to learn Time/Space complexities and Asymptotic Analysis!

If this helped cheers, this is my first post, let me know if I missed anything or was just blatantly wrong. Feel free to link up with me on [GH ](https://github.com/b00000001) or [LinkedIn](https://www.linkedin.com/in/aaron-deas-ba9908166/)!