В Python функция является рекурсивной, если она вызывает сама себя и имеет условие завершения, не позволяющее функции вызывать себя бесконечно. Рекурсивные функции состоят из двух частей: базового случая и рекурсивного случая.
Классический пример рекурсивной фунции - факториал:
В этом примере функция factorial() принимает на вход целое число n и возвращает факториал n. Базовый случай - это когда n равно 0, в этом случае функция возвращает 1. Рекурсивный случай - когда n больше 0, в этом случае функция вызывает сама себя с аргументом n-1 и умножает результат на n.
За и Против Рекурсии в Python
Использование рекурсии в Python имеет несколько преимуществ.
- Рекурсивный код имеет более чистый вид, и сгенерировать последовательность с помощью рекурсии может быть проще, чем с помощью вложенной итерации.
- Рекурсия упрощает код, поскольку разбивает задачу на небольшие по объему действия.
- Это удобный способ реализации непостоянного количества вложенных циклов.
Однако использование рекурсии в Python имеет и некоторые недостатки.
- Рекурсивные вызовы дороги, они занимают много памяти и времени.
- Рекурсивные функции трудно отлаживать, и даже одна строка кода может привести к ошибке.
- Рекурсивные решения всегда логичны, и их крайне сложно трассировать.
Наконец, Python останавливает вызовы функций после глубины в 1000 вызовов, и если глубина рекурсии превысит этот предел, программа может аварийно завершиться.
Упомянутый выше лимит глубины рекурсии в Python можно увеличить или уменшьить используя следующий код:
sys.setrecursionlimit(i)
Где i - лимит рекурсии, который вы бы хотели установить.
Главное помнить, что такой довольно низкий лимит по умолчанию стоит неспроста, и увеличивая его без необходимости и на слишком большие величины, вы при запуске программы с ошибкой рискуете получить намертво зависший интерпретатор.
Когда используется Рекурсия
Рекурсия полезна, когда проблему можно разбить на более мелкие подпроблемы, которые аналогичны исходной проблеме.
Рекурсия обычно используется в алгоритмах, которые обращаются к нелинейным структурам данных, таким как деревья и графы. Она также используется в алгоритмах сортировки, таких как quicksort и mergesort.
Пример. Обходим дерево используя рекурсию
В данном примере функция traverse_tree() принимает на вход узел дерева и печатает значение узла. Затем она рекурсивно вызывает саму себя с левым и правым дочерними узлами текущего узла в качестве аргументов. Этот процесс будет продолжаться до тех пор, пока не будут посещены все узлы дерева.
🎉✨ Поздравляю с завершением чтения статьи
Если Вам понравилось, можете подписаться, оставить комментарий и поставить лайк.
Также, можете взглянуть на некоторые из моих других публикаций, чтобы найти еще больше отличного контента 🔥: