Последнее обновление 20/03/2021
Рекурсия
В информатике рекурсия — это метод поиска решений проблем с использованием меньших решений той же проблемы. Рекурсивные алгоритмы находят применение в сортировке списков, обходе двоичного дерева, поиске путей и многом другом. В этом уроке мы обсудим классическую рекурсивную процедуру, используемую для нахождения факториала натурального числа.
Поскольку мы будем писать алгоритм для поиска факториалов, стоит пересмотреть определение факториала. Факториал натурального числа n — это произведение всех натуральных чисел, меньших или равных n:
n! = n\times(n-1)\times(n-2)\times(n-3)\times \ldots \times 3\times2\times1
Например, если n = 6:
6! = 6 \times 5 \times 4 \times 3 \times 2 \times 1 = 720
Подумаем об этом рекурсивно. Если у нас есть рекурсивная функция f, мы хотели бы использовать f для вычисления 6! следующим образом:
6! = f(6)
f(6)= 6\times f(5)
f(5) = 5\times f(4)\ или\ f(6) = 6\times5\times f(4)
f(4) = 4\times f(3)\ или\ f(6) = 6\times5\times4\times f(3)
f(3) = 3\times f(2)\ или\ f(6) = 6\times5\times4\times3\times f(2)
f(2) = 2\times f(1)\ или\ f(6) = 6\times5\times4\times3\times2\times f(1)
f(1) = 1\ или\ f(6) = 6\times5\times4\times3\times2\times1.
Чтобы реализовать это в python, нам нужно определить функцию, назовём её recursive_factorial, которая на вход принимает аргумент n и возвращает n * recursive_factorial(n-1). Более того, мы хотим, чтобы функция продолжала выполняться до тех пор, пока вход не стал равен единице. В этот момент мы возвращаем 1, и рекурсия прекращается. Делаем следующее:
def recursive_factorial(n):
if n == 1:
return 1
else:
return n*recursive_factorial(n-1)
Кроме того, необходимо обработать случай, когда n = 0, учитывая, что 0! = 1.
Соответствующим образом изменим оператор if:
def recursive_factorial(n):
if n <= 1:
return 1
else:
return n*recursive_factorial(n-1)
Еще стоит отметить, что наша функция не обрабатывает отрицательные числа. Этот метод работает только для натуральных чисел и нуля.
Посмотрим, что делает эта функция для 4!:
Нам нужно вычислить recursive_factorial (4).
Функция спрашивает, n = 1? Нет, n = 4, поэтому давайте вернем 4 * recursive_factorial (4-1), что равно 4 * recursive_factorial (3).Теперь нам нужно вычислить recursive_factorial (3).
N = 1? Нет, n = 3, поэтому давайте вернем 4 * 3 * recursive_factorial (3-1), что равно 4 * 3 * recursive_factorial (2).Теперь нам нужно вычислить recursive_factorial (2).
N = 1? Нет, n = 2, поэтому давайте вернем 4 * 3 * 2recursive_factorial (2-1), что равно 4 * 3 * 2recursive_factorial (1).
Теперь нам нужно вычислить recursive_factorial (1).
N = 1? да, n = 1, поэтому вернем 4 * 3 * 2 * 1.
Случаи, когда n > 1, называются рекурсивными случаями, а когда n <= 1, завершением рекурсии.
Исходя из этой логики, recursive_factorial(4) = 4 * 3 * 2 * 1 = 24. Проверим это:
def recursive_factorial(n):
if n <= 1:
return 1
else:
return n*recursive_factorial(n-1)
print("4! =", recursive_factorial(4))
4! = 24
Попробуем предыдущий пример, 6!:
print("6! =", recursive_factorial(4))
6! = 720
Я остановлюсь на этом, но не стесняйтесь поиграть с кодом.
Подводя итог, можно отметить, что в этом уроке мы обсудили, как написать рекурсивный алгоритм для нахождения факториала натурального числа.
К другим классическим приложениям рекурсивных алгоритмов относятся головоломка Ханойская башняએ и проблема N-й ступени лестницы. Надеюсь, вы нашли этот урок полезным/интересным. Код можно скопировать прямо отсюда в IDLE для собственных развлечений.
Мемоизация
Мемоизация — это термин, введенный Дональдом Мичи в 1968 году, который происходит от латинского слова «меморандум» (запомнить). Мемоизация — это метод, используемый в информатике для ускорения вычислений за счет сохранения (запоминания) предыдущих вычислений. Если повторные вызовы функций выполняются с одинаковыми параметрами, можно сохранить уже вычисленные значения вместо того, чтобы повторять их ещё раз. В этом уроке мы будем использовать мемоизацию, чтобы найти числа Фибоначчи.
Во-первых, давайте определим рекурсивную функцию, которую мы можем использовать для отображения первых n чисел в последовательности Фибоначчи. Если вы не знакомы с рекурсией, посмотрите урок: Рекурсия в Python.
Напоминаем, что последовательность Фибоначчи определяется так, что каждое число является суммой двух предыдущих чисел. Например, первые 6 членов последовательности Фибоначчи — это
1, 1, 2, 3, 5, 8.
Рекурсивную функцию мы можем определить следующим образом.
def fibonacci(input_value):
if input_value == 1:
return 1
elif input_value == 2:
return 1
elif input_value > 2:
return fibonacci(input_value -1) + fibonacci(input_value -2)
Здесь мы описываем начало последовательности — если входное значение равно 1 или 2, то функция возвращает 1. Если входное значение больше 2, возвращаются результаты рекурсивных вызовов функции, суммирующие предыдущие два числа Фибоначчи.
Теперь напечатаем первые 10 чисел:
for i in range(1, 11):
print("fib({}) = ".format(i), fibonacci(i))
====================== RESTART: D:\PHYTON\fibonatc\1.py ====================== fib(1) = 1 fib(2) = 1 fib(3) = 2 fib(4) = 3 fib(5) = 5 fib(6) = 8 fib(7) = 13 fib(8) = 21 fib(9) = 34 fib(10) = 55
Кажется, все работает нормально. Теперь давайте попробуем отобразить первые 200 чисел последовательности:
for i in range(1, 201):
print("fib({}) = ".format(i), fibonacci(i))
====================== RESTART: D:\PHYTON\fibonatc\1.py ====================== ... fib(20) = 6765 fib(21) = 10946 fib(22) = 17711 fib(23) = 28657 fib(24) = 46368 fib(25) = 75025 fib(26) = 121393 fib(27) = 196418 fib(28) = 317811 fib(29) = 514229 fib(30) = 832040 fib(31) = 1346269 fib(32) = 2178309 fib(33) = 3524578 fib(34) = 5702887 fib(35) = 9227465 fib(36) = 14930352 fib(37) = 24157817 fib(38) = 39088169
Заметили? — После fib(20) последующие вычисления занимают значительно больше времени, чем предыдущие. Это потому, что с каждым последующим вычислением мы повторяем одну и ту же работу.
Рассмотрим, как рекурсивная функция вычисляет каждое число:
fib(1) = 1
fib(2) = 1
fib(3) = fib(1)+fib(2) = 2
fib(4) = fib(3)+fib(2) = fib(5) = fib(4)+fib(3) = 5
Обратите внимание, что для fib(5) мы повторяем вычисление fib(4) и fib(3). Если бы у нас был способ запоминать/сохранять эти значения после их вычисления, то мы бы избежали повторений. Это создаёт мотивацию для метода мемоизации.
Теперь давайте пройдемся по этапам реализации метода мемоизации. Для продолжения давайте инициализируем словарь:
fibonacci_cache = {}
Далее определим нашу функцию мемоизации. Сначала проверяем, существует ли в словаре номер числа в последовательности, который будет ключом словаря. Если ключ присутствует, то возвращаем число, соответствующее номеру/ключу:
def fibonacci_memo(input_value):
if input_value in fibonacci_cache:
return fibonacci_cache[input_value]
Затем определяем два начальных числа последовательности. Если входное значение (фактический аргумент функции input_value) равно 1 или 2, то устанавливаем значение 1:
def fibonacci_memo(input_value):
...
if input_value == 1:
value = 1
elif input_value == 2:
value = 1
Далее рассмотрим рекурсивные случаи. Если аргумент больше 2, мы устанавливаем значение, равное сумме двух предыдущих чисел:
def fibonacci_memo(input_value):
...
elif input_value > 2:
value = fibonacci_memo(input_value -1) + fibonacci_memo(input_value -2)
В конце сохраняем значение в нашем словаре и возвращаем значение:
def fibonacci_memo(input_value):
...
fibonacci_cache[input_value] = value
return value
Полностью функция выглядит так:
def fibonacci_memo(input_value):
if input_value in fibonacci_cache:
return fibonacci_cache[input_value]
if input_value == 1:
value = 1
elif input_value == 2:
value = 1
elif input_value > 2:
value = fibonacci_memo(input_value -1) + fibonacci_memo(input_value -2)
fibonacci_cache[input_value] = value
return value
Теперь давайте попробуем получить первые 200 чисел Фибоначчи с помощью нашей новой функции:
for i in range(1, 201):
print("fib({}) = ".format(i), fibonacci_memo(i))
Python 3.6.8 (tags/v3.6.8:3c6b436a57, Dec 24 2018, 00:16:47) [MSC v.1916 64 bit (AMD64)] on win32 Type "help", "copyright", "credits" or "license()" for more information. >>> ====================== RESTART: D:\PHYTON\fibonatc\2.py ====================== ... fib(184) = 127127879743834334146972278486287885163 fib(185) = 205697230343233228174223751303346572685 fib(186) = 332825110087067562321196029789634457848 fib(187) = 538522340430300790495419781092981030533 fib(188) = 871347450517368352816615810882615488381 fib(189) = 1409869790947669143312035591975596518914 fib(190) = 2281217241465037496128651402858212007295 fib(191) = 3691087032412706639440686994833808526209 fib(192) = 5972304273877744135569338397692020533504 fib(193) = 9663391306290450775010025392525829059713 fib(194) = 15635695580168194910579363790217849593217 fib(195) = 25299086886458645685589389182743678652930 fib(196) = 40934782466626840596168752972961528246147 fib(197) = 66233869353085486281758142155705206899077 fib(198) = 107168651819712326877926895128666735145224 fib(199) = 173402521172797813159685037284371942044301 fib(200) = 280571172992510140037611932413038677189525 >>>
Запустили наш скрипт, заметили? — довольно быстро мы пришли к 200‑му числу последовательности.
Есть более простой способ реализовать мемоизацию и сократить код. Рассмотрим нашу исходную рекурсивную функцию:
def fibonacci(input_value):
if input_value == 1:
return 1
elif input_value == 2:
return 1
elif input_value > 2:
return fibonacci(input_value -1) + fibonacci(input_value -2)
Из модуля functools можно импортировать декоратор, называемый lru_cache, который позволяет кэшировать наши значения. Название означает «кэш последнего использования». Используя декоратор можно достичь той же производительности, что и наш метод fibonacci_memo:
from functools import lru_cache
@lru_cache(maxsize = 1000)
def fibonacci(input_value):
if input_value == 1:
return 1
elif input_value == 2:
return 1
elif input_value > 2:
return fibonacci(input_value -1) + fibonacci(input_value -2)
for i in range(1, 201):
print("fib({}) = ".format(i), fibonacci(i))
Python 3.6.8 (tags/v3.6.8:3c6b436a57, Dec 24 2018, 00:16:47) [MSC v.1916 64 bit (AMD64)] on win32 Type "help", "copyright", "credits" or "license()" for more information. >>> ====================== RESTART: D:\PHYTON\fibonatc\3.py ====================== ... fib(184) = 127127879743834334146972278486287885163 fib(185) = 205697230343233228174223751303346572685 fib(186) = 332825110087067562321196029789634457848 fib(187) = 538522340430300790495419781092981030533 fib(188) = 871347450517368352816615810882615488381 fib(189) = 1409869790947669143312035591975596518914 fib(190) = 2281217241465037496128651402858212007295 fib(191) = 3691087032412706639440686994833808526209 fib(192) = 5972304273877744135569338397692020533504 fib(193) = 9663391306290450775010025392525829059713 fib(194) = 15635695580168194910579363790217849593217 fib(195) = 25299086886458645685589389182743678652930 fib(196) = 40934782466626840596168752972961528246147 fib(197) = 66233869353085486281758142155705206899077 fib(198) = 107168651819712326877926895128666735145224 fib(199) = 173402521172797813159685037284371942044301 fib(200) = 280571172992510140037611932413038677189525 >>>
Заметили? — показатели аналогичны. И на этом я остановлюсь, однако, призываю вас поиграть с кодом самостоятельно.
Заключение
Подводя итог уроку, можно сказать, что мы обсудили метод мемоизации в Python. Во-первых, показано, как наивная реализация рекурсивной функции становится причиной очень медленных вычисления большого количества чисел последовательности Фибоначчи.
Затем мы определили новый метод, в котором мы сохраняем предыдущие уже вычисленные значения в словаре, что приводит к значительному ускорению вычислений.
Далее мы обсудили декоратор lru_cache, который показал производительность, аналогичную нашему методу fibonacci_memo, но с меньшим количеством операторов кода.
Надеюсь, вы нашли этот урок полезным и интересным. Код этого урока доступен на GitHub. Спасибо за внимание!
Ваш комментарий будет первым