Без кэша функция пересчитывает одно и то же много раз: f(5, 7) нужна и для f(4, 7), и для f(3, 7).
Кэш — это словарь готовых ответов. Ключ — аргументы функции, значение — посчитанный ответ.
Перед расчётом смотрим в словарь. После расчёта записываем ответ: memo[x] = ways.
memo[x] = ways
Ошибка RecursionError. Кэш не делает цепочку вызовов короче. Помогает sys.setrecursionlimit(10000). Если программа всё равно падает, переходи на цикл из прошлой тетради.
sys.setrecursionlimit(10000)
Тот же подсчёт 2 → 7 со своим словарём. Запусти и посмотри, что запомнилось.
Вывод программы:
8 {6: 1, 5: 2, 4: 3, 3: 5, 2: 8}
Программа вывела словарь memo. Что означает запись 4: 3?
memo
4: 3