RecursionError: maximum recursion depth exceeded in comparison
К сожалению, на значениях m, n = -10779,-15755 сталкиваюсь с исключением RecursionError: maximum recursion depth exceeded in comparison . Попытка задать лимит для количества рекурсий не даёт результатов, когда целочисленные значения возрастают до 100 000 — память не позволяет приблизиться к этим числам. Пока остановились с преподавателем на том, что эту задачу посредством Python 3.9 не решить. Возможно здесь есть те, кто может доказать обратное. Хочется посмотреть какими средствами можно справиться.
Отслеживать
68k 218 218 золотых знаков 79 79 серебряных знаков 221 221 бронзовый знак
задан 15 дек 2021 в 14:26
Артемий Шувалов Артемий Шувалов
79 1 1 серебряный знак 6 6 бронзовых знаков
Пожалуйста, уточните вашу конкретную проблему или приведите более подробную информацию о том, что именно вам нужно. В текущем виде сложно понять, что именно вы спрашиваете.
15 дек 2021 в 14:29
Во-первых, есть Stackless Python: ru.stackoverflow.com/questions/1220820/…
15 дек 2021 в 14:51
@Stanislav, всё оч просто. Вот текст задачи, который нужно решить конкретно через рекурсию. Не идёт речи о том, что это хорошо/плохо. Речь идёт о том, чтобы исследовать python на возможность решения такой задачи. Я придумать ничего не смог.
16 дек 2021 в 8:11
2 ответа 2
Сортировка: Сброс на вариант по умолчанию
Отличная задача. Спасибо!
Чтобы обойти ограничение на глубину рекурсии нужно заменить линейную рекурсию на древовидную. Число операций в линейной рекурсии равно её глубине. Число операций в древовидной рекурсии можно довести до степени двойки от её глубины.
Функция tree_add может сделать до level^2 операций. Если этого хватило чтобы обнулить b (второй элемент p ), хорошо. Если нет, функция возвращает неполный результат.
# level - неотрицательное число # p - пара чисел (a, b), которые нужно сложить # если |b| 0 # или (a - 2^level, b + 2^level), если b < 0 def tree_add(level, p): if level == 0: a, b = p if b == 0: return a, 0 if b >0: return a + 1, b - 1 if b < 0: return a - 1, b + 1 return tree_add(level - 1, tree_add(level - 1, p)) Функция linear_add вызывает tree_add до тех пор пока та не сумеет выполнить всю работу. Уровень каждый раз увеличивается на единицу, соответственно tree_add может выполнить в два раза больше работы:
def linear_add(level, p): a, b = tree_add(level, p) if b == 0: return a return linear_add(level + 1, (a, b)) Верхний уровень - просто сложение:
def add(a, b): return linear_add(0, (a, b)) Можно показать что глубина рекурсии не превосходит 2log2(b) , что позволяет обрабатывать числа до 2^500 .
@>>> add(1_000_000, 1_000_000) 2000000 Maximum recursion depth exceeded in comparison python как исправить
Скачай курс
в приложении
Перейти в приложение
Открыть мобильную версию сайта
© 2013 — 2023. Stepik
Наши условия использования и конфиденциальности
Public user contributions licensed under cc-wiki license with attribution required
Почему выводит RecursionError: maximum recursion depth exceeded in comparison?
Определите наименьшее значение суммы n+m такое, что значение F(n, m) больше числа 15 и выполняется условие n≠m, n и m – натуральные числа. Запишите в ответе сначала значения n и m, при которых указанная сумма достигается, в порядке неубывания, а затем – соответствующее значение F(n, m). Числа в ответе разделяйте пробелом.
Код, данный в задаче:
def F(n,m): if nTraceback (most recent call last): File "main.py", line 12, in if F(a, b) > 15 and a != b and a + b < minnm: File "main.py", line 5, in F return F(n-m, m) File "main.py", line 5, in F return F(n-m, m) File "main.py", line 5, in F return F(n-m, m) [Previous line repeated 995 more times] File "main.py", line 2, in F if n < m: RecursionError: maximum recursion depth exceeded in comparisondef F(n, m): if n < m: n, m = m, n if n != m: return F(n-m, m) else: return n minnm = 0 for a in range(1, 10000): for b in range(1, 10000): if F(a, b) >15 and a != b and a + b < minnm: print(a, b, F(a, b)) minnm = a + b- Вопрос задан более года назад
- 751 просмотр
Комментировать
Решения вопроса 1
Для правильного вопроса надо знать половину ответа
[Previous line repeated 995 more times]
То есть, у вас глубина стека ограничена 1000 вызовов. Если проанализировать функцию, то видно, что при n = 1 и m > 1 глубина стека вызовов будет m.
Таким образом у вас два варианта - переписать функцию или ограничить циклы до ~990.
Кроме того, функция симметрична относительно порядка аргументов. Значит внутренний цикл можно начитать не с 1, а с a+1.
Ну или решить задачу аналитически.
Данная функция реализует алгоритм нахождения наибольшего общего делителя методом Евклида. F(n, m) = X означает, что n = iX, m = jX, где i и j - натуральные числа и
i != j.
n + m = (i + j)X.
Минимальная пара i и j будет 1 и 2. Минимальное значение X, большее 15 будет 16.
Получаем n = 16, m = 32, F(16, 32) = 16, n + m = 48.
How to Fix RecursionError in Python
The Python RecursionError is an exception that occurs when the maximum recursion depth is exceeded. This typically occurs when a function calls itself recursively, and the recursion doesn't have a proper stopping condition (base case).
What Causes RecursionError
A RecursionError in Python is caused by a function calling itself recursively without a proper base case. Python has a limit on the number of times a function can call itself recursively. This is to ensure that the function does not execute indefinitely. If this limit is exceeded by a recursive function, a RecursionError is raised.
Python RecursionError Example
Here’s an example of a Python RecursionError thrown when calling a recursive function that does not have a base case:
def func(): func() func() Since the recursive function func() does not have a terminating condition, calling it creates an infinite loop as the function keeps calling itself over and over again until the RecursionError: maximum recursion depth exceeded error occurs:
Traceback (most recent call last): File "test.py", line 4, in func() File "test.py", line 2, in func func() File "test.py", line 2, in func func() File "test.py", line 2, in func func() [Previous line repeated 996 more times] RecursionError: maximum recursion depth exceeded How to Fix RecursionError in Python
Here are some approaches to fix a recursion error in Python:
- Adding a base case: The most common cause of a recursion error is that the function does not have a base case to stop the recursion. In such cases, a base case can be added to the function that stops recursion when a condition is met.
- Increasing the recursion limit: Python has a default maximum recursion depth of 1000. If a function exceeds this limit, it can be increased using the sys.setrecursionlimit(n) function. Developers should be careful when increasing the limit as this can cause a crash if the recursion is not properly controlled.
- Using an iterative approach: If a recursive approach is causing a recursion error, it may be possible to use an iterative approach instead e.g. a for or while loop. This can reduce the risk of hitting the maximum recursion depth, and in some cases can also lead to more efficient and easier to understand code.
Track, Analyze and Manage Errors With Rollbar
Managing errors and exceptions in your code is challenging. It can make deploying production code an unnerving experience. Being able to track, analyze, and manage errors in real-time can help you to proceed with more confidence. Rollbar automates error monitoring and triaging, making fixing Python errors easier than ever. Try it today!