Recursion with Memoization

Memoization is an optimization technique that stores the results of expensive function calls and returns the cached result when the same inputs occur again. Here’s an example demonstrating how to implement memoization in Python using a decorator to optimize a recursive Fibonacci function.

Memoization Example

# Memoization decorator
def memoize(func):
    cache = {}
    def wrapper(*args):
        if args in cache:
            return cache[args]
        result = func(*args)
        cache[args] = result
        return result
    return wrapper

@memoize
def fibonacci_memoized(n):
    """Recursively calculate the nth Fibonacci number with memoization."""
    if n <= 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibonacci_memoized(n - 1) + fibonacci_memoized(n - 2)

# Test the memoized Fibonacci function
print(f"Fibonacci of 10 with memoization: {fibonacci_memoized(10)}")

Explanation

1. memoize Decorator:
   • The memoize function is a decorator that takes a function func as an argument and returns a wrapper function.
   • The wrapper function maintains a cache (dictionary) to store the results of previous function calls.
   • When wrapper is called, it first checks if the result for the given arguments is already in the cache.
   • If the result is cached, it returns the cached result.
   • If not, it calls the original function func, stores the result in the cache, and then returns the result.
2. fibonacci_memoized Function:
   • This function calculates the nth Fibonacci number recursively.
   • It is decorated with the @memoize decorator, which optimizes the function by caching its results.
   • The base cases handle n less than or equal to 0 (returning 0) and n equal to 1 (returning 1).
   • For other values of n, it returns the sum of the Fibonacci numbers of n-1 and n-2.
3. Testing the Function:
   • The Fibonacci function is tested with the input 10.
   • The output demonstrates the efficiency gained by memoization, as repeated calculations are avoided.

Output

When you run the above code, you will get the following output:

Fibonacci of 10 with memoization: 55