Как увеличить глубину рекурсии в python

Настройка рекурсии в 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 поддерживает рекурсию, когда функция может вызывать саму себя. На глубину вложения рекурсивных вызовов наложены ограничения. По умолчанию 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 2 2 бронзовых знака

1 ответ 1

Сортировка: Сброс на вариант по умолчанию

import sys sys.setrecursionlimit(2000) # по умолчанию стоит 1000

Это увеличивает возможную глубину рекурсии до конкретного значения

Отслеживать
ответ дан 29 апр 2022 в 13:13
RuslanZanevskiy RuslanZanevskiy
612 3 3 серебряных знака 7 7 бронзовых знаков
Ну и как собственно мне это поможет?
29 апр 2022 в 13:30
При указании рекурсии 10000, то ничего не происходит
29 апр 2022 в 13:31

Читать:

Как вставить картинку ссылку в html

Да? Я копировал ваш код, ставил 2000 и уменя все прекрасно работало. Как это поможет? Мы увеличили допустимый лимит вызовов функции в глубину.

29 апр 2022 в 13:34
Вставляйте этот код перед вызовом всех функций(в начале файла)
29 апр 2022 в 13:34

Мне кажется если вы используете рекурсию вы понимаете что функция вызывает сама себя много раз из-за чего тратиться память стэка вызовов, поэтому такое поведение и ограничивается. Кстати StackOverflow с английсткого и есть переполнение стэка.

Устранение рекурсии в Python

Привет, Хабр! Представляю вашему вниманию перевод статьи «Removing a recursion in Python, part 1» автора Эрика Липперта (Eric Lippert).

На протяжении последних 20 лет я восхищался простоте и возможностям Python, хотя на самом деле никогда не работал с ним и не изучал подробно.

В последнее время я присмотрелся к нему поближе — и он оказался действительно приятным языком.

Недавний вопрос на StackOverflow заставил меня задуматься, как преобразовать рекурсивный алгоритм в итеративный, и оказалось, что Python довольно подходящий язык для этого.
Проблема с которой столкнулся автор вопроса заключалась в следующем:

Игрок находится в произвольной клетке на пронумерованном поле;
Цель вернуться в клетку №1;
Если игрок находится на чётной клетке, он платит одну монету и проходит половину пути к клетке №1;
Если игрок находится на нечётной клетке, он может заплатить 5 монет и сразу перейти на первую клетку или заплатить одну монету и сделать один шаг к клетке №1 — на чётную клетку.

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

Задача имеет очевидное рекурсивное решение:

def cost(s): if s


Однако эта программа падала, достигая максимальной глубины рекурсии, вероятнее всего из-за того, что автор вопроса экспериментировал с очень большими числами. 
Следовательно возникает вопрос: как превратить рекурсивный алгоритм в итерационный на Python?
Перед тем как мы начнем, хочу отметить, что конечно существуют более быстрые решения этой конкретной задачи, сама по себе она не очень интересна.
Скорее эта задача послужила лишь отправной точкой в вопросе, как в общем случае избавиться от единственного рекурсивного вызова в программе на Python.
Смысл в том, что можно преобразовать любой простой рекурсивный метод и избавиться от рекурсии, а это всего лишь пример, который оказался под рукой.
Техника, которую я собираюсь показать, конечно не совсем соответствует тому, как принято писать на Python, вероятно решение в Python-стиле использовало бы генераторы или другие возможности языка.
Что я хочу показать здесь, так это как избавиться от рекурсии, используя последовательность маленьких и безопасных преобразований, приводящих функцию к такой форме, в которой легко произвести замену рекурсии на итерацию.
Для начала давайте посмотрим как привести программу к такой форме.
На первом шаге нашего преобразования я хочу чтобы вычисления производимые до рекурсивного вызова сводились к вычислению аргумента, а вычисления, после рекурсивного вызова, производились в отдельном методе, который принимает результат рекурсивного вызова.
def add_one(n): return n + 1 def get_min(n): return min(n + 1, 5) def cost(s): if s 

Вторым шагом я хочу вынести вычисление аргумента в отдельную функцию:
# . def get_argument(s): if s % 2 == 0: return s // 2 return s - 1 def cost(s): if s 

На третьем шаге, я хочу добавить вспомогательную функцию, которая будет выбирать функцию-продолжение, вызываемую после возврата из рекурсии.
Обратите внимание, что вспомогательная функция возвращает функцию.
#. def get_after(s): if s % 2 == 0: return add_one return get_min def cost(s): if s  

Теперь запишем это в более общей и краткой форме:
#. def is_base_case(s): return s  

Видно, что каждое проделанное изменение сохраняло смысл программы.
Сейчас проверка на чётность числа выполняется дважды, хотя до изменений проверка была одна.
Если мы захотим, то можем решить эту проблему объединив две вспомогательные функции в одну, возвращающую кортеж.
Но давайте не будем беспокоиться об этом в рамках решения этой задачи.
Мы свели наш рекурсивный метод до максимально общей формы.

В базовом случае: 

вычисляем значение, которое нужно вернуть;
возвращаем его.


вычисляем аргумент рекурсии;
производим рекурсивный вызов;
вычисляем возвращаемое значение;
возвращаем его.

Кое-что важное на что необходимо обратить внимание на этом шаге — это то, что after не должен сам содержать вызовов cost .
Способ, который я показываю здесь, удаляет единственный рекурсивный вызов.
Если у вас 2 и более рекурсии, то нам понадобится другое решение.
Как только мы привели наш рекурсивный алгоритм к такой форме, преобразовать его в итеративный уже просто.
Хитрость в том, чтобы представить, что происходит в рекурсивной программе.
Как мы делаем рекурсивный спуск: мы вызываем get_argument перед рекурсивным вызовом и вызываем функцию after после возврата из рекурсии.
То есть, все вызовы get_argument происходят перед всеми вызовами after. 
Поэтому мы можем преобразовать это в 2 цикла: первый вызывает get_argument и формирует список функций after, а второй вызывает все функции after:
#. def cost(s): # Создаём стек из функций "after". Все эти функции # принимают результат рекурсивного вызова и возвращают # значение, которое вычисляет рекурсивный метод. afters = [ ] while not is_base_case(s): argument = get_argument(s) after = get_after(s) afters.append(after) s = argument # Теперь у нас есть стек функций "after" : result = base_case_value(s) while len(afters) != 0: after = afters.pop() result = after(result) return result
Больше никакой рекурсии!
Выглядит как магия, но все что мы здесь делаем — то же самое, что делала рекурсивная версия программы и в том же порядке.
Этот пример отражает мысль, которую я часто повторяю о стеке вызовов: его цель сообщить то, что произойдёт дальше, а не то, что уже произошло!
Единственная полезная информация в стеке вызовов в рекурсивной версии программы — это какое значение имеет after, поскольку эта функция вызывается следующей, а все остальное на стеке не важно.
Вместо использования стека вызовов, как неэффективного и громоздкого способа хранения стека after, мы можем просто хранить стек функций after.
В следующий раз мы рассмотрим более сложный способ удаления рекурсии на Python.