Memoization python [closed]

Question

Closed. This question needs to be more focused. It is not currently accepting answers.

---

Want to improve this question? Update the question so it focuses on one problem only by editing this post.

Closed 8 years ago.

Improve this question

What is memoization, how it is used in python ? and also how it is different from recursion. Somewhere I came across a statement that to reduce execution time of a recursive program or function we should use memoization instead of recursion. for eg :

def factorial( n ):
   if n <1:   # base case
       return 1
   else:
       return n * factorial( n - 1 )  # recursive call

If this is a recursive function to calculate factorial, what will be the change when memoization is used ?

Answer 1

Memoization is the storing of results for future use. Python's functools module includes a simple decorator, lru_cache, that handles this for you. So for your example:

@lru_cache(maxsize=None)
def factorial( n ):
   ...

will store each result of factorial, including its recursive calls. That means the next time you call factorial you will not perform the full calculation, but instead stop as soon as you reach a call that has been called before. At that point the result will be pulled from the previously stored results.

These answers might also be useful to you: What is memoization and how can I use it in Python?

Answer 2

If a function is pure, then it will always give the same input. We can take advantage of this by remembering the results of executing a function, saving work for expensive functions like factorial. The results look something like this:

factorialAns = {}
def factorial( n ):
   global factorialAns
   if n in factorialAns:
        return factorialAns[n]
   if n <1:   # base case
       return 1
   else:
       factorialAns[n] = n * factorial( n - 1 )  # recursive call
       return factorialAns[n]