Recursion vs Dynamic Programming

Dynamic programming is an optimization technique that builds upon the idea of recursion. It is used to solve problems that have overlapping subproblems and optimal substructure. While plain recursion can lead to redundant calculations, dynamic programming aims to eliminate this redundancy and improve efficiency.

Key differences between dynamic programming and plain recursion:

1. Memoization: Dynamic programming often involves memoization, which is the process of storing the results of expensive function calls and returning the cached result when the same inputs occur again. This eliminates the need to recompute the same subproblems multiple times.
2. Tabulation: Dynamic programming can also be implemented using tabulation, where the results of subproblems are computed in a bottom-up manner and stored in a table. This avoids the overhead of recursive function calls and can be more efficient in terms of memory usage.
3. Optimal substructure: Dynamic programming is applicable when the problem has an optimal substructure, meaning that the optimal solution to the problem can be constructed from the optimal solutions of its subproblems.
4. Overlapping subproblems: Dynamic programming is effective when the problem has overlapping subproblems, i.e., when the same subproblems are solved multiple times during the recursive process.

When to use dynamic programming:

• When the problem has overlapping subproblems and optimal substructure.
• When plain recursion leads to redundant calculations and inefficient solutions.
• When the problem size is large, and the recursive solution is too slow or exceeds the stack limit.

Let's consider the classic example of the Fibonacci sequence to illustrate the difference:

1#include <iostream>
2#include <unordered_map>
3
4// Plain recursive solution
5int fibonacciRecursive(int n) {
6  if (n <= 1) {
7    return n;
8  }
9  return fibonacciRecursive(n - 1)
10    + fibonacciRecursive(n - 2);
11}
12
13// Dynamic programming solution with memoization
14std::unordered_map<int, int> memoMap;
15
16int fibonacciMemoized(int n) {
17  if (memoMap.find(n) != memoMap.end()) {
18    return memoMap[n];
19  }
20  if (n <= 1) {
21    return n;
22  }
23  int result = fibonacciMemoized(n - 1)
24    + fibonacciMemoized(n - 2);
25  memoMap[n] = result;
26  return result;
27}
28
29int main() {
30  int n = 40;
31  std::cout << "Fibonacci (recursive): "
32    << fibonacciRecursive(n) << "\n";
33  std::cout << "Fibonacci (memoized): "
34    << fibonacciMemoized(n) << "\n";
35}

1Fibonacci (recursive): 102334155
2Fibonacci (memoized): 102334155

In the plain recursive solution, the fibonacciRecursive function calculates the Fibonacci number by recursively calling itself. However, this leads to redundant calculations, as the same Fibonacci numbers are computed multiple times.

On the other hand, the dynamic programming solution with memoization (fibonacciMemoized) uses an unordered map (memoMap) to store the previously computed Fibonacci numbers. Before recursively calling itself, it checks if the result is already memoized. If so, it returns the memoized value, avoiding redundant calculations.

The dynamic programming solution is much more efficient, especially for larger values of n. It eliminates the redundant calculations and significantly reduces the time complexity from exponential to linear.

In summary, dynamic programming is a powerful technique that can be used to optimize recursive solutions by eliminating redundant calculations through memoization or tabulation. It is particularly useful when the problem has overlapping subproblems and optimal substructure. By applying dynamic programming, you can improve the efficiency and scalability of your solutions.