ckorley4

Posted on

# Memoization in Python; an alternative to Recursion

Introduction
One of the most effective recipes for solving Dynamic Programming problems is Memoization.
Memoization is the process of storing the result of the subproblem and calling them again when a similar subproblem is to be solved. This will reduce the time complexity of the problem. If we do not use memorization, similar subproblems are repeatedly solved which can lead to exponential time complexities.

Memorization has one major advantage over conventional computation techniques: it can drastically cut down on the time and resources needed to compute a function’s output. This is especially helpful when dealing with functions that perform repetitive tasks or have a high computational cost. The program can execute more quickly by avoiding the overhead of repeatedly computing the same result by caching the output of these functions.

Memoization is useful in various Python programming applications, such as:

• Recursive functions that call themselves with the same input values
• Computationally intensive functions, such as mathematical functions
• Functions that retrieve data from a remote source or database

Factorial
Let's look a simple example if recursion. The example below uses recursion to compute the factorial of a number. eg.(200)

``````def factorial(input):
if input < 2:
return 1
elif input >= 2:
return input * factorial(input-1)

print(factorial(200))
``````

Memoization
Lets look at the same example with Memoization

``````memo ={}
def memoized(n):
if n in memo:
return memo[n]
elif n == 0:
return 1
else:
x = fact(n-1) * n
memo[n] = x
return x
print(memoized(200))
``````