Рекурсия в Python
В программировании рекурсия является фундаментальным понятием. В большинстве собеседований по Python могут задать вопрос на эту тему. Независимо от того, являетесь ли вы программистом или специалистом по обработке данных, эту концепцию должен знать каждый. Рекурсивны не только алгоритмы поиска и сортировки, но и каждое собеседование по Python будет включать некоторые вопросы, основанные на рекурсии. Это делает рекурсию ключевой концепцией, которую нужно пересматривать перед любым собеседованием по программированию.
Здесь я попытаюсь объяснить рекурсию максимально простым способом, разделив рекурсию на шаги:
- Что такое рекурсия?
- Почему мы используем рекурсию?
- Рекурсия в Python.
- Примеры рекурсии.
Что такое рекурсия?
Рекурсия - это математическая концепция, которую мы также используем в программировании. Рекурсия - это процесс определения проблемы в терминах самой себя. Это простейшее определение рекурсии.
В программировании рекурсия - это процесс, в котором функция вызывает себя прямо или косвенно, а соответствующая функция вызывается как рекурсивная функция.
Итак, вывод заключается в том, что рекурсия определяет новую, используя саму себя.
Почему мы используем рекурсию?
Большинство проблем решаются без рекурсии. Так что, строго говоря, в рекурсии обычно нет необходимости. Рекурсия предназначена для решения проблем, которые можно разбить на более мелкие повторяющиеся проблемы. Она особенно хороша для работы с вещами, которые имеют много возможных ветвей и слишком сложны для итеративного подхода.
Плюсы:
- Быстрее при оптимизации.
- Меньше кода. Вы можете писать рекурсивный код быстрее, а для отладки у вас меньше кода для сравнения, чем итеративный код.
- Декларативная.
- Эффективная сортировка и поиск
Минусы:
- Максимальная глубина рекурсии.
- По ошибке или непреднамеренно использовать рекурсию без базового условия.
- Больше потребления памяти.
Рекурсия в Python
Когда вы вызываете функцию в Python, интерпретатор создает новое локальное пространство имен, чтобы имена, определенные в этой функции, не конфликтовали с идентичными именами, определенными в другом месте.
def recurse():
x = 5
recurse()
Когда функция recurse() выполняется в первый раз, она создаст локальное пространство имен в python, а переменной x присваивается 10. После этого рекурсия () вызывает себя рекурсивно. При повторном выполнении рекурсии () интерпретатор создает второе пространство имен и также назначает переменной x значние 10. Эти два экземпляра имени x отличаются друг от друга и могут сосуществовать без конфликтов, поскольку они находятся в разных пространствах имен.
После выполнения рекурсии () она будет вызывать себя снова и снова, но python будет отображать трассировку, потому что невозможно запускать ее вечно.
RecursionError: maximum recursion depth exceededПотому что существует ограничение на рекурсию в соответствии с вашей системой.
Теоретически она будет работать вечно, но практически ничто не может быть вечным из-за ограничений памяти. Python не позволяет этому случиться. Интерпретатор ограничивает максимальное количество раз, которое функция может вызывать саму себя рекурсивно, и при достижении этого предела вызывает исключение RecursionError.
Итак, чтобы наша функция не запускалась навсегда, должно быть базовое условие.
Базовый вариант.
Базовое условие поможет завершить процесс рекурсии или остановить функцию, вызывая себя снова и снова. Есть один или несколько базовых случаев, которые решаются напрямую без необходимости дальнейшей рекурсии.
Рекурсивный случай.
Если желаемое состояние не было достигнуто, и функция переходит на другой рекурсивный шаг. Каждый рекурсивный вызов постепенно приближает решение к базовому случаю.
Примеры рекурсии
Обратный отсчет до нуля
def countdown(n):
print(n)
if n==0:
return # Base condition. it will return None.
else:
return countdown(n-1) # Recursive call
countdown(int(input('Enter number')))В приведенном выше примере пользователю будет предложено ввести номер. В базовом случае n = 0 и на этом рекурсия остановится. В рекурсивном случае в качестве аргумента n передается значение на единицу меньше, чем текущее значение, и, как и в этом случае, рекурсия приближается к базовому случаю.
Рассчет факториала
В следующем примере используется математическая концепция факториала. Факториал натурального числа n, обозначаемый как n! и рассчитывается как:
n! = n*(n-1)*(n-2)...3*2*1
Другими словами, n! является произведением всех целых чисел от 1 до n включительно.
def factorial(n):
if n<=1:
return 1 # Base condition
esle:
return n*factorial(n-1)
factorial(int(input('Enter number to get factorial ')))Примеров рекурсии может быть так много, но возникает вопрос: "Действительно ли это необходимо для реализации рекурсии?". Потому что эти два вышеперечисленных кода также можно записать с помощью цикла for. Второе - это скорость выполнения. Между рекурсивными и нерекурсивными решениями (итеративными) могут быть значительные различия в производительности.
Это был один из немногих простых примеров рекурсии.
Я перечисляю некоторые из примеров, на которых вы можете попрактиковаться или изучить рекурсию, чтобы получить опыт. Я не объясняю эти примеры, потому что, возможно, любой новичок прочтет эту статью, а затем он или она запутается, когда увидит эти предварительные примеры рекурсии в структуре данных. Чтобы упростить эту статью, я просто пишу названия примеров.
