Здравствуйте! В своем прошлом посте я вскользь упомянул рекурсию, но особо не пояснил про нее. Надо восполнить пробел. Тем более, что для кого-то это может быть полезным. Для начала определимся, что же такое рекурсия. Как пишет нам википедия:
В программировании рекурсия — вызов функции (процедуры) из неё же самой, непосредственно (простая рекурсия) или через другие функции (сложная или косвенная рекурсия), например, функция
вызывает функцию
, а функция
— функцию
. Количество вложенных вызовов функции или процедуры называется глубиной рекурсии.
Проще сказать нельзя. Про рекурсии есть известная поговорка:
Чтобы понять рекурсию, нужно сперва понять рекурсию
Итак, питон позволяет работать с рекурсиями легко и непринужденно. Самый первый пример рекурсии, с которой сталкиваются большинство программистов - это нахождение факториала. Код может быть таким:
def factorial(n):
if n <= 1: return 1
else: return n * factorial(n - 1)
Как видно, мы записали инструкцию if else слегка необычным для питона способом, но это позволяется в данном случаее, ввиду того, что читабельность здесь не ухудшается, но не следует злоупотреблять таким стилем. И вообще, PEP8 всех рассудит. :)
Теперь проясним несколько важных особенностей, о которых всегда нужно помнить при работе с рекурсиями.
Также, всегда следует определять точки выхода из рекурсивных функций. Это как с циклами - бесконечный цикл может здорово «просадить» вашу операционную систему. И наконец, где лучше применять рекурсию, а где лучше воздержаться и обойтись, например циклами. Конечно, здесь многое зависит от задачи, но всегда следует помнить, что рекурсия в разы медленнее цикла. Так уж устроен питон, что вызов функции дорого вам обходится :) Вообще, в циклах не стоит вызывать функции, а уж рекурсивные функции и подавно.
Рекурсия хорошо подходит там, где производительность не слишком важна, а важнее читабельность и поддержка кода. К примеру, напишите две функции для обхода дерева каталогов, одну рекурсивную, другую с циклами. Сравните полученный код, сделайте выводы. Затем, через неделю другую вернитесь к этому коду и добавьте в каждую из функций какую-нибудь новую задачу. Снова, сравните код и время, затраченное на понимание и написание кода и сделайте окончательный вывод. Помните, что у вас свой стиль и свои задачи, и писать так, а не иначе только из-за того, что так написано где-то в книжке или на форуме не всегда означает, что этот стиль подходит к вашей задаче. А закончу я еще одной цитатой:
Всегда пишите код так, будто сопровождать его будет склонный к насилию психопат, который знает, где вы живете. © Martin Golding.
Помните об этом :) Спасибо за внимание!