В моей предыдущей статье мы видели восходящий подход или табуляцию для решения проблем. В этой статье мы собираемся выбрать ту же задачу по вычислению 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 ().