Максимальная глубина рекурсии
Рекурсия в своей работе использует специальный участок памяти -
стек, в котором хранятся все локальные переменные, адреса возврата и др. Когда количество вызовов функции становится слишком большим и стек не может больше вместить данных, происходит переполнение стека. В результате при выполнении программы мы можем увидеть сообщение об ошибке:
RecursionError: maximum recursion depth exceeded in comparison
В Python есть ограничение на глубину рекурсии из-за максимальной глубины стека вызовов. По умолчанию это ограничение равно 1000 вызовам, то есть функция может вызывать саму себя не более 1000 раз, прежде чем будет сгенерировано исключение RecursionError.
Чтобы увеличить это ограничение, можно использовать модуль sys и метод setrecursionlimit(). Однако, стоит помнить, что изменение этого ограничения может привести к тому, что программа начнет потреблять больше памяти и увеличится время выполнения.
Пример 3. Увеличиваем глубину рекурсии
Алгоритм вычисления функции F(n) задан следующими соотношениями:
F(n) = n при n > 5000
F(n) = 3 + F(n+1), если n ≤ 5000
Чему равно значение функции F(100) + F(90)?
В данном примере нет вызовов функций с одинаковыми значениями, поэтому повторных вычислений не будет. Но самих вызовов будет очень много, так как нам необходимо дойти до базового случая, при котором n > 5000. Это больше 1000 вызовов. Для решения этой задачи необходимо увеличить глубину рекурсии. Можно увеличить до 5000 (можно сделать и больше, например, 1000000, но не забывайте, что чем больше значение мы установим, тем дольше будет выполняться программа).
Программа для решения задачи