Насколько безопасна рекурсия в Python?

Question

Я работаю над домашним заданием по искусственному интеллекту, и, несмотря на предложения моего профессора, я не собираюсь писать это задание на языке lisp.Тем не менее, я делаю хочу написать это рекурсивно, чтобы лучше было быть кратким и простым.Вот мой вопрос:

Имею ли я большой риск нехватки места в стеке, если я выполняю поиск по большому пространству состояний?Насколько глубокий стек Python идет?

Answer 1

Насколько глубокий стек Python идет?

Ограничение рекурсии по умолчанию в python составляет 1000 кадров. Вы можете использовать sys.setrecursionlimit(n), чтобы изменить это на свой страх и риск.

Если вы используете Python, я бы предложил использовать шаблон, более подходящий для языка. Если вы хотите использовать рекурсивный поиск по стилю и нуждаетесь в произвольной глубине стека, вы можете использовать расширенные генераторы (сопрограммы) python для создания «шаблона батута» (например, PEP342 )

и, несмотря на предложения моего профессора, я не собираюсь писать это задание на lisp

Если упражнение предназначено для рекурсии, лучше всего подойдет язык с оптимизированным хвостовым вызовом, такой как шутка.

Answer 2

Рекурсия в Python (то есть CPython) не может идти глубже, чем sys.getrecursionlimit(). Вы можете установить этот предел на другое значение с помощью sys.setrecursionlimit.

вижу три варианта:

1. В конце концов используйте Lisp, он оптимизирован для рекурсивных проблем (а умные компиляторы Lisp устранят хвостовую рекурсию)
2. Установите предел рекурсии в рекурсивной функции, чтобы получить неограниченную рекурсию (с риском, что программа съест пылающая смерть )
3. Использовать итерацию с явным стеком. Простое list подойдет. append это push, pop это pop.

Answer 3

>>> i=0
>>> def a():
...     global i
...     i += 1
...     try:
...             a()
...     except:
...             print(i)
... 
>>> a()
999
>>> import sys
>>> sys.getrecursionlimit()
1000

Не уверен, поможет ли это

Answer 4

Как уже отмечали другие, вы можете увеличить глубину рекурсии, используя sys.setrecursiondepth(), хотя существует риск переполнения стека C (при условии, что вы используете CPython).Если вы столкнулись с этой проблемой, вы можете создать поток с большим размером стека, вызвав thread.stack_size() с новым размером стека, а затем породить новый поток для выполнения реальной работы.

Answer 5

Python ограничивает глубину рекурсии значением, которое вы можете узнать, вызвав sys.getrecursionlimit, и измените, вызвав sys.setrecursionlimit.Значение по умолчанию не очень большое.Если вы установите его слишком высоко, то вы можете в конечном итоге выбросить стек C, когда Python возвращается.То, как высоко «слишком высокий», зависит от платформы, хотя значение по умолчанию должно быть безопасным (вы получаете исключение Python, а не сбой) на всех платформах.оптимизация звонков.Схема - самый известный пример;это Лиспский диалект.Вы должны изучить изучение хотя бы одного языка, похожего на Лисп, независимо от того, насколько сильно вам не нравится ваш профессор.