08. Recursion & Dynamic Programming

Dynamic-Programming

Recursion

• Identifying Recursive Problems:

  • A problem is likely recursive if it can be built off of subproblems.
  • Common patterns in questions:
    • “Design an algorithm to compute the nth…”
    • “Write code to list the first n…”
    • “Implement a method to compute all…”

• Memory Efficiency:

  • Each recursive call adds a new layer to the call stack.
  • Space complexity is O(n) for a stack depth of N.

• Iterative vs. Recursive:

  • Before implementing a recursive solution:
    • Ask how difficult it would be to implement iteratively.
    • Discuss tradeoffs with your interviewer (e.g., readability vs. efficiency).

---

Common Ways to Divide Subproblems

1. Bottom-Up:

   • Start with the simplest case and build up.
   • Example: Iteratively compute the Fibonacci sequence.

2. Top-Down:

   • Break down the problem into smaller subproblems.
   • Solve each subproblem as needed, reusing solutions to avoid redundant work.
   • Example: Recursive Fibonacci with memorization.

3. Half-and-Half:

   • Divide the dataset in half to reduce the problem size.
   • Example: Binary search, merge sort.

---

Dynamic Programming

• What is Dynamic Programming?

  • Simplified: Take a recursive algorithm and identify overlapping subproblems.
  • Cache results of subproblems to avoid redundant computations.

• Iterative Substitution:

  • Convert recursive solutions to iterative ones by caching intermediate results.

• Visualizing the Problem:

  • Draw recursive calls as a tree to:
    • Identify overlapping subproblems.
    • Analyze runtime.

---

Key Takeaways

• Recursive solutions are clean but can be memory-intensive; evaluate alternatives.
• Dynamic programming optimizes recursive problems by caching results, saving time at the cost of space.
• Understand and practice breaking problems into subproblems using different strategies.