Skip to main content
Practice

Enhancing Recursive Function Efficiency with Memoization

Recursive functions are functions that call themselves, and they can suffer from performance issues due to repetitive calculations.

To address this problem, the memoization technique is employed.


What is Memoization?​

Memoization is a technique that stores the return values of a function so that when the function is called again with the same input, it can return the stored value instead.

Memoization stores function return values to avoid redundant calculations, thereby improving execution speed.

Fibonacci sequence example using memoization
def fibonacci(n):
    # Create an empty dictionary for memoization
    memo = {}

    def helper(x):
        # Return stored value if it has already been calculated
        if x in memo:
            return memo[x]
        # Base case: return x for 0 or 1
        if x <= 1:
            return x
        # Store the calculation result in the memoization dictionary
        memo[x] = helper(x - 1) + helper(x - 2)
        return memo[x]

    # Call the recursive function
    return helper(n)

# Print the 10th Fibonacci number
print(fibonacci(10))
# 55

In the code above, the memo dictionary is used to store previously calculated values, and if a value has already been calculated, the stored value is returned.

The values stored in the dictionary represent the results of the Fibonacci sequence for the given n.

memo dictionary
{
    2: 1,
    3: 2,
    4: 3,
    5: 5,
    6: 8,
    7: 13,
    8: 21,
    9: 34,
    10: 55
}

Using memoization can significantly improve the execution speed of a function by avoiding redundant calculations, thus enhancing performance.

However, since additional memory is required to store the calculation results, attention must be paid to memory usage when employing memoization.

Want to learn more?

Join CodeFriends Plus membership or enroll in a course to start your journey.