Enhancing Recursive Function Efficiency with Memoization

Recursive functions call themselves and may suffer from performance issues due to repeated calculations.

To address this problem, the memoization technique is employed.

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.

It avoids redundant calculations by caching function results, thereby improving execution speed.

Copy
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.

Copy
{
    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, It's important to consider memory usage when applying memoization.