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.

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.

Using memoization allows you to store function return values to avoid redundant calculations, thereby improving the function's 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 above code, 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, attention must be paid to memory usage when employing memoization.