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, 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, 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 or LinkedIn!
Top comments (0)