Проще говоря, рекурсия - это способ решения проблемы с помощью самого вызова функции. Слово « рекурсивный »Происходит от латинского глагола« повторяться », Что означает что-то переделать. Это то, что делает рекурсивная функция: она повторяет одно и то же снова и снова, то есть отзывается о себе. В этой статье мы узнаем о рекурсии в Python. В этом блоге рассматриваются следующие темы:
- Что такое рекурсия в Python?
- Условия прекращения действия
- Предел рекурсии Python
- Сглаживание списков с помощью рекурсии
- Преимущества рекурсии
- Недостатки рекурсии
Что такое рекурсия в Python?
Рекурсия - это процесс определения чего-либо в терминах самого себя. Мы знаем, что в Python любая функция может вызывать любую другую функцию, функция также может вызывать сама себя. Эти типы функций, которые вызывают сами себя до тех пор, пока не будет выполнено определенное условие, называются рекурсивными функциями.
Давайте рассмотрим несколько примеров, чтобы увидеть, как это работает. Если вам дано положительное целое число n, факториал будет.
- п! = n * (n-1) * (n-2) и так далее.
- 2! = 2 * (2-1)
- один! = 1
- 0! = 0
- 4! = 4 * 3!
- 3! = 3 * 2!
- 2! = 2 * 1!
Замена приведенных выше значений приведет к следующему выражению
- 4! = 4 * 3 * 2 * 1
Мы должны определить функцию, позволяющую сказать fact (n), которая принимает положительное целое число или 0 в качестве параметра и возвращает n-й факториал, как мы можем сделать это с помощью рекурсии?
Давайте посмотрим, чтобы сделать это с помощью рекурсии, нам нужно изучить следующее уравнение
п! = п. (п-1). (п-2) & hellip3.2.1
п! = п. (п-1)! # мы можем переписать приведенный выше оператор как в этой строке
Теперь, если мы передадим 2 в качестве параметра, мы получим:
2! = 2,1! = 2
Аналогично, если мы передадим 1, мы получим:
один! = 1.0! = 1
Но если мы передадим 0, он сломается
0! = 0. (- 1)! и здесь факториал для -1 не определен, поэтому это работает только для значений> 0
Итак, мы должны написать два случая
1. п! = п. (п-1)! если n> = 1
как получить доступ к aws cli
2. 1, если n = 0
Это полное решение для всех положительных целых чисел и 0.
Условия прекращения действия
Рекурсивная функция должна выполнять важное условие для завершения. При переходе к состоянию, при котором проблема может быть решена без дальнейшей рекурсии, рекурсивная функция завершается, сводя проблему к минимуму на более мелкие подэтапы. Рекурсия может закончиться бесконечным циклом, если в вызовах не соблюдается условие завершения.
Факторные условия:
- факториал n = n * (n-1), если n больше 1.
- 1, если n = 0
Мы преобразуем приведенные выше факториальные условия в код Python:
def fact (n): if n == 1: return n else: return n * fact (n-1)
Давайте возьмем пример, допустим, мы хотим найти факториал 4:
fact (4) # это вернет 4 * fact (3) и так далее, пока n == 1.
Вывод: 24
Его так часто используют в качестве примера для рекурсии из-за его простоты и ясности. Решение меньших экземпляров проблемы на каждом этапе в информатике называется рекурсией.
Предел рекурсии Python
В некоторых языках вы можете создать бесконечный рекурсивный цикл, но в Python существует ограничение на рекурсию. Чтобы проверить лимит, запустите следующую функцию из модуля sys. что даст предел набора рекурсии для python.
как сделать словарь на java
импорт sys sys.getrecursionlimit ()
Вывод: 1000
Вы также можете изменить ограничение с помощью функции setrecursionlimit () модуля sys в соответствии с вашими требованиями. Теперь давайте создадим функцию, которая вызывает себя рекурсивно, пока не превысит ограничение, и проверяет, что происходит:
def recursive (): рекурсивный () if __name__ == '__main__': recursive ()
Если вы запустите приведенный выше код, вы получите исключение времени выполнения: RuntimeError: максимальная глубина рекурсии превышена. Python не позволяет вам создавать функцию, которая заканчивается бесконечным рекурсивным циклом.
Сглаживание списков с помощью рекурсии
Другие вещи, которые вы можете сделать с помощью рекурсии, кроме факториалов, скажем, вы хотите создать сингл из списка, который является вложенным, это можно сделать с помощью следующего кода:
def flatten (a_list, flat_list = none): if flat_list is none: flat_list = [] для элемента в a_list: if isinstance (item, list): flatten (item, flat_list) else: flat_list.append (item) вернуть flat_list if __name__ == '__main__': nested = [1,2,3, [4,5], 6] x = плоский (вложенный) print (x)
Вывод: [1,2,3,4,5,6]
Выполнение приведенного выше кода приведет к созданию одного списка вместо целочисленного списка, содержащего целочисленный список, который мы использовали в качестве входных. Вы также можете сделать то же самое и другими способами. В Python есть нечто, называемое itertools.chain (), вы можете проверить код, используемый для создания цепочки функций (), это другой подход, чтобы сделать то же самое, что и мы.
Преимущества рекурсии
В рекурсивной функции код чистый и элегантный.
Сложную задачу можно разбить на более простые подзадачи с помощью рекурсии.
С помощью рекурсии создать последовательность проще, чем с использованием некоторой вложенной итерации.
Недостатки рекурсии
Иногда бывает сложно следовать логике рекурсивной функции.
Рекурсивные вызовы дороги (неэффективны), так как занимают много памяти и времени.
Рекурсивные функции сложно отлаживать.
В этой статье мы увидели, что такое рекурсия и как мы можем разработать рекурсивные функции из постановки задачи, как математически можно определить постановку задачи. Мы решили проблему факториала и выяснили условия, необходимые для нахождения факториалов, из которых мы смогли преобразовать эти условия в код Python, что дало вам понимание того, как работает рекурсия. Я думаю, это здорово, что в Python есть встроенное ограничение для рекурсии, чтобы разработчики не создавали плохо сконструированные рекурсивные функции. Следует отметить одну важную вещь: рекурсию трудно отлаживать, поскольку функция продолжает вызывать сама себя.