Рекурсия в Python

Дата публикации:30 апреля 2013 г. 4:22:13

Здравствуйте! В своем прошлом посте я вскользь упомянул рекурсию, но особо не пояснил про нее. Надо восполнить пробел. Тем более, что для кого-то это может быть полезным. Для начала определимся, что же такое рекурсия. Как пишет нам википедия:

В программировании рекурсия — вызов функции (процедуры) из неё же самой, непосредственно (простая рекурсия) или через другие функции (сложная или косвенная рекурсия), например, функция $A$ вызывает функцию $B$ , а функция $B$ — функцию $A$ . Количество вложенных вызовов функции или процедуры называется глубиной рекурсии.

Проще сказать нельзя. Про рекурсии есть известная поговорка:

Чтобы понять рекурсию, нужно сперва понять рекурсию

Итак, питон позволяет работать с рекурсиями легко и непринужденно. Самый первый пример рекурсии, с которой сталкиваются большинство программистов - это нахождение факториала. Код может быть таким:

def factorial(n):
    if n <= 1: return 1
    else: return n * factorial(n - 1)

Как видно, мы записали инструкцию if else слегка необычным для питона способом, но это позволяется в данном случаее, ввиду того, что читабельность здесь не ухудшается, но не следует злоупотреблять таким стилем. И вообще, PEP8 всех рассудит. :)

Теперь проясним несколько важных особенностей, о которых всегда нужно помнить при работе с рекурсиями.

Существует ограничение на глубину рекурсии. По умолчанию оно равно 1000.
Для того, чтобы изменить это ограничение нужно вызвать функцию sys.setrecursionlimit(), а для просмотра текущего лимита sys.getrecursionlimit().
Не смотря на это - существует ограничение размером стека, который устанавливается операционной системой.
Рекурсия в Python не может использоваться в функциях-генераторах и сопрограммах. Однако, можно это поведение исправить, но лучше не стоит.
И последнее - применение декораторов к рекурсивным функциям может приводить к неожиданным результатам, поэтому будьте очень осторожны декорируя рекурсивные функции.

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

Рекурсия хорошо подходит там, где производительность не слишком важна, а важнее читабельность и поддержка кода. К примеру, напишите две функции для обхода дерева каталогов, одну рекурсивную, другую с циклами. Сравните полученный код, сделайте выводы. Затем, через неделю другую вернитесь к этому коду и добавьте в каждую из функций какую-нибудь новую задачу. Снова, сравните код и время, затраченное на понимание и написание кода и сделайте окончательный вывод. Помните, что у вас свой стиль и свои задачи, и писать так, а не иначе только из-за того, что так написано где-то в книжке или на форуме не всегда означает, что этот стиль подходит к вашей задаче. А закончу я еще одной цитатой:

Всегда пишите код так, будто сопровождать его будет склонный к насилию психопат, который знает, где вы живете. © Martin Golding.

Помните об этом :) Спасибо за внимание!