В моей предыдущей статье мы видели восходящий подход или табуляцию для решения проблем. В этой статье мы собираемся выбрать ту же задачу по вычислению n-го числа Фибоначчи ряда Фибоначчи, используя другой метод, называемый подходом сверху вниз.
Подобно тому, как при восходящем подходе мы дошли до сути проблемы и решили подзадачи, прежде чем перейти к решению основной проблемы, нисходящий подход прямо противоположен этому. А если наоборот, то вы говорите, что мы начнем с решения проблемы? Что ж! В этом нет никакого смысла.
Чтобы понять, что это означает, нам нужно подумать о рекурсии. Рекурсивные алгоритмы обладают двумя основными свойствами:
- У них есть базовое состояние
- У них есть рекурсивная логика, которая начинается с окончательного решения и многократно вызывает одну и ту же функцию, пока не найдет решение для базового состояния.
Каково базовое состояние ряда Фибоначчи?
Давайте посмотрим на ряд Фибоначчи, чтобы понять это:
0, 1, 1, 2, 3, 5, 8 ... 0th, 1st, 2nd, 3rd, 4th, 5th, 6th ...
Как мы видим, первые 2 числа последовательности, 0-е и 1-е, имеют значения, равные их номеру позиции в последовательности. Это можно использовать как базовое состояние этого алгоритма:
if n < 2: return n
Теперь рекурсивная логика проста:
fib(n) = fib(n-1) + fib(n-2)
Следовательно, мы можем написать алгоритм, который выглядит так:
def fib(n): if n < 2: return n return fib(n-1) + fib(n-2)
Мемоизация
Как нам это оптимизировать? Вспомните, как мы использовали список в моей предыдущей статье для кэширования значений, чтобы его можно было повторно использовать для будущих вызовов. Но есть небольшая проблема с рекурсивным алгоритмом, как у нас здесь. Как мы сохраняем значения между вызовами функций?
Чтобы решить эту проблему, мы используем другую функцию под названием memoize, которая возвращает другую функцию с кешем, и мы воспользуемся изящным трюком, чтобы использовать эту функцию с рекурсивной логикой.
def memoize(fn): cache = {} # Create an empty cache on memoize's namespace def cached_fib(n): if n in cache: return cache[n] cache[n] = fn(n) return cache[n] return cached_fib def fib(n): if n < 2: return n return fast_fib(n-1) + fast_fib(n-2) # call the fast_fib fast_fib = memoize(fib)
Вот и все! Теперь, когда выполняется fib (n), рекурсивные вызовы в строке 4 перейдут к функции fast_fib (), которая сохраняет результаты предыдущих шагов в кеше. И почему этот кеш работает между вызовами функций? Потому что он находится в пространстве имен memoize () и является атрибутом общих данных для разных вызовов функций fast_fib ().