How Dynamic Programming is different from Recursion and Memoization?

Dynamic programming (DP), recursion, and memoization are closely related techniques used in algorithm design, but they have distinct characteristics and applications. Here’s a detailed comparison of these methods:

Recursion

Recursion is a technique where a function calls itself to solve smaller instances of the same problem until it reaches a base case. It is often used for problems that can be broken down into simpler, smaller subproblems of the same type.

Characteristics:

• Top-Down Approach: Recursion typically works in a top-down manner, starting from the main problem and breaking it down into subproblems.
• Base Case: A termination condition is necessary to avoid infinite recursion.
• Overhead: Recursion can be inefficient due to the overhead of multiple function calls and redundant calculations.

Example:

Calculating the Fibonacci sequence using recursion:

int fibonacci_recursive(int n) {
    if (n <= 1) {
        return n;
    } else {
        return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2);
    }
}

This approach has an exponential time complexity $$O(2^n)$$ due to repeated calculations of the same subproblems[2][3].

Memoization

Memoization is an optimization technique that involves storing the results of expensive function calls and reusing them when the same inputs occur again. It is often used in conjunction with recursion to improve efficiency.

Characteristics:

• Top-Down Approach: Like recursion, memoization works in a top-down manner.
• Caching: Results of subproblems are stored in a table (often a hash map or array) to avoid redundant calculations.
• Efficiency: Reduces the time complexity by avoiding repeated work, typically transforming exponential time complexity into polynomial time complexity.

Example:

Calculating the Fibonacci sequence using memoization:

int fibonacci_memo(int n, std::unordered_map<int, int>& memo) {
    if (memo.find(n) != memo.end()) {
        return memo[n];
    }
    if (n <= 1) {
        return n;
    }
    memo[n] = fibonacci_memo(n - 1, memo) + fibonacci_memo(n - 2, memo);
    return memo[n];
}

This approach has a time complexity of $$O(n)$$ due to the caching of results[1][5][8].

Dynamic Programming

Dynamic programming is a method for solving complex problems by breaking them down into simpler subproblems and solving each subproblem only once, storing the results for future use. It can be implemented using either memoization (top-down) or tabulation (bottom-up).

Characteristics:

• Bottom-Up Approach: DP often uses a bottom-up approach, solving smaller subproblems first and using their solutions to build up to the solution of the main problem.
• Tabulation: In the bottom-up approach, results of subproblems are stored in a table, and the solution is built itera...