Мемоизация, рекурсия и цикл for в Python

В этой статье мы подробно разберем, как создать последовательность Фибоначчи. Решение данной задачи мы покажем с использованием трех разных методов. Рассмотрим мемоизацию, рекурсию и цикл for в Python.

Как вы, вероятно, знаете, последовательность Фибоначчи образуется следующим образом. Мы складываем первое и второе число, 0 и 1, чтобы получить третье число в последовательности (0 + 1 = 1). Затем мы складываем второе и третье число, чтобы получить 4-е число в последовательности (1 + 1 = 2). И так проделываем для каждого последующего числа Фибоначчи.

Код, который мы будем рассматривать, вы можете писать в Jupyter, Colab или любой IDE или текстовом редакторе, который вам удобен.

Вычисление n-го члена последовательности Фибоначчи с помощью цикла for

Напишем базовую программу, используя цикл for. Логика последовательности проста, мы уже обсудили ее выше.

Временная сложность решения с помощью цикла for — O(n), а пространственная сложность – O(1) или константа. Правда, на самом деле все несколько сложнее.

«Если ваше число меньше, чем 94, и вы используете 64-битное число, тогда алгоритм ведет себя, как имеющий линейную сложность. Но для N > 94 он начинает вести себя, как алгоритм с квадратичной сложностью», — из ответа Майкла Векслера на сайте Quora.

def fib_for(n):
    n1 = 0
    n2 = 1
    if n <= 0:
        return 'Введите число больше 0'
    elif n == 1:
        return n1
    elif n == 2:
        return n2
    else:
        for i in range(2, n):
            n1, n2 = n2, n1 + n2
        return n2

Запустим этот код с помощью модуля Python %timeit. Это позволит замерить время выполнения, избежав ряда распространенных ловушек.

Для того, чтобы высчитать 10-е число Фибоначчи, потребовалось по 675 наносекунд на каждую итерацию цикла.

Вычисление n-го члена последовательности Фибоначчи с помощью рекурсии

Теперь давайте реализуем последовательность Фибоначчи с помощью рекурсии. Рекурсивные функции вызывают себя повторно, пока не достигнут базового случая. Таким образом, рекурсия создает древовидную структуру.

Если мы возьмем первые 5 чисел Фибоначчи, то в результате рекурсии получится вот такое дерево.

Пространственная сложность в данном случае — O(n), а временная сложность — O(2ⁿ). Так происходит, потому что у корневого узла есть 2 дочерних узла (fib(4) и fib(3)) и 4 внука. И, как видите, у каждого узла есть 2 дочерних элемента. Кроме того, вы могли заметить, что правое поддерево меньше, чем левое. Так что, на самом деле время выполнения составляет примерно O(1,6ⁿ).

Базовый случай: Fibonacci(2) = Fib(1) + Fib(0)  = 1 + 0 = 1

def fib_recursion(n):
    if n <= 0:
        return 'Введите число больше 0'
    elif n == 1:
        return 0
    elif n == 2:
        return 1
    else:
        return fib_recursion(n - 1) + fib_recursion(n - 2)

Вычисление n-го члена последовательности Фибоначчи при помощи рекурсии определенно быстрее, чем с помощью цикла for.

Вычисление n-го члена последовательности Фибоначчи с использованием мемоизации

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

Давайте ещё раз посмотрим на приведенное выше дерево. Легко заметить, что некоторые входные данные пересчитываются при каждом обращении к ним.

def Fib_memoisation(n, memo):
    if n <= 0:
        return 'Введите число больше 0'
    elif n == 1:
        return 0
    elif n == 2:
        return 1
    else:
        if n not in memo:
            memo[n] = Fib_memoisation(n - 1, memo) + Fib_memoisation(n - 2, memo)
        return memo[n]

Временная сложность — O(n * log₁₀n).

Что лучше: рекурсия, цикл for или мемоизация?

Нельзя сказать, что какая-то из этих техник однозначно лучше других. Вам просто нужно знать, в каких случаях какая из них будет наиболее подходящей и эффективной. Это, конечно же, зависит от ваших требований.

Итерация с помощью цикла for будет быстрее, чем рекурсия, потому что рекурсия должна иметь дело с фреймом рекурсивного стека вызовов. Однако, если рекурсия написана на языке, который оптимизирует «хвостовой» вызов, это устраняет излишние расходы, и тогда рекурсия сравнима с циклом for.

Наконец, мемоизация лучше, когда нужно иметь дело только с некоторыми более мелкими подзадачами, а не решать их все.

Таким образом, каждый из разобранных нами в этой статье методов по-своему хорош. Стоит помнить о существовании и особенностях каждого из них и выбирать наиболее оптимальный под вашу задачу.