Алгоритмы на Python

Фибоначчи с рекурсией и мемоизацией в Python

В этом уроке вы вычислите числа Фибоначчи рекурсивно и с помощью мемоизации избавитесь от повторного вычисления уже известных результатов.

  • Средний
  • Чтение: 2 мин
  • Примеров для запуска: 1

Введение

Какую задачу это решает

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

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

Мемоизация похожа на ученика, который записывает каждый ответ в тетрадь. Когда его снова спрашивают fib(5), он не делает работу заново, а читает ответ из тетради. Каждый вопрос решается только один раз.

От тетради к коду
@cache📓 Вести тетрадь ответов
fibonacci(number - 1) + fibonacci(number - 2)🧮 Решить через два меньших вопроса
if number < 2: return number🛑 Первые два ответа известны
fibonacci(10)⚡ Каждый меньший ответ вычисляется один раз: быстро
Сохраняйте каждый результат в первый раз; потом используйте его снова.
Одним предложением

Мемоизация сохраняет результат каждого вызова функции по её аргументам, так что повторные вызовы возвращают сохранённый результат, а не вычисляют его заново.

Главное

  1. if number < 2: return number даёт первые два члена, 0 и 1.
  2. fibonacci(number - 1) + fibonacci(number - 2) прямо следует определению.
  3. @cache из functools запоминает каждый результат, поэтому каждый fibonacci(k) выполняется только один раз.
  4. Без @cache fibonacci(10) сделал бы 177 вызовов; с ним - 11.

Когда это нужно?

  • Рекурсивные функции, повторяющие одни и те же подзадачи: пути в сетке, размен монет, разбиение слов.
  • Знакомство с идеей динамического программирования.
  • Ускорение любой чистой функции, которую часто вызывают с одними и теми же аргументами.

Когда это не нужно

  • Функции с побочными эффектами или результатами, меняющимися со временем: кэш вернул бы устаревшие ответы.
  • Очень глубокая рекурсия: даже с кэшем fib(5000) может превысить предел рекурсии; цикл этого избегает.

Как это работает

Нажимайте Шаг, чтобы следить за каждым вызовом. Обратите внимание, как fib снова и снова вычисляет одни и те же маленькие значения - поэтому простая версия медленная.

Пример кода

Запустить код →
main.py
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.

Упражнения для практики

Попробуйте изменить код по подсказкам ниже. Если менять код и смотреть на результат, урок запомнится гораздо лучше, чем при простом чтении.

  1. Проверьте работу на пустом списке, списке из одного элемента и списке с повторами.
  2. Выводите состояние после каждого шага, чтобы увидеть алгоритм в действии.
  3. Измерьте время работы на 100, 1 000 и 10 000 элементах и сравните с другим решением.
Запустить в компиляторе Python →

Частые ошибки

Рекурсия без кэша

Одни и те же значения вычисляются снова и снова, и 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)

Закончили этот урок?

Отметьте его как изученный, чтобы следить за прогрессом.

Попрактикуйтесь на задаче

Примените материал этого урока к реальной задаче. Каждая задача запускается в браузере, с мгновенными тестами и разбором от ИИ.

Все задачи