Strategies Flashcards
Dynamic programming vs. recursion
Recursion:
Recursion is a method where the solution to a problem depends on solutions to smaller instances of the same problem. Essentially, it’s a function that calls itself until it reaches a base case. Imagine you’re in a labyrinth and you’re trying every path until you find the exit. If a path doesn’t lead to the exit, you backtrack and try another one. This is a recursive approach.
Dynamic Programming:
Dynamic Programming is a strategy for solving optimization problems. It involves breaking down a problem into simpler, smaller subproblems, solving each of those subproblems just once, and storing their solutions - ideally in a table. So, if the same subproblem occurs, instead of recalculating its solution, you simply look up the previously computed solution, thereby saving computation time.
The main difference between the two is that recursion does not remember the result of each step, while dynamic programming takes advantage of the overlapping subproblems by storing the results. Therefore, dynamic programming avoids the redundant computation present in recursion, which can be quite inefficient for larger inputs.
Think of dynamic programming like checking off each path you’ve tried in the labyrinth and writing down where it led. If you see a path you’ve already tried before, instead of trying it again, you just check your notes. This way, you’re not retracing your steps and you’re saving a lot of time and effort.
