Понимание рекурсии и мемоизации в программировании на Python

Подробное руководство по рекурсии и запоминанию в программировании на Python.

Что такое рекурсия в программировании на Python?

Термин «рекурсия» в программировании на Python может быть определен как процесс определения проблемы с точки зрения самой себя или, выражаясь простыми словами, процесс, при котором функция прямо или косвенно вызывает сама себя. Это простой процесс разбиения проблемы на составные части и обращения к себе для решения подзадач и создания последовательности для поиска решения основной проблемы. Рекурсивные алгоритмы используют сортировку по списку, обход бинарного дерева, поиск пути и т. д. Рекурсия помогает сделать код простым и эффективным. Недостатки рекурсии включают в себя: дорогой процесс из-за чрезмерного использования памяти и времени, сложность отладки и, наконец, обоснование рекурсии может усложниться.

Что такое мемоизация в программировании на Python?

Мемоизацию в программировании на Python можно описать как метод оптимизации, используемый в первую очередь для ускорения компьютерного программирования путем сохранения промежуточных результатов, чтобы его можно было использовать, чтобы избежать повторных вычислений и ускорить программы. Технику запоминания можно использовать при использовании рекурсивных операторов. Мемоизацию в программировании на Python можно использовать либо путем создания словаря для хранения значений, либо путем импорта lru_cache из модуля functools и указания максимального размера, который в основном сохраняет последнее значение в кеше, который можно использовать повторно.

Чтобы понять обе концепции, мы рассмотрим два вопроса — вопрос о факториале и вопрос о Фибоначчи, а также рассмотрим разные пути к одному и тому же решению.

1. Факториал. Факториал любого заданного числа — это произведение самого числа на все числа, меньшие его, но большие 1. Предположим, мы пытаемся найти факториал 6: 6! = 6x5x4x3x2x1 = 720.

Когда вы запустите этот код, вы можете заметить, что компьютер замедляется при завершении вывода факториала до 999, и это может занять около 20–40 секунд. Вот почему нам нужен лучший способ, потому что здесь, в случае рекурсии, когда компьютер находит факториал 999, он пересчитывает факториал 998 и так далее. Таким образом, для экономии времени мы используем мемоизацию, в которой ранее рассчитанные числа сохраняются и могут быть повторно использованы, что повышает эффективность обработки.

2. Фибоначчи. Некоторые утверждают, что последовательность Фибоначчи начинается с 1, а другие говорят, что она начинается с 0, но мы избегаем этого обсуждения и, например, предположим, что она начинается с 1. Первые несколько чисел последовательности Фибоначчи это — 1,1,2,3,5,8,13,21 и т. д.. По сути, первое и второе число складываются, образуя третье число, а второе и третье числа создают четвертое число и продолжают ту же цепочку.