170. Function Memoization

Snippet 1: Basic Function Memoization Using a Dictionary

Copy

def fibonacci(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 2:
        return 1
    memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo)
    return memo[n]

print(fibonacci(10))  # Output: 55

---

Snippet 2: Memoization with functools.lru_cache

Copy

from functools import lru_cache

@lru_cache(maxsize=None)
def factorial(n):
    return n * factorial(n - 1) if n > 1 else 1

print(factorial(10))  # Output: 3628800

---

Snippet 3: Custom Memoization Decorator

Copy

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 add(a, b):
    return a + b

print(add(3, 4))  # Output: 7

---

Snippet 4: Memoization for a Computationally Expensive Function

Copy

def expensive_function(x, memo={}):
    if x in memo:
        return memo[x]
    result = sum(i ** 2 for i in range(x))
    memo[x] = result
    return result

print(expensive_function(1000))  # Cached for future calls

---

Snippet 5: Recursive Memoization for Combinatorics

Copy

def nCr(n, r, memo={}):
    if r == 0 or n == r:
        return 1
    if (n, r) in memo:
        return memo[(n, r)]
    memo[(n, r)] = nCr(n - 1, r - 1, memo) + nCr(n - 1, r, memo)
    return memo[(n, r)]

print(nCr(5, 2))  # Output: 10

---

Snippet 6: Memoization with Immutable Default Arguments

Copy

def power(base, exp, memo=None):
    if memo is None:
        memo = {}
    if (base, exp) in memo:
        return memo[(base, exp)]
    if exp == 0:
        return 1
    memo[(base, exp)] = base * power(base, exp - 1, memo)
    return memo[(base, exp)]

print(power(2, 10))  # Output: 1024

---

Snippet 7: Using functools.cache for Memoization (Python 3.9+)

Copy

from functools import cache

@cache
def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

print(gcd(48, 18))  # Output: 6

---

Snippet 8: Memoization for String Processing

Copy

def is_palindrome(s, memo={}):
    if s in memo:
        return memo[s]
    memo[s] = s == s[::-1]
    return memo[s]

print(is_palindrome("racecar"))  # Output: True
print(is_palindrome("python"))  # Output: False

---

Snippet 9: Memoization for Pathfinding Problems

Copy

def unique_paths(m, n, memo={}):
    if (m, n) in memo:
        return memo[(m, n)]
    if m == 1 or n == 1:
        return 1
    memo[(m, n)] = unique_paths(m - 1, n, memo) + unique_paths(m, n - 1, memo)
    return memo[(m, n)]

print(unique_paths(3, 3))  # Output: 6

---

Snippet 10: Caching Results of an API Call Simulation

Copy

import time

def simulate_api_call(endpoint, memo={}):
    if endpoint in memo:
        return memo[endpoint]
    time.sleep(2)  # Simulate API delay
    result = f"Data from {endpoint}"
    memo[endpoint] = result
    return result

print(simulate_api_call("/users"))  # Takes time
print(simulate_api_call("/users"))  # Instant result from cache

---