Menu
If I have a choice to use recursion or memoization to solve a problem which should I use? In other words if they are both viable solutions in that they give the correct output and can be reasonably expressed in the code I'm using, when would I use one over the other?
601
Memoization is a way to potentially make functions that use recursion run faster. As I'll show in an example below, a recursive function might end up performing the same calculation with the same input multiple times. This means it could end up taking longer than the iterative alternative.
When should I use recursion? Recursion is made for solving problems that can be broken down into smaller, repetitive problems. It is especially good for working on things that have many possible branches and are too complex for an iterative approach .
Recursion has absolutely nothing to do with memoization and dynamic programming; it is a completely separate concept.
For Example, when we applied memoization to a recursive algorithm with O(2^n) complexity, we saw a massive performance boost. In this case, accessing a cache is much faster than repeating a calculation. Memoization allows us to use the recursive Fibonacci algorithm.
They are not mutually exclusive. You can use them both.
Personally, I'd build the base recursive function first, and add memoization afterwards, as an optimisation step.
170
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
