What Is the Maximum Recursion Depth in Python
The maximum recursion depth in Python is 1000.
You can verify this by calling sys.getrecursionlimit() function:
You can change the limit by calling sys.setrecursionlimit() method.
Consider this a dangerous action!
If possible, instead of tweaking the recursion limit, try to implement your algorithm iteratively to avoid deep recursion.
Python Maximum Recursion Depth Exceded in Comparison
Whenever you exceed the recursion depth of 1000, you get an error in Python.
For example, if we try to compute a too large Fibonacci number, we get the recursion depth error.
This error says it all—maximum recursion depth exceeded in comparison. This tells you that Python’s recursion depth limit of 1000 is reached.
But why is there such a limit? More importantly, how can you overcome it?
Let’s answer these questions next.
Why Is There a Recursion Depth Limit in Python
A recursive function could call itself indefinitely. In other words, you could end up with an endless loop.
Also, a stack overflow error can occur even if the recursion is not infinite. This can happen due to too big of a stack frame.
In Python, the recursion depth limit takes these risks out of the equation.
Python uses a maximum recursion depth of 1000 to ensure no stack overflow errors and infinite recursions are possible.
This recursion limit is somewhat conservative, but it is reasonable as stack frames can become big in Python.
What Is a Stack Overflow Error in Python
Stack overflow error is usually caused by too deep (or infinite) recursion.
This means a function calls itself so many times that the space needed to store the information related to each call is more than what fits on the stack.
How to Change the Recursion Depth Limit in Python—Danger Zone!
You can change the maximum recursion depth in Python. But consider it a dangerous action.
To do this, call the sys.setrecursionlimit() function.
For example, let’s set the maximum recursion depth to 2000 :
Temporarily Change the Recursion Depth Limit in Python
Do you often need to tweak the recursion depth limit in your project?
If you do, consider using a context manager. This can improve the quality of your code.
For example, let’s implement a context manager that temporarily switches the recursion limit:
Now you can temporarily change the recursion depth to perform a recursive task.
When this operation completes, the context manager automatically switches the recursion depth limit back to the original value.
How to get rid of maximum recursion depth error or better solve this?
Problem: We have a square grid of 5 rows and 4 columns. We need to use these numbers to fill the grid; 1,2,3,4,5,6,7,8,9,10,12,18,20,21,24,27,30,35,36,40 . We need to fill the grid in such a way that every horizontal and vertical neighbors should divide other without remainder. For example, 12 and 3 can be neighbors because 12 % 3 == 0 , but 5 and 12 can’t. Grid 2×2 is given to be 10 .
I tried to solve problem using a list of sets. Each set represent possible values for each grid. When every set has only one element, problem is solved. Here are the functions I use to try to solve this problem (I added whole thing just in case, but I think my problem is in solve function.);
I think this algorithm should solve the problem. But I am exceding maximum recursion depth. Any ideas how to work around this, or how should I solve this problem better in Python?
This is not a homework question. I am working on this by myself.
3 Answers 3
To avoid blowing up your stack, a more robust approach is to devise an encoding for your partial solutions (partially filled in board), and implement the backtracking yourself. That will require a lot less memory than relying on python’s stack.
Google’s Peter Norvig has written an illuminating article describing how he used such techniques to build an efficient backtracking sudoku solver. It uses a technique he calls «constraint propagation» to limit the space of options, so that the solution can be quickly found via brute force backtracking search (that is, without checking every possible grid of numbers, but only pursuing partial grids that might still lead to a solution). I think you will find it extremely applicable, not only for the general ideas but also for the specifics: Your problem, as you have approached it, is extremely close to a sudoku solver.
There’s a way to set custom value for Python recursion limit (which is 1000 by default):
You can add those lines before recursive call and if the problem remains, you have to review your implementation for other possible bugs.
it’s a rainy day here, so i wrote a solution. i can post if you want, but perhaps you would rather find it yourself?
here are some hints:
your code doesn’t seem to start with 10 at (2,2)
when trying a new value, you could add it to any empty space. the best space to try is one that has lots of neighbours, because that lets you test and reject bad values quickly.
assumed above, or a different way of saying the same thing — my search was over values. so i chose a location for «next move» and tried each value there. the opposite would be to search over locations (chose a «next value» and search with that value at each location), but that is not as efficient (see above).
when backtracking and re-trying, always follow the same pattern of locations. for example, (2,2) is 10 then (2,3) might be 40, then you might find nothing fits (2,4). so you backtrack and remove 40 and try a different number at (2,3). but the second number you try (after 10 and something at (2,2)) is always at (2,3). if you aren’t careful in this way you can end up testing many duplicate combinations. sorry not sure this is very clear. basically — choose a «path» that you fill and stick to it when searching and backtracking. since this path is chosen to maximise the number of neighbours (point above) i constructed it as i went on, but kept a cache of the path locations that i used when backtracking. this is easier to explain by showing the code.
for the table i used an array of arrays. when copying i re-used columns that were not changed. this should reduce memory use (i don’t know if it is important).
the search only needs to recurse 40 times (once for each value) so the stack is plenty big enough.
a simple search, in python, that tries each value in turn, backtracking on failure, runs
4 minutes on my laptop (assuming you use the hints above) (without the printing a slightly modified version takes just 8 seconds).
i found it was useful to have a python function that, given a grid and a position, returns a list (well, a generator, with yield ) of the coordinates of neighbours. that made writing other functions, like the one that tests whether a move is ok, simpler.
anyway, if you want the code or the solution (i changed my code to print all and there was just one) just ask and i will post. of course, it may have a bug too :o)
solution
i tweaked this some, and it now prints out the (2,2)=10 solution and then searches for all solutions (which is still running for me):
it starts by choosing the square where it will add the next number using next_xy() . it chooses a place near as many existing numbers as possible so that it can test and reject numbers efficiently (the position is saved in xy_moves so that it doesn’t need to be re-found if we backtrack). for each value it checks to see if putting the value at that position works using move_ok . if so, it calculates a new grid (with the value added) and a new list of values (with the used value removed) and recurses. recursion finishes when there are no values left to add.
and here is the result (each inner list is a column):
[deleted incorrect comment about recursion and generators]
it finished the global search — if you don’t fix (2,2) at the start there seem to be 12 solutions in total (3 distinct solutions if you ignore simple symmetries).
Python RecursionError: Maximum Recursion Depth Exceeded. Why?
You might have seen a Python recursion error when running your Python code. Why does this happen? Is there a way to fix this error?
A Python RecursionError exception is raised when the execution of your program exceeds the recursion limit of the Python interpreter. Two ways to address this exception are increasing the Python recursion limit or refactoring…
Written by Claudio Sabato
I’m a Software Engineer and Programming Coach. I want to help you in your journey to become a Super Developer!
Максимальная глубина рекурсии Python превышена в сравнении
Ismycode |. Прежде чем прыгать в ошибку, превышена максимальная глубина рекурсии по сравнению. Давайте … Помечено с Python, программированием, CodeNewie.
- Автор записи
Прежде чем прыгать в ошибку, Максимальная глубина рекурсии превышена в сравнении Отказ Сначала понять основы рекурсии и как работает рекурсион в Python.
Что такое рекурсия?
Рекурсия на языке компьютерных языков – это процесс, в котором функция вызывает себя прямо или косвенно, и соответствующая функция называется рекурсивной функцией.
Классический пример рекурсии
Наиболее классическим примером рекурсивного программирования каждый извлек факториал номера. Факториал числа – это Продукт всех положительных целых чисел меньше или равен данному положительному целым числу.
Например, факториал (5) составляет 5 * 4 * 3 * 2 * 1, а факториал (3) составляет 3 * 2 * 1.
Точно так же вы можете использовать рекурсивные во многих других сценариях, таких как Фибоначчи серии , Башня Ханой , Обход деревьев , DFS графа , и т.д.
Почему Python бросает максимальную глубину рекурсии в сравнении?
Как мы уже знаем, рекурсивные функции вызывают сама прямо или косвенно, и во время этого процесса выполнение должно пройти бесконечно.
Python ограничивает количество раз, когда рекурсивная функция может позвонить сам по себе, чтобы убедиться, что она не выполняется бесконечно и вызывает ошибку переполнения стека.
Как проверить максимальную глубину рекурсии в Python?
Вы можете проверить максимальную глубину рекурсии в Python, используя код Sys.getRecursionLimit (). Python не имеет отличной поддержки для рекурсии из-за отсутствия TRE (устранение рекурсионного хвоста). По умолчанию предельный предел рекурсии в Python составляет 1000.
Как вы исправите максимальную глубину рекурсии RecursionError, при вызове объекта Python?
Давайте напишем рекурсивную функцию для расчета серии Fibonacci для данного номера.
Поскольку вы найдете фибоначчи из 1500, а лимит рекурсии по умолчанию в Python является 1000, вы получите ошибку « RecursionError: максимальная глубина рекурсии превышена в сравнении ».
Это может быть исправлено, увеличивая предел рекурсиона в Python, ниже – фрагмент о том, как вы можете увеличить предел рекурсии.
Закрытие мыслей
Этот код устанавливает максимальную глубину рекурсии до 1500, и вы даже можете изменить это на более высокий предел. Тем не менее, не рекомендуется выполнять эту операцию, так как ограничение по умолчанию в основном достаточно хорош, и Python не является функциональным языком, а рекурсия хвоста не является особенно эффективной техникой. Переписать алгоритм итеративно, если возможно, в целом, как правило, является лучшей идеей.