Dynamic Programming in a nutshell
When we talk about optimizing recursion, we talk about Dynamic Programming. This means that solving recursive problems can be done using plain recursive algorithms or Dynamic Programming.
Now, let's apply Dynamic Programming to the Fibonacci numbers, starting with the plain recursive algorithm:
int fibonacci(int k) {
if (k <= 1) {
return k;
}
return fibonacci(k - 2) + fibonacci(k - 1);
}
The plain recursive algorithm for the Fibonacci numbers has a runtime of O(2n) and a space complexity of O(n) – you can find the explanation in Chapter 7, Big O Analysis of Algorithms. If we set k=7 and represent the call stack as a tree of calls, then we obtain the following diagram:
Figure 8.1 – Tree of calls (plain recursion)
If we check the Big O chart from Chapter 7, Big O Analysis of Algorithms...