Настройка рекурсии в 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
Какова максимальная глубина рекурсии и как ее увеличить?
Она работает до n=997 , затем она просто ломается и выскакивает RecursionError: максимальная глубина рекурсии превышена при сравнении . Это просто переполнение стека? Есть ли способ обойти это? python recursion
Поделиться Источник 23 июля 2010 в 23:04
19 ответов
Это предохранитель от переполнения стека, да. Python (а точнее, реализация CPython) не оптимизирует хвостовую рекурсию, а необузданная рекурсия вызывает переполнение стека. Вы можете проверить ограничение рекурсии с помощью sys.getrecursionlimit :
import sys print(sys.getrecursionlimit()) и изменить ограничение рекурсии с помощью sys.setrecursionlimit :
sys.setrecursionlimit(1500) но делать это опасно — стандартное ограничение немного консервативное, но стековые рамки Python могут быть довольно большими. Python не является функциональным языком, и хвостовая рекурсия не является особенно эффективным методом. Переписывание алгоритма итеративно, если это возможно, в целом является лучшей идеей.
Поделиться 23 июля 2010 в 23:08
Похоже, вам просто нужно установить большую глубину рекурсии:
import sys sys.setrecursionlimit(1500) Поделиться 23 июля 2010 в 23:07
Если вам часто нужно изменить ограничение рекурсии (например, при решении проблем с программированием), вы можете определить простой контекстный менеджер следующим образом:
import sys class recursionlimit: def __init__(self, limit): self.limit = limit def __enter__(self): self.old_limit = sys.getrecursionlimit() sys.setrecursionlimit(self.limit) def __exit__(self, type, value, tb): sys.setrecursionlimit(self.old_limit) Затем, чтобы вызвать функцию с пользовательским ограничением, вы можете сделать следующее:
with recursionlimit(1500): print(fib(1000, 0)) При выходе из тела оператора with ограничение рекурсии будет восстановлено до значения по умолчанию. P.S. Вы также можете увеличить размер стека процесса Python для больших значений ограничения рекурсии. Это можно сделать с помощью встроенной оболочки ulimit или файла limits.conf(5) , например.
Поделиться 01 мая 2018 в 16:37
Это для того, чтобы избежать переполнения стека. Интерпретатор Python ограничивает глубину рекурсии, чтобы помочь вам избежать бесконечных рекурсий, что приводит к переполнению стека. Попробуйте увеличить ограничение рекурсии ( sys.setrecursionlimit ) или переписать свой код без рекурсии. Из документации Python:
sys.getrecursionlimit() Возвратите текущее значение ограничения рекурсии, максимальную глубину стека интерпретатора Python. Это ограничение предотвращает бесконечную рекурсию, вызывающую переполнение стека C и вывод из строя Python. Его можно установить с помощью setrecursionlimit() .
Поделиться 23 июля 2010 в 23:08
resource.setrlimit также должен использоваться для увеличения размера стека и предотвращения сегментации Ядро Linux ограничивает стек процессов . Python хранит локальные переменные в стеке интерпретатора, и поэтому рекурсия занимает пространство стека интерпретатора. Если интерпретатор Python пытается преодолеть ограничение стека, ядро Linux приводит к ошибке сегментации. Ограничение размера стека контролируется системными вызовами getrlimit и setrlimit . Python предлагает доступ к этим системным вызовам через модуль resource . sys.setrecursionlimit упомянуто, например,на https://stackoverflow.com/a/3323013/895245 только увеличивает ограничение, которое интерпретатор Python сам накладывает на свой собственный размер стека, но не затрагивает ограничение, наложенное ядром Linux на процесс Python. Пример программы: main.py
import resource import sys print resource.getrlimit(resource.RLIMIT_STACK) print sys.getrecursionlimit() print # Will segfault without this line. resource.setrlimit(resource.RLIMIT_STACK, [0x10000000, resource.RLIM_INFINITY]) sys.setrecursionlimit(0x100000) def f(i): print i sys.stdout.flush() f(i + 1) f(0) Конечно, если вы продолжаете увеличивать setrlimit , ваша оперативная память в конечном итоге иссякнет, что либо замедлит работу вашего компьютера из-за безумия обмена, либо уничтожит Python с помощью Killer OOM . Из bash вы можете увидеть и установить ограничение стека (в kb) с помощью:
ulimit -s ulimit -s 10000 - Настройка размера стека в скрипте Python
- Какой жесткий предел рекурсии для Linux, Mac и Windows?
Протестировано на Ubuntu 16.10, Python 2.7.12.
Поделиться 28 января 2017 в 23:40
У меня была похожая проблема с ошибкой «Макс. глубина рекурсии превышена». Я обнаружил, что ошибка была вызвана поврежденным файлом в каталоге, в котором я работал с помощью os.walk . Если у вас возникли проблемы с решением этой проблемы и вы работаете с путями к файлам, убедитесь, что сузите его, так как это может быть поврежденный файл.
Поделиться 14 октября 2014 в 18:14
Я понимаю, что это старый вопрос, но для тех, кто читает, я бы рекомендовал не использовать рекурсию для таких проблем, как это — списки гораздо быстрее и полностью избегают рекурсии. Я бы реализовал это так:
def fibonacci(n): f = [0,1,1] for i in xrange(3,n): f.append(f[i-1] + f[i-2]) return 'The %.0fth fibonacci number is: %.0f' % (n,f[-1]) (Используйте n+1 в xrange, если вы начинаете подсчитывать свою последовательность Фибоначчи с 0 вместо 1.)
Поделиться 06 сентября 2013 в 03:17
Используйте язык, который гарантирует оптимизацию хвостового вызова. Или используйте итерацию. В качестве альтернативы, будьте любезны с декораторами.
Поделиться 23 июля 2010 в 23:12
Конечно, числа Фибоначчи можно вычислить в O(n), применяя формулу Бинта:
from math import floor, sqrt def fib(n): return int(floor(((1+sqrt(5))**n-(1-sqrt(5))**n)/(2**n*sqrt(5))+0.5)) Как отмечают комментаторы, это не O(1) а O(n), потому что 2**n . Также разница в том, что вы получаете только одно значение, в то время как с помощью рекурсии вы получаете все значения Fibonacci(n) вплоть до этого значения.
Поделиться 08 октября 2015 в 06:19
Если вы хотите получить только несколько чисел Фибоначчи, вы можете использовать метод матрицы.
from numpy import matrix def fib(n): return (matrix('0 1; 1 1', dtype='object') ** n).item(1) Это быстро, так как numpy использует алгоритм быстрого выравнивания. Вы получаете ответ в O(log n). И это лучше, чем формула Бнета, потому что она использует только целые числа. Но если вы хотите, чтобы все числа Фибоначчи были до n, то лучше сделать это с помощью запоминания.
Поделиться 17 февраля 2018 в 15:57
RecursionError: превышение максимальной глубины рекурсии при сравнении
Сначала лучше знать, когда вы выполняете рекурсивную функцию в Python на большом входе ( > 10^4), вы можете столкнуться с ошибкой «превышение максимальной глубины рекурсии».
Модуль sys в Python имеет функцию getrecursionlimit() которая может показывать ограничение рекурсии в вашей версии Python.
import sys print("Python Recursive Limitation = ", sys.getrecursionlimit()) По умолчанию в некоторых версиях Python это 1000, а в других — 1500
Вы можете изменить это ограничение, но очень важно знать, если вы увеличиваете его сильно, у вас будет ошибка переполнения памяти.
Так что будьте осторожны перед ее увеличением. Вы можете использовать setrecursionlimit() для увеличения этого ограничения в Python.
import sys sys.setrecursionlimit(3000) Пожалуйста, следуйте этой ссылке для получения дополнительной информации о причинах этой проблемы:
Поделиться 17 марта 2021 в 16:33
Мы можем сделать это, используя декоратор @lru_cache и метод setrecursionlimit() :
import sys from functools import lru_cache sys.setrecursionlimit(15000) @lru_cache(128) def fib(n: int) -> int: if n == 0: return 0 if n == 1: return 1 return fib(n - 2) + fib(n - 1) print(fib(14000)) Вывод
3002468761178461090995494179715025648692747937490792943468375429502230242942284835863402333575216217865811638730389352239181342307756720414619391217798542575996541081060501905302157019002614964717310808809478675602711440361241500732699145834377856326394037071666274321657305320804055307021019793251762830816701587386994888032362232198219843549865275880699612359275125243457132496772854886508703396643365042454333009802006384286859581649296390803003232654898464561589234445139863242606285711591746222880807391057211912655818499798720987302540712067959840802106849776547522247429904618357394771725653253559346195282601285019169360207355179223814857106405285007997547692546378757062999581657867188420995770650565521377874333085963123444258953052751461206977615079511435862879678439081175536265576977106865074099512897235100538241196445815568291377846656352979228098911566675956525644182645608178603837172227838896725425605719942300037650526231486881066037397866942013838296769284745527778439272995067231492069369130289154753132313883294398593507873555667211005422003204156154859031529462152953119957597195735953686798871131148255050140450845034240095305094449911578598539658855704158240221809528010179414493499583473568873253067921639513996596738275817909624857593693291980841303291145613566466575233283651420134915764961372875933822262953420444548349180436583183291944875599477240814774580187144637965487250578134990402443365677985388481961492444981994523034245619781853365476552719460960795929666883665704293897310201276011658074359194189359660792496027472226428571547971602259808697441435358578480589837766911684200275636889192254762678512597000452676191374475932796663842865744658264924913771676415404179920096074751516422872997665425047457428327276230059296132722787915300105002019006293320082955378715908263653377755031155794063450515731009402407584683132870206376994025920790298591144213659942668622062191441346200098342943955169522532574271644954360217472458521489671859465232568419404182043966092211744372699797375966048010775453444600153524772238401414789562651410289808994960533132759532092895779406940925252906166612153699850759933762897947175972147868784008320247586210378556711332739463277940255289047962323306946068381887446046387745247925675240182981190836264964640612069909458682443392729946084099312047752966806439331403663934969942958022237945205992581178803606156982034385347182766573351768749665172549908638337611953199808161937885366709285043276595726484068138091188914698151703122773726725261370542355162118164302728812259192476428938730724109825922331973256105091200551566581350508061922762910078528219869913214146575557249199263634241165352226570749618907050553115468306669184485910269806225894530809823102279231750061652042560772530576713148647858705369649642907780603247428680176236527220826640665659902650188140474762163503557640566711903907798932853656216227739411210513756695569391593763704981001125 Источник
Поделиться 26 октября 2019 в 15:26
Редактирование: 6 лет спустя я понял, что мой «Использовать генераторы» был легкомысленным и не ответил на вопрос. Мои извинения.
Я думаю, что мой первый вопрос будет: действительно ли вам нужно изменить ограничение рекурсии? Если нет, то, возможно, мои или любые другие ответы, которые не имеют отношения к изменению ограничения рекурсии, будут применяться. В противном случае, как было отмечено, переопределите ограничение рекурсии с помощью sys.getrecursionlimit(n) .
def fib(): a, b = 0, 1 while True: yield a a, b = b, a + b fibs = fib() #seems to be the only way to get the following line to work is to #assign the infinite generator to a variable f = [fibs.next() for x in xrange(1001)] for num in f: print num Вышеуказанная функция fib() адаптирована из Введения в Python Generators .
Поделиться 30 июля 2015 в 18:32
Как предложил @alex , вы можете использовать функцию-генератор для последовательного выполнения этого, а не рекурсивного.
Вот эквивалент кода в вашем вопросе:
def fib(n): def fibseq(n): """ Iteratively return the first n Fibonacci numbers, starting from 0. """ a, b = 0, 1 for _ in xrange(n): yield a a, b = b, a + b return sum(v for v in fibseq(n)) print format(fib(100000), ',d') # -> no recursion depth error Поделиться 12 июля 2016 в 16:58
Я хотел привести вам пример использования мемоизации для вычисления Фибоначчи, так как это позволит вам вычислять значительно большие числа с помощью рекурсии:
cache = <> def fib_dp(n): if n in cache: return cache[n] if n == 0: return 0 elif n == 1: return 1 else: value = fib_dp(n-1) + fib_dp(n-2) cache[n] = value return value print(fib_dp(998)) Это все еще рекурсивно, но использует простую хэштег-таблицу, которая позволяет повторно использовать ранее вычисленные числа Фибоначчи, вместо того, чтобы делать их снова.
Поделиться 12 марта 2019 в 13:59
Многие рекомендуют, чтобы увеличение лимита рекурсии было хорошим решением, но это не так, потому что всегда будет лимит. Вместо этого используйте итеративное решение.
def fib(n): a,b = 1,1 for i in range(n-1): a,b = b,a+b return a print fib(5) Поделиться 13 апреля 2016 в 08:56
import sys sys.setrecursionlimit(1500) def fib(n, sum): if n < 1: return sum else: return fib(n-1, sum+n) c = 998 print(fib(c, 0)) Поделиться 07 мая 2019 в 05:35
Я не уверен, что повторяю кого-то, но некоторое время назад какой-то добрый дух написал Y-оператор для рекурсивно вызываемой функции, например:
def tail_recursive(func): y_operator = (lambda f: (lambda y: y(y))(lambda x: f(lambda *args: lambda: x(x)(*args))))(func) def wrap_func_tail(*args): out = y_operator(*args) while callable(out): out = out() return out return wrap_func_tail а затем рекурсивная функция должна иметь форму:
def my_recursive_func(g): def wrapped(some_arg, acc): if : return acc return g(some_arg, acc) return wrapped # and finally you call it in code (tail_recursive(my_recursive_func))(some_arg, acc) для чисел Фибоначчи ваша функция выглядит так:
def fib(g): def wrapped(n_1, n_2, n): if n == 0: return n_1 return g(n_2, n_1 + n_2, n-1) return wrapped print((tail_recursive(fib))(0, 1, 1000000)) ..684684301719893411568996526838242546875 (на самом деле, это тоны цифр)
Поделиться 14 декабря 2020 в 14:33
Мы также можем использовать вариацию подхода динамического программирования снизу вверх
def fib_bottom_up(n): bottom_up = [None] * (n+1) bottom_up[0] = 1 bottom_up[1] = 1 for i in range(2, n+1): bottom_up[i] = bottom_up[i-1] + bottom_up[i-2] return bottom_up[n] print(fib_bottom_up(20000)) Рекурсия в Python, примеры кода
Python поддерживает рекурсию, когда функция может вызывать саму себя. На глубину вложения рекурсивных вызовов наложены ограничения. По умолчанию Python прерывает рекурсию и бросает исключение RecursionError , если обнаруживает, что глубина стека рекурсивных вызовов превысила 1000. Для этого предела можно установить другое значение с помощью функции setrecursionlimit() модуля sys .
Однако возможность изменения рекурсивного предела не означает, что вы можете сделать его сколько угодно большим. Абсолютное максимальное значение этого предела зависит от платформы, на которой выполняется программа. Максимальное значение рекурсивных вызовов можно посмотреть с помощью sys.getrecursionlimit() . В типичных случаях вы можете рассчитывать на рекурсию глубиной порядка нескольких тысяч уровней. При чрезмерно большой установленной глубине рекурсивных вызовов программа может завершиться аварийно. Такие выходящие из-под контроля рекурсии, являются одной из немногих причин возможного краха программы на Python, когда не срабатывает даже обычный защитный механизм исключений Python. Поэтому "НЕ ЛЕЧИТЕ" программу, в которой возникает исключение RecursionError , путем повышения разрешенной глубины вложения рекурсивных вызовов с помощью функции sys.setrecursionlimit(n) . В таких случаях лучше изменить организацию программы таким образом, чтобы избавиться от рекурсии или хотя бы постараться уменьшить глубину вложения рекурсивных вызовов.
Рекурсию в Python рассмотрим на примере решения факториала, функции, определённой на множестве неотрицательных целых чисел. Например 5! = 1 * 2 * 3 * 4 * 5 = 120
def factorial(n): if n == 0: return 1 else: return n * factorial(n - 1) x = factorial(5) print(x) # 120
Наглядный пример работы рекурсии:
def countDown(start, indent=0): print('-'*indent, '>', start) start = start - 1 indent = indent + 1 if start >= 0: # Рекурсивный вызов 'countDown', в которой # происходит печать строки, но только уже с # другими значениями, которые вычисляются выше countDown(start, indent) countDown(5, 2) # -- > 5 # --- > 4 # ---- > 3 # ----- > 2 # ------ > 1 # ------- > 0
Еще нагляднее:
def countDown(start, indent=1): print('-'*indent, 'UP:', start) if start == 0: # Здесь рекурсивный вызов 'countDown' прекратился, сначала # печатается эта строчка, потом все, что было накоплено в стеке. print('-'*indent, 'DOWN:', start) else: # Рекурсивный вызов 'countDown' countDown(start - 1, indent + 1) # Вызов 'countDown' не дает функции print выполнится # и накапливает (откладывает) ее исполнение в стеке print('-'*indent, 'DOWN:', start) countDown(5) # - UP: 5 # -- UP: 4 # --- UP: 3 # ---- UP: 2 # ----- UP: 1 # ------ UP: 0 # ------ DOWN: 0 # ----- DOWN: 1 # ---- DOWN: 2 # --- DOWN: 3 # -- DOWN: 4 # - DOWN: 5
- КРАТКИЙ ОБЗОР МАТЕРИАЛА.
- Функции это объекты
- Функции могут иметь атрибуты
- Функции могут храниться в структурах данных
- Функции могут быть вложенными
- Передача функции в качестве аргумента другой функции
- Область видимости переменных функции
- Операторы global и nonlocal
- Параметры (аргументы) функции
- Ключевые аргументы в определении функции Python
- Значение аргумента по умолчанию в функциях Python
- Варианты передачи аргументов в функцию Python
- Переменные аргументов *args и **kwargs в функции Python
- Распаковка аргументов для передачи в функцию Python
- Как оцениваются аргументы при вызове функции?
- Строгие правила передачи аргументов в функцию Python
- Инструкция return
- Анонимные функции (lambda-выражения)
- Строки документации в функциях Python
- Рекурсия
- Замыкания в функциях Python
- Перегрузка функций
Как исправить ошибку 'Превышена максимальная глубина рекурсии'
У меня есть код для ЕГЭ. Задания с 19 по 21. Я написал код для этих заданий, но при запуске кода выдает ошибку RecursionError: maximum recursion depth exceeded. Я целый день искал ошибку, гуглил в интернете , но ничего не нашел. Знатоки помогите пожалуйста.
from functools import lru_cache def xodi(h): a,b = h return (a+1,b),(a,b+1),(a*4,b),(a,b*4) @lru_cache(None) def game(h): a,b = h if a + b >= 310: return 'W' if any(game(m)== 'W' for m in xodi(h)): return 'P1' if any(game(m)== 'P1' for m in xodi(h)): return 'B1' if any(game(m)== 'B1' for m in xodi(h)): return 'P2' if all(game(m)== 'P2' or game(m)== 'P1' for m in xodi(h)): return 'B2' for s in range(1, 101): h = (16, s) if game(h) is not (None): print(s, game(h)) 
Вот собственно самое задание, прошу именно решить по моему коду, не писать новый.
Отслеживать
задан 29 апр 2022 в 13:09
3 1 1 серебряный знак 2 2 бронзовых знака
1 ответ 1
Сортировка: Сброс на вариант по умолчанию
import sys sys.setrecursionlimit(2000) # по умолчанию стоит 1000 Это увеличивает возможную глубину рекурсии до конкретного значения
Отслеживать
ответ дан 29 апр 2022 в 13:13
RuslanZanevskiy RuslanZanevskiy
610 3 3 серебряных знака 7 7 бронзовых знаков
Ну и как собственно мне это поможет?
29 апр 2022 в 13:30
При указании рекурсии 10000, то ничего не происходит
29 апр 2022 в 13:31
Да? Я копировал ваш код, ставил 2000 и уменя все прекрасно работало. Как это поможет? Мы увеличили допустимый лимит вызовов функции в глубину.
29 апр 2022 в 13:34
Вставляйте этот код перед вызовом всех функций(в начале файла)
29 апр 2022 в 13:34
Мне кажется если вы используете рекурсию вы понимаете что функция вызывает сама себя много раз из-за чего тратиться память стэка вызовов, поэтому такое поведение и ограничивается. Кстати StackOverflow с английсткого и есть переполнение стэка.