опасность рекурсивных функций

Часто люди говорят, что не рекомендуется использовать рекурсивные функции в python (ограничения глубины рекурсии, потребление памяти и т. Д.),

Я взял пример перестановки из этого вопроса .

def all_perms(str): if len(str) <=1: yield str else: for perm in all_perms(str[1:]): for i in range(len(perm)+1): yield perm[:i] + str[0:1] + perm[i:]

Впоследствии я преобразовал его в нерекурсивную версию (я новичок в python)

 def not_recursive(string): perm = [string[0]] for e in string[1:]: perm_next = [] for p in perm: perm_next.extend(p[:i] + e + p[i:] for i in range(len(p) + 1)) perm = perm_next for p in perm: yield p

И я сравнил их

 before=time() print len([p for p in all_perms("1234567890")]) print "time of all_perms %i " % (time()-before) before=time() print len([p for p in not_recursive("1234567890")]) print "time of not_recursive %i " % (time()-before) before=time() print len([p for p in itertools.permutations("1234567890")]) print "time of itertools.permutations %i " % (time()-before) того before=time() print len([p for p in all_perms("1234567890")]) print "time of all_perms %i " % (time()-before) before=time() print len([p for p in not_recursive("1234567890")]) print "time of not_recursive %i " % (time()-before) before=time() print len([p for p in itertools.permutations("1234567890")]) print "time of itertools.permutations %i " % (time()-before) того before=time() print len([p for p in all_perms("1234567890")]) print "time of all_perms %i " % (time()-before) before=time() print len([p for p in not_recursive("1234567890")]) print "time of not_recursive %i " % (time()-before) before=time() print len([p for p in itertools.permutations("1234567890")]) print "time of itertools.permutations %i " % (time()-before) того before=time() print len([p for p in all_perms("1234567890")]) print "time of all_perms %i " % (time()-before) before=time() print len([p for p in not_recursive("1234567890")]) print "time of not_recursive %i " % (time()-before) before=time() print len([p for p in itertools.permutations("1234567890")]) print "time of itertools.permutations %i " % (time()-before)

Результаты весьма интересны. Рекурсивная функция – самая быстрая из 5 сек, затем не рекурсивная 8 сек, а затем buildin 35 сек.

Так рекурсивные функции, что плохо в Python? Что не так с встроенными настройками itertools.permutations?

4 Solutions collect form web for “опасность рекурсивных функций”

Рекурсия «плохо» в Python, потому что она обычно медленнее, чем итеративное решение, а также потому, что глубина стека Python не является неограниченной. Для функции суммы, да, вы, вероятно, хотите неограниченную глубину, так как было бы разумно хотеть суммировать список из миллиона чисел, а дельта производительности станет проблемой с таким большим количеством элементов. В этом случае вы не должны использовать рекурсию.

С другой стороны, если вы идете по дереву DOM, читаемому из XML-файла, он вряд ли превысит глубину рекурсии Python (по умолчанию 1000). Это, конечно, могло, но, по сути, это, вероятно, не будет. Если вы знаете, какие данные вы будете работать с опережением времени, вы можете быть уверены, что не будете переполнять стек. Рекурсивная прогулка по дереву, на мой взгляд, гораздо естественнее писать и читать, чем итеративную, а накладные расходы на рекурсию – это, как правило, небольшая часть времени работы. Если для вас действительно важно, что вместо 14 требуется 16 секунд, бросание Psyco на это может быть лучшим использованием вашего времени.

Рекурсия кажется естественной приспосабливаемой к проблеме, которую вы опубликовали, и если вы считаете, что код легче читать и поддерживать таким образом, а производительность адекватна, то ищите его.

Я вырос, написав код на компьютерах, которые, как практический вопрос, ограничили глубину рекурсии примерно до 16, поэтому 1000 кажется мне роскошным. 🙂

Рекурсия хороша для проблем, которые поддаются чистым, ясным, рекурсивным реализациям. Но, как и все программы, вы должны выполнить некоторый алгоритм анализа, чтобы понять характеристики производительности. В случае рекурсии, помимо числа операций, вы также должны оценить максимальную глубину стека.

Большинство проблем возникает, когда новые программисты предполагают, что рекурсия волшебна, и не понимают, что под ней есть стек. Новые программисты также, как известно, выделяют память и никогда не освобождают ее, а также другие ошибки, поэтому рекурсия не уникальна в этой опасности.

Ваши тайминги совершенно неверны:

 def perms1(str): if len(str) <=1: yield str else: for perm in perms1(str[1:]): for i in range(len(perm)+1): yield perm[:i] + str[0:1] + perm[i:] def perms2(string): perm = [string[0]] for e in string[1:]: perm_next = [] for p in perm: perm_next.extend(p[:i] + e + p[i:] for i in range(len(p) + 1)) perm = perm_next for p in perm: yield p s = "01235678" import itertools perms3 = itertools.permutations

Теперь протестируйте его с помощью timeit:

 thc:~$ for i in 1 2 3; do echo "perms$i:"; python -m timeit -s "import permtest as p" "list(p.perms$i(ps))"; done perms1: 10 loops, best of 3: 23.9 msec per loop perms2: 10 loops, best of 3: 39.1 msec per loop perms3: 100 loops, best of 3: 5.64 msec per loop

Как вы можете видеть, itertools.permutations является самым быстрым, за которым следует рекурсивная версия.

Но и чистая функция Python не имела шансов быть быстрой, потому что они выполняют дорогостоящие операции, такие как добавление списков ala perm[:i] + str[0:1] + perm[i:]

Я не могу воспроизвести ваши результаты времени (в Python 2.6.1 в Mac OS X):

 >>> import itertools, timeit >>> timeit.timeit('list(all_perms("0123456789"))', ... setup='from __main__ import all_perms'), ... number=1) 2.603626012802124 >>> timeit.timeit('list(itertools.permutations("0123456789"))', number=1) 1.6111600399017334