DEV Community

Cover image for Memoization in Python; an alternative to Recursion

Posted on

Memoization in Python; an alternative to Recursion

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

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)

Enter fullscreen mode Exit fullscreen mode

Lets look at the same example with Memoization

memo ={}
def memoized(n):
    if n in memo:
        return memo[n]
    elif n == 0:
        return 1
        x = fact(n-1) * n
        memo[n] = x
        return x
Enter fullscreen mode Exit fullscreen mode

Top comments (0)