Фибоначчи с рекурсией и мемоизацией в Python
В этом уроке вы вычислите числа Фибоначчи рекурсивно и с помощью мемоизации избавитесь от повторного вычисления уже известных результатов.
Введение
Какую задачу это решает
Рекурсивное определение Фибоначчи красиво, но очень медленно: вычисление 40-го члена повторяет одни и те же меньшие вычисления сотни миллионов раз. Мемоизация исправляет это одной строкой и учит ключевой идее динамического программирования.
Пример из жизни
Мемоизация похожа на ученика, который записывает каждый ответ в тетрадь. Когда его снова спрашивают fib(5), он не делает работу заново, а читает ответ из тетради. Каждый вопрос решается только один раз.
@cache📓 Вести тетрадь ответовfibonacci(number - 1) + fibonacci(number - 2)🧮 Решить через два меньших вопросаif number < 2: return number🛑 Первые два ответа известныfibonacci(10)⚡ Каждый меньший ответ вычисляется один раз: быстроМемоизация сохраняет результат каждого вызова функции по её аргументам, так что повторные вызовы возвращают сохранённый результат, а не вычисляют его заново.
Главное
if number < 2: return numberдаёт первые два члена, 0 и 1.fibonacci(number - 1) + fibonacci(number - 2)прямо следует определению.@cacheизfunctoolsзапоминает каждый результат, поэтому каждыйfibonacci(k)выполняется только один раз.- Без
@cachefibonacci(10)сделал бы 177 вызовов; с ним - 11.
Когда это нужно?
- Рекурсивные функции, повторяющие одни и те же подзадачи: пути в сетке, размен монет, разбиение слов.
- Знакомство с идеей динамического программирования.
- Ускорение любой чистой функции, которую часто вызывают с одними и теми же аргументами.
Когда это не нужно
- Функции с побочными эффектами или результатами, меняющимися со временем: кэш вернул бы устаревшие ответы.
- Очень глубокая рекурсия: даже с кэшем
fib(5000)может превысить предел рекурсии; цикл этого избегает.
Как это работает
Нажимайте Шаг, чтобы следить за каждым вызовом. Обратите внимание, как fib снова и снова вычисляет одни и те же маленькие значения - поэтому простая версия медленная.
Пример кода
from functools import cache
@cache
def fibonacci(number):
if number < 2:
return number
return fibonacci(number - 1) + fibonacci(number - 2)
print(fibonacci(10))
Результат выполнения
55
Разбор кода
Декоратор @cache автоматически запоминает результат функции для каждого входного значения. Когда fibonacci(8) уже вычислено, следующие вызовы сразу получают готовый результат. Так время работы сокращается с экспоненциального до O(n) ценой O(n) памяти для хранения результатов.
Измените значения и запустите программу в онлайн-компиляторе Python CodeUtility без локальной установки Python.
Упражнения для практики
Попробуйте изменить код по подсказкам ниже. Если менять код и смотреть на результат, урок запомнится гораздо лучше, чем при простом чтении.
- Проверьте работу на пустом списке, списке из одного элемента и списке с повторами.
- Выводите состояние после каждого шага, чтобы увидеть алгоритм в действии.
- Измерьте время работы на 100, 1 000 и 10 000 элементах и сравните с другим решением.
Частые ошибки
Рекурсия без кэша
Одни и те же значения вычисляются снова и снова, и fib(40) занимает много секунд.
def fibonacci(number):
if number < 2:
return number
return fibonacci(number - 1) + fibonacci(number - 2)
@cache
def fibonacci(number):
if number < 2:
return number
return fibonacci(number - 1) + fibonacci(number - 2)
Закончили этот урок?
Отметьте его как изученный, чтобы следить за прогрессом.
Попрактикуйтесь на задаче
Примените материал этого урока к реальной задаче. Каждая задача запускается в браузере, с мгновенными тестами и разбором от ИИ.
- Число Фибоначчи Верните n-е число Фибоначчи. Легко
- Подсчёт последовательностей бросков кубика Посчитайте количество упорядоченных последовательностей бросков кубика с заданной суммой. Средне