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.
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 your code using iteration instead of recursion.
Let’s go through some examples so you can understand how this works.
The recursion begins!
RecursionError: Maximum Recursion Depth Exceeded in Comparison
Let’s create a program to calculate the factorial of a number following the formula below:
Write a function called factorial and then use print statements to print the value of the factorial for a few numbers.
This is a recursive function…
A recursive function is a function that calls itself. Recursion is not specific to Python, it’s a concept common to most programming languages.
You can see that in the else statement of the if else we call the factorial function passing n-1 as parameter.
The execution of the function continues until n is equal to 0.
Let’s see what happens when we calculate the factorial for two small numbers:
After checking that __name__ is equal to ‘__main__’ we print the factorial for two numbers.
But, here is what happens if we calculate the factorial of 1000…
The RecursionError occurs because the Python interpreter has exceeded the recursion limit allowed.
The reason why the Python interpreter limits the number of times recursion can be performed is to avoid infinite recursion and hence avoid a stack overflow.
Let’s have a look at how to find out what the recursion limit is in Python and how to update it.
What is the Recursion Limit in Python?
Open the Python shell and use the following code to see the value of the recursion limit for the Python interpreter:
Interesting…the limit is 1000.
To increase the recursion limit to 1500 we can add the following lines at the beginning of our program:
If you do that and try to calculate again the factorial of 1000 you get a long number back (no more errors).
…this solution could work if like in this case we are very near to the recursion limit and we are pretty confident that our program won’t end up using too much memory on our system.
How to Catch a Python Recursion Error
One possible option to handle the RecursionError exception is by using try except.
It allows to provide a clean message when your application is executed instead of showing an unclear and verbose exception.
Modify the “main” of your program as follows:
Note: before executing the program remember to comment the line we have added in the section before that increases the recursion limit for the Python interpreter.
Now, execute the code…
You will get the following when calculating the factorial for 1000.
Definitely a lot cleaner than the long exception traceback.
Interestingly, if we run our program with Python 2.7 the output is different:
We get back a NameError exception because the exception of type RecursionError is not defined.
Looking at the Python documentation I can see that the error is caused by the fact that the RecursionError exception was only introduced in Python 3.5:
So, if you are using a version of Python older than 3.5 replace the RecursionError with a RuntimeError.
In this way our Python application works fine with Python2:
How Do You Stop Infinite Recursion in Python?
As we have seen so far, the use of recursion in Python can lead to a recursion error.
How can you prevent infinite recursion from happening? Is that even something we have to worry about in Python?
Firstly, do you think the code we have written to calculate the factorial could cause an infinite recursion?
Let’s look at the function again…
This function cannot cause infinite recursion because the if branch doesn’t make a recursive call. This means that the execution of our function eventually stops.
We will create a very simple recursive function that doesn’t have an branch breaking the recursion…
When you run this program you get back “RecursionError: maximum recursion depth exceeded”.
So, in theory this program could have caused infinite recursion, in practice this didn’t happen because the recursion depth limit set by the Python interpreter prevents infinite recursion from occurring.
How to Convert a Python Recursion to an Iterative Approach
Using recursion is not the only option possible. An alternative to solve the RecursionError is to use a Python while loop.
We are basically going from recursion to iteration.
Firstly we set the value of the factorial to 1 and then at each iteration of the while loop we:
- Multiply the latest value of the factorial by n
- Decrease n by 1
The execution of the while loop continues as long as n is greater than 0.
I want to make sure that this implementation of the factorial returns the same results as the implementation that uses recursion.
So, let’s define a Python list that contains a few numbers. Then we will calculate the factorial of each number using both functions and compare the results.
We use a Python for loop to go through each number in the list.
Our program ends as soon as the factorials calculated by the two functions for a given number don’t match.
Let’s run our program and see what we get:
Our implementation of the factorial using an iterative approach works well.
Conclusion
In this tutorial we have seen why the RecursionError occurs in Python and how you can fix it.
Two options you have are:
- Increase the value of the recursion limit for the Python interpreter.
- Use iteration instead of recursion.
Which one are you going to use?
I’m a Software Engineer and Programming Coach. I want to help you in your journey to become a Super Developer!
Рекурсия в Python
Если бы я хотел узнать сумму чисел от 1 до n, где n — натуральное число, я мог бы посчитать вручную 1 + 2 + 3 + 4 + . + (несколько часов спустя) + n. А можно просто написать цикл for :
Или использовать рекурсию:
У рекурсии есть несколько преимуществ в сравнении с первыми двумя методами. Рекурсия занимает меньше времени, чем выписывание 1 + 2 + 3 на сумму от 1 до 3.
Для recusion(4) рекурсия может работать в обратную сторону:
Вызов функций: (4 -> 4 + 3 -> 4 + 3 + 2 -> 4 + 3 + 2 + 1 -> 10)
Принимая во внимание, что цикл [for] работает строго вперед: (1 -> 1 + 2 -> 1 + 2 + 3 -> 1 + 2 + 3 + 4 -> 10). Иногда рекурсивное решение проще, чем итеративное решение. Это очевидно при реализации обращения связанного списка.
Как и когда происходит рекурсия
Рекурсия появляется когда вызов функции повторно вызывает ту же функцию до завершения первоначального вызова функции. Например, рассмотрим известное математическое выражение x! (т.е. факториал). Факториал определяется для всех неотрицательных целых чисел следующим образом:
Если число равно 0, то будет 1.
В противном случае ответом будет то, что число умножается на факториал на единицу меньше этого числа.
В Python наивная реализация факториала может быть определена как функция следующим образом:
Иногда функции рекурсии трудно понять, поэтому давайте рассмотрим поэтапно.
Рассмотрим выражение factorial(3) . Эта и все остальные вызовы функций создают новую среду. Среда представляет собой таблицу, которая сопоставляет идентификаторы (например, n, factorial, print и т.д.) с их соответствующими значениями.
В любой момент времени вы можете получить доступ к текущей среде с помощью locals() . В первом вызове функции единственная локальная переменная, которая определяется n = 3 .Поэтому locals() будет показывать <"n": 3>. Так как n == 3 , возвращаемое значение становится n * factorial(n — 1) .
На следующем этапе ситуация может немного запутаться. Глядя на наше новое выражение, мы уже знаем, что такое n . Однако мы еще не знаем, что такое factorial(n — 1) .
Во-первых, n — 1 принимает значение 2 .Затем 2 передаётся factorial как значение для n . Поскольку это новый вызов функции, создаётся вторая среда для хранения нового n .
Пусть A — первое окружение, а B — второе окружение. A всё ещё существует и равен <"n": 3>, однако B (что равно <"n": 2>) является текущей средой. Если посмотреть на тело функции, возвращаемое значение, опять же, n * factorial(n — 1) .
Не определяя это выражение, заменим его на исходное выражение return . Делая это, мы мысленно отбрасываем B , поэтому не забудьте заменить n соответственно (т.е. ссылки на B n заменены на n — 1) который использует A n ). Теперь исходное обратное выражение становится n * ((n — 1) * factorial((n — 1) — 1)) . Подумайте, почему так?
Теперь давайте определим factorial((n — 1) — 1)) . Так как A n == 3 , мы пропускаем 1 через factorial . Поэтому мы создаем новую среду C, которая равна <"n": 1>. Мы снова возвращаем значение n * factorial(n — 1) . Итак, заменим исходный factorial((n — 1) — 1)) выражения return аналогично тому, как раньше мы скорректировали исходное выражение return. Исходное выражение теперь n * ((n — 1) * ((n — 2) * factorial((n — 2) — 1))) .
Почти закончили. Теперь нам нужно оценить factorial((n — 2) — 1) . На этот раз мы пропустим через 0 . Следовательно, должно получиться 1 .
Теперь давайте проведём нашу последнюю замену. Исходное выражение return теперь n * ((n — 1) * ((n — 2) * 1)) . Напомню, что исходное выражение возврата оценивается под A , выражение становится 3 * ((3 — 1) * ((3 — 2) * 1)) . Здесь получается 6.
Чтобы убедиться, что это правильный ответ, вспомните, что 3! == 3 * 2 * 1 == 6 . Прежде чем читать дальше, убедитесь, что вы полностью понимаете концепцию среды и то, как они применяются к рекурсии.
Утверждение, if n == 0: return 1 , называется базовым случаем. Потому что это не рекурсия. Базовый случай необходим, без него вы столкнетесь с бесконечной рекурсией. С учетом сказанного, если у вас есть хотя бы один базовый случай, у вас может быть столько случаев, сколько вы хотите. Например, можно записать факториал таким образом:
У вас может также быть несколько случаев рекурсии, но мы не будем вдаваться в подробности, потому что это редкий случай, и его трудно мысленно обрабатывать.
Вы также можете иметь «параллельные» рекурсивные вызовы функций. Например, рассмотрим последовательность Фибоначчи, которая определяется следующим образом:
- Если число равно 0, то ответ равен 0.
- Если число равно 1, то ответ равен 1.
В противном случае ответ представляет собой сумму двух предыдущих чисел Фибоначчи.
Мы можем определить это следующим образом:
Я не буду разбирать эту функцию также тщательно, как и с factorial(3) , но окончательное значение возврата fib(5) эквивалентно следующему (синтаксически недействительному) выражению:
Решением (1 + (0 + 1)) + ((0 + 1) + (1 + (0 + 1))) будет 5 .
Теперь давайте рассмотрим еще несколько терминов:
Tail call — это просто вызов рекурсивной функции, который является последней операцией и должна быть выполнена перед возвратом значения. Чтобы было понятно, return foo(n — 1) — это хвост вызова, но return foo(n — 1) + 1 не является (поскольку операция сложения будет последней операцией).
Оптимизация хвоста вызова (TCO или tail cost optimization) — это способ автоматического сокращения рекурсии в рекурсивных функциях.
Устранение хвоста вызова (TCE или tail cost elimination) — это сокращение хвостового вызова до выражения, которое может быть оценено без рекурсии. TCE — это тип TCO.
Оптимизация хвоста вызова может пригодиться по нескольким причинам:
Интерпретатор может снизить объём памяти, занятый средами. Поскольку ни у кого нет неограниченной памяти, чрезмерные рекурсивные вызовы функций приведут к переполнению стека.
Интерпретатор может уменьшить количество переключателей кадров стека.
В Python нет TCO по нескольким причинам, поэтому для обхода этого ограничения можно использовать другие методы. Выбор используемого метода зависит от варианта использования. Интуитивно понятно, что factorial и fib можно относительно легко преобразовать в итеративный код следующим образом:
Обычно это самый эффективный способ устранения рекурсии вручную, но для более сложных функций может быть трудно.
Другим полезным инструментом является декодер lru_cache , который можно использовать для уменьшения количества лишних вычислений.
Теперь вы знаете, как избежать рекурсии в Python, но когда её нужно использовать? Ответ «не часто». Все рекурсивные функции могут быть реализованы итеративно. Это просто вопрос, как именно сделать. Однако есть редкие случаи, когда можно использовать рекурсию. Рекурсия распространена в Python, когда ожидаемые вводы не вызовут значительного количества вызовов рекурсивных функций.
Если вы интересуетесь рекурсией, стоит изучить функциональные языки, такие как Scheme или Haskell. На таких языках рекурсия намного полезней.
Хотя приведённый выше пример последовательности Фибоначчи, хорошо показывает, как применять определение в python и позже использовать кэш lru, при этом он имеет неэффективное время работы, из-за того, что выполняет 2 рекурсивных вызова. Количество вызовов функции растет экспоненциально до n .
В таком случае лучше использовать линейную рекурсию:
Но у этого примера есть проблема в возвращении пары числе вместо одного. Это показывает, что не всегда стоит использовать рекурсию.
Исследование дерева с рекурсией
Допустим, у нас есть такое дерево:
Если мы хотим перечислить все имена элементов, мы можем сделать это с помощью простого цикла for . У нас есть функция get_name() , которая возвращает строку с именем узла, функция get_children() , которая возвращает список всех подузлов данного узла в дереве, и функция get_root() для получить корневой узел.
Этот код работает хорошо и быстро, но что если под-узлы получили свои под-узлы? И эти под-узлы могут иметь больше под-узлов . Что если вы не знаете заранее, сколько их будет? Решением этой проблемы будет использование рекурсии.
Возможно, вы не хотите вывести, а вернуть список всех имён узлов. Это можно сделать с помощью передачи прокручиваемого списка в качестве параметра.
Увеличение максимальной глубины рекурсии
Существует предел глубины возможной рекурсии, который зависит от реализации Python. Когда предел достигнут, возникает исключение RuntimeError :
RuntimeError: Maximum Recursion Depth Exceeded
Пример программы, которая может вызвать такую ошибку:
Можно изменить предел глубины рекурсии с помощью
Чтобы проверить текущие параметры лимита, нужно запустить:
Если запустить тот же метод выше с новым пределом, мы получаем
В Python 3.5 ошибка стала называться RecursionError, которая является производной от RuntimeError.
Хвостовая рекурсия — как не надо делать
Хвостовая рекурсия — частный случай рекурсии, при котором любой рекурсивный вызов является последней операцией перед возвратом из функции.
Вот пример обратного отсчета, написанного с использованием хвостовой рекурсии:
Любое вычисление, которое может быть выполнено с использованием итерации, также может быть выполнено с использованием рекурсии. Вот версия find_max, написанная с использованием хвостовой рекурсии:
Хвостовую рекурсию лучше не использовать, поскольку компилятор Python не обрабатывает оптимизацию для хвостовых рекурсивных вызовов. В таких случаях рекурсивное решение использует больше системных ресурсов, чем итеративное.
Оптимизация хвостовой рекурсии с помощью интроспекции стека
По умолчанию рекурсивный стек Python не превышает 1000 кадров. Это ограничение можно изменить, установив sys.setrecursionlimit(15000) который быстрее, однако этот метод потребляет больше памяти. Вместо этого мы также можем решить проблему рекурсии хвоста, используя интроспекцию стека.
Чтобы оптимизировать рекурсивные функции, мы можем использовать декоратор @tail_call_optimized для вызова нашей функции. Вот несколько примеров общей рекурсии с использованием декоратора, описанного выше:
Чтобы выйти из рекурсии, нужно ввести команду stopCondition .
Исходная переменная должна быть передана рекурсивной функции, чтобы сохранить её.
Как увеличить глубину рекурсии в python
When you execute a recursive function in Python on a large input ( > 10^4), you might encounter a “maximum recursion depth exceeded error”. This is a common error when executing algorithms such as DFS, factorial, etc. on large inputs. This is also common in competitive programming on multiple platforms when you are trying to run a recursive algorithm on various test cases.
In this article, we shall look at why this error occurs and how to handle it in Python. To understand this, we need to first look at tail recursion.
Tail recursion –
In a typical recursive function, we usually make the recursive calls first, and then take the return value of the recursive call to calculate the result. Therefore, we only get the final result after all the recursive calls have returned some value. But in a tail recursive function, the various calculations and statements are performed first and the recursive call to the function is made after that. By doing this, we pass the results of the current step to the next recursive call to the function. Hence, the last statement in a Tail recursive function is the recursive call to the function.
This means that when we perform the next recursive call to the function, the current stack frame (occupied by the current function call) is not needed anymore. This allows us to optimize the code. We Simply reuse the current stack frame for the next recursive step and repeat this process for all the other function calls.
Using regular recursion, each recursive call pushes another entry onto the call stack. When the functions return, they are popped from the stack. In the case of tail recursion, we can optimize it so that only one stack entry is used for all the recursive calls of the function. This means that even on large inputs, there can be no stack overflow. This is called Tail recursion optimization.
Languages such as lisp and c/c++ have this sort of optimization. But, the Python interpreter doesn’t perform tail recursion optimization. Due to this, the recursion limit of python is usually set to a small value (approx, 10^4). This means that when you provide a large input to the recursive function, you will get an error. This is done to avoid a stack overflow. The Python interpreter limits the recursion limit so that infinite recursions are avoided.
Handling recursion limit –
The “sys” module in Python provides a function called setrecursionlimit() to modify the recursion limit in Python. It takes one parameter, the value of the new recursion limit. By default, this value is usually 10^3. If you are dealing with large inputs, you can set it to, 10^6 so that large inputs can be handled without any errors.
Example:
Consider a program to compute the factorial of a number using recursion. When given a large input, the program crashes and gives a “maximum recursion depth exceeded error”.