What’s the difference between recursion, memoization and dynamic programming?

Recursion

1. Key Concept: Function calls itself to solve smaller sub-problems
2. Approach: Top-down (Starts with the original problem and breaks it down into smaller sub-problems)
3. Repetitive Computation: High
4. Memory Usage: Low
5. Time Complexity: Can be efficient due to repeated computations

Recursion is essential when a function calls itself, frequently with a new input provided to the child function. It keeps calling itself until an exit condition is met, at which point it sends the results back up the call stack, possibly with some changes made along the way.

Dynamic Programming

1. Key Concept: Break the problem into smaller sub-problems and store the results
2. 2. Approach: Bottom-up (solves sub-problems first and combines their solutions to solve the original problem)
3. 3. Repetitive Computation: Avoids repetitive computation by storing results
4. Memory Usage: High (requires memory for storing results)
5. Time Complexity: More efficient due to reusing stored results

Dynamic programming is mostly an improvement over straightforward recursion. Dynamic Programming can be used to optimize any recursive solution that makes repeated calls for the same inputs. To avoid having to…