Настройка рекурсии в Python
Функция sys.getrecursionlimit() возвращает текущее значение предела рекурсии, максимальную глубину стека интерпретатора Python. Этот предел предотвращает бесконечную рекурсию от переполнения стека языка C и сбоя Python. Это значение может быть установлено с помощью sys.setrecursionlimit() .
sys.setrecursionlimit(limit) :
Функция sys.setrecursionlimit() устанавливает максимальную глубину стека интерпретатора Python для ограничения. Этот предел предотвращает бесконечную рекурсию от переполнения стека языка C и сбоя Python.
Максимально возможный предел зависит от платформы. Пользователю может потребоваться установить более высокий предел, если у него есть программа, которая требует глубокой рекурсии и платформа, которая поддерживает более высокий предел. Это следует делать с осторожностью, так как слишком высокий лимит может привести к сбою.
Если новый предел глубины стека слишком низкий на текущей глубине рекурсии, возникает исключение RecursionError .
Изменено в Python 3.12: Ограничение рекурсии теперь применяется только к коду Python. Встроенные функции не используют ограничение рекурсии, но защищены другим механизмом, который не позволяет рекурсии вызывать сбой виртуальной машины.
- ОБЗОРНАЯ СТРАНИЦА РАЗДЕЛА
- События аудита CPython
- Функция argv модуля sys
- Имя используемой OS
- Различные сведения о версии Python
- Каталоги и пути интерпретатора Python
- Кодировка, используемая Python
- Настройка рекурсии
- Функции трассировки и профилирования кода модуля sys
- Функция breakpointhook() модуля sys
- Объекты stdin, stdout, stderr модуля sys
- Функции exc_info() и exception() модуля sys
- Функция getrefcount() модуля sys
- Атрибуты path и path_hooks модуля sys
- Список загруженных и скомпилированных модулей
- Атрибут float_info модуля sys
- Атрибут int_info модуля sys
- Атрибут maxsize модуля sys
- Атрибут byteorder модуля sys
- Функция exit() модуля sys
- Функция getsizeof() модуля sys
- Атрибут dont_write_bytecode модуля sys
- Функция warnoptions() модуля sys
- Переменные last_type, last_value, last_traceback
- Переменная sys.last_exc модуля sys
- Функция set_asyncgen_hooks() модуля sys
- Функция get_coroutine_origin_tracking_depth() модуля sys
Python-сообщество
- Начало
- » Python для новичков
- » Проблемы с рекурсией
#1 Окт. 14, 2010 18:58:31
Андрей Светлов От: Зарегистрирован: 2007-05-15 Сообщения: 3137 Репутация: 14 Профиль Адрес электронной почты
Проблемы с рекурсией
Сейчас будет много теории — а потом варианты решения.
Стек — непрерывная область памяти (в виртуальной адресации, разумеется).
Резервируется окно и в нем сверху выделяется кусок памяти.
По умолчанию на винде это выглядит так: ]
Размер стека потока должен быть указан до запуска этого самого потока, естественно.
Также очевидно, что готовый стек уже нельзя перенести в другое место — в нем записаны абсолютные адреса, перенос все ломает.
В общем случае стек еще и нельзя расширить — место за границами окна может быть занято.
Т.е. стек — это навсегда, пока поток не помрет.
Почему нельзя резервировать сразу очень много? Да потому, что объем виртуальной (адресуемой) памяти — конечен.
На Windows 32 bit это 2 гигабайта. Каждый поток ест по крайней мере 2 мегабайта на свой стек. Результат — невозможно запустить больше тысячи потоков.
На практике это число еще меньше.
Далее. Максимальный размер стека можно указать перед запуском потока — есть такой параметр у CreateThread.
Но для нового процесса размер стека для главного потока указать нельзя — CreateProcess о таком не заботится.
В linux есть ulimit, в Windows — ничего. А после запуска процесса (нашего питона, например) уже ничего поменять нельзя — поток стартовал, поезд ушел.
Но способ регулировки есть. В заголовках образа (exe файла, если по простому) есть параметр, указывающий размер зарезервированного стека.
Запускаем cmd.exe
cd “C:\Program Files\Microsoft Visual Studio 9.0\VC\”
vcvarsall.bat
cd bin
dumpbin.exe /HEADERS c:\Python27\python.exe
Выводит длинную простыню. Во втором заголовке (OPTIONAL HEADER VALUES) находим 1E8480 size of stack reserve. Это наши 2 мегабайта.
Увеличим вдвое:
editbin.exe /STACK:4000000 c:\Python27\python.exe
Через dumpbin можно проверить результат.
Выглядит кривовато — да так оно и есть. Не трогая питон — стек не увеличишь.
Есть еще один вариант. Сделать свой exe — запускатель интерпретатора (это несложно) и в нем указать желаемый размер стека.
Или запаковать все py2exe — а дальше вы поняли. Можно и py2exe поправить, чтобы размер сразу нужный был.
Главный вывод — не трогая запускаемый файл — стек не увеличишь (для главного потока).
Для потоков, созданных из питона можно перед запуском потока вызвать threading.stack_size
Только помните — размеры стеков станут разными. А это тоже неудобно и выглядит опять таки хаком.
Решения на Python
Первым делом нужно отметить, что Python, являясь языком интерпретируемым, а не компилируемым, не способен обеспечить должную скорость работы в большинстве задач. Эталонных решений на Python нет и не предполагается, поэтому используйте этот язык на свой страх и риск. Возможно, решение придётся переписывать на другом языке. Эмпирические наблюдения показывают, что Python использует до 10 раз больше памяти и около 10–100 раз больше времени по сравнению с аналогичным решением на C/C++.
Некоторые внешние библиотеки (numpy и др.) способны улучшить эти показатели, однако использование библиотек, отличных от стандартных, не допускается тестирующей системой. В отличие от компилируемых языков, где использование внешних библиотек приводит к ошибке компиляции, интерпретатор Python успешно осуществляет запуск такой программы и порождает исключение на строке import numpy (или при подключении другой библиотеки). Это, в свою очередь, трактуется тестирующей системой как ошибка во время исполнения и приводит к вердикту Run-time Error.
В Python стандартный размер программного стека невелик — меньше 1000 вызовов — чего вполне достаточно для нерекурсивной программы практически любого реалистичного уровня сложности, но часто недостаточно для рекурсивных алгоритмов. Увеличить размер стека можно при помощи функции sys.setrecursionlimit , однако нужно иметь в виду, что более предпочтительным решением проблемы будет итеративная версия алгоритма (возможно, с использованием структуры данных стек), поскольку кадр программного стека (stack frame) в Python может занимать много памяти (следовательно, требовать много времени).
Использование рекурсии более 1000 раз
Я новичок в программировании на Python(мой 1 язык программирования). Решал задачу №12 из Проекта Эйлера. Я использовал рекурсию в функции, но к сожалению, чтобы решить задачу, придётся использовать рекурсию более 1000 раз. Хотел бы узнать, как решить эту задачу по-прежнему используя рекурсию, для того чтобы знать об этом в будущем. Как можно улучшить код и что вы думаете о моих названиях переменных и функции? Вот так звучит задача : Последовательность треугольных чисел образуется путем сложения натуральных чисел. К примеру, 7-ое треугольное число равно 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. Первые десять треугольных чисел: 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, . Перечислим делители первых семи треугольных чисел: 1: 1 3: 1, 3 6: 1, 2, 3, 6 10: 1, 2, 5, 10 15: 1, 3, 5, 15 21: 1, 3, 7, 21 28: 1, 2, 4, 7, 14, 28 Как мы видим, 28 — первое треугольное число, у которого более пяти делителей. Каково первое треугольное число, у которого более пятисот делителей? Вот мой код:
def tringle_number(x): if x == 1: return 1 else: return x + tringle_number(x-1) for i in range(1, 900): a.append(tringle_number(i)) print(a) need = 0 all_number = [1] count = 0 for item in a: number = 0 for j in range(1, 100000): if item % j == 0: count = j number += 1 if number == 100: for items in all_number: need += 1 if need == 1: all_number.append(item) else: continue else: continue print(all_number[1]) Отслеживать
543 5 5 серебряных знаков 14 14 бронзовых знаков
задан 18 дек 2020 в 18:56