Ответ.

История вопроса:

Мемоизация — это оптимизационная техника, широко применяемая в функциональном программировании, рекурсивных вычислениях и динамическом программировании, когда одни и те же функции вызываются с одинаковыми аргументами многократно. В Python она вошла в обиход с появлением декоратора functools.lru_cache и паттернов кэширования результатов вычислений.

Проблема:

Без кэширования рекурсивные функции типа вычисления чисел Фибоначчи работают очень медленно: для каждого аргумента вычисления повторяются много раз, что приводит к экспоненциальному росту количества вызовов.

Решение:

Мемоизация сохраняет уже вычисленные значения (например, в словаре), чтобы повторно использовать их при необходимости:

Пример ручной реализации:

memo = {}
def fib(n):
    if n in memo:
        return memo[n]
    if n <= 1:
        result = n
    else:
        result = fib(n-1) + fib(n-2)
    memo[n] = result
    return result

С Python 3.2 можно просто использовать декоратор:

from functools import lru_cache

@lru_cache(maxsize=128)
def fib(n):
    if n <= 1:
        return n
    return fib(n-1) + fib(n-2)

Ключевые особенности:

Позволяет ускорить рекурсивные или вычислительно затратные функции без изменения их логики
Реализация бывает ручная (на словаре) и автоматическая (через lru_cache)
Нужно быть осторожным с изменяемыми аргументами, так как lru_cache работает только с хешируемыми (immutable) аргументами

Вопросы с подвохом.

Можно ли мемоизировать функцию с изменяемыми аргументами (например, списками)?

Нет, lru_cache требует все аргументы хешируемыми (immutable), иначе будет TypeError.

from functools import lru_cache

@lru_cache
# def f(a): return a[0]  # TypeError: unhashable type: 'list'

Удаляются ли мемоизированные значения автоматически?

Да, если установлен maxsize — значения, вышедшие за лимит, удаляются (Least Recently Used). Бесконечный кэш (maxsize=None) может привести к переполнению памяти.

Что будет, если мемоизированная функция вызывает саму себя с новыми аргументами?

Мемоизация всё равно сработает — для каждого уникального набора аргументов результат вычисляется только раз и кэшируется.

Типовые ошибки и анти-паттерны

Использовать memoization без ограничения кэша и переполнить память
Пытаться мемоизировать функции с изменяемыми аргументами
Забывать про очистку кэша, когда он больше не нужен

Пример из жизни

Негативный кейс

Пишут собственный кэш без ограничения размера:

cache = {}
def foo(x):
    if x not in cache:
        cache[x] = long_heavy_computation(x)
    return cache[x]

через время программа использует гигабайты памяти.

Плюсы:

Быстро работает для повторяющихся вызовов

Минусы:

Неограниченный рост памяти
Возможен Out of Memory

Позитивный кейс

Использование lru_cache с maxsize:

from functools import lru_cache

@lru_cache(maxsize=1000)
def foo(x):
    return long_heavy_computation(x)