Кратко — проблема в том, что аргумент по умолчанию `memo={}` мутируемый и живёт в области определения функции между вызовами. Это даёт побочные эффекты, рост памяти и неожиданные семантические последствия.
Пояснения:
- По сути `memo` сохраняется между вызовами и накапливает все рассчитанные значения: если вы вызовете `fib(k)` для многих разных `k`, словарь будет расти — утечка памяти в долгоживущем приложении.
- Семантика: функция перестаёт быть «чистой» (не иметь побочных эффектов). Повторный вызов `fib(n)` может опираться на результаты предыдущих вызовов; это может быть неожиданным или неверным в некоторых сценариях.
- Потенциальные проблемы в многопоточности: общий `memo` разделяется между потоками, возможны гонки при одновременных записях.
Как это влияет: память будет увеличиваться по мере уникальных сохранённых ключей; поведение функции становится зависимым от истории вызовов и контекста.
Правильные варианты исправления (корректно и безопасно):
1) Инициализировать внутри функции при `None`:
def fib(n, memo=None):
if memo is None:
memo = {}
if n in memo: return memo[n]
if n < 2: return n
memo[n] = fib(n-1, memo) + fib(n-2, memo)
return memo[n]
(Здесь базовый случай — $n<2$, а `memo` не разделяется между независимыми вызовами.)
2) Использовать кеширование стандартной библиотеки:
from functools import lru_cache
@lru_cache(maxsize=None) # или задать maxsize для ограничения роста
def fib(n):
if n < 2: return n
return fib(n-1) + fib(n-2)
(Плюс: готовая реализация с опцией ограниченного кэша через `maxsize`, потокобезопасна.)
3) Итеративный вариант без рекурсивного мемо: экономит память и быстрее:
def fib(n):
a, b = 0, 1
for _ in range(n):
a, b = b, a + b
return a
(Этот код даёт те же значения для $n=0,1,2,\dots$ и не хранит историю.)
Дополнительно: если нужен кэш, но с ограничением по памяти — используйте `lru_cache(maxsize=...)` или собственную структуру с очисткой/ограничением; для объектов больших размеров можно рассмотреть `weakref.WeakValueDictionary`, но для чисел это редко нужно.
Вывод: не используйте мутируемые объекты как значения аргументов по умолчанию; предпочитайте `None` + инициализация внутри функции или стандартные механизмы кеширования.