Как исправить RecursionError: maximum recursion depth exceeded
from functools import *
@lru_cache(None)
def f(n):
if n == 1:
return 2
elif n > 1:
return f(n - 1) + n + 1
print(f(23023))
выдает это
File "C:\Users\zizib\PycharmProjects\pythonProject\№13ЕГЭ.py", line 8, in f
return f(n - 1) + n + 1
^^^^^^^^
[Previous line repeated 496 more times]
RecursionError: maximum recursion depth exceeded
Сколько не пыталась не смогла найти решение проблемы. Помогите пожалуйста
Ответы (2 шт):
Цикл вообще не нужен, можно обойтись формулой суммы ряда с небольшой модификацией
n = 23023
print(n*(n+1)//2+n)
265063799
Осмотр на месте
Поиск фразы "RecursionError: maximum recursion depth exceeded" приводит на страницу с документацией по RecursionError. Оттуда можно узнать про функции sys.getrecursionlimit и sys.setrecursionlimit. В Питоне установлен предел количества рекурсивных вызовов. Первая функция его возвращает, вторая его меняет.
Скорее всего у вас установлен предел в 1000 вызовов. Обратите внимание на строку в выводе программы: [Previous line repeated 496 more times]. Когда ошибка случилась, функция была вызвана рекурсивно около пятисот раз. Пятьсот - не тысячу, потому что на функцию надет декоратор @lru_cache(None), который сам по себе функция. Если не вдаваться в подробности, каждый раз когда вы вызываете f, вызывается пара вложенных функций: кэширующая оболочка и сама функция.
Значит нам надо увеличить предел, скажем до 50000. Это в два раза больше, чем нужный нам аргумент (мы хотим вычислить f(23023)). Делаем и немедленно получаем ошибку:
Segmentation fault (core dumped)
Стек не резиновый, его не хватает на такую глубокую рекурсию. Кое-что можно прочитать в вопросе Использование рекурсии более 1000 раз.
Новая надежда
Для небольших чисел функцию вычислить можно. Прибегнем к хитрости: рекурсивные вызовы прекращаются как только значение найдено в кэше. Заполним кэш вызывая функцию от меньших значений параметра к большим:
...
for n in range(1, 24000, 100):
f(n)
print(f(23023))
$ python f.py 265063799
Цикл заполняет кэш. Хотя цикл с шагом в сотню, кэш заполняется целиком. Когда требуется вычислить f(23023), соответствующее значение берётся из кэша и никакой глубокой рекурсии не требуется. Задача решена. Неприятно что для заполнения кэша надо знать в каком порядке вызывать f.
Очень странные дела
Можно написать универсальную обёртку, которая будет работать с любыми функциями.
NB Ненормальное программирование на грани фола. Но работает.
Идея в том чтобы обрабатывать RecursionError при вызове функции f. Помимо словаря-кэша обёртка хранит список stack с аргументами, которые не удалось вычислить. Рекурсивный вызов кладёт аргумент в список, вызывает f, убирает аргумент из списка:
stack.append(args)
cache[args] = f(*args)
stack.pop()
Если ошибки нет, список в конце пуст. Если рекурсия привела к ошибке, в списке остались аргументы вызовов. Тогда вычислим f от последнего элемента списка. Если успех, уберём аргумент и продолжим обработку пока список не опустеет. Если снова ошибка, список пополнится новым комплектом аргументов. И так далее, пока функция не будет вычислена. Вот код:
def cache(f):
cache = {}
stack = []
def wrap(*args):
if args not in cache:
if stack:
stack.append(args)
cache[args] = f(*args)
stack.pop()
else:
stack.append(args)
while stack:
args = stack[-1]
if args in cache:
stack.pop()
else:
try:
r = f(*args)
except RecursionError:
# print('RecursionError, len(stack)', len(stack))
pass
else:
cache[args] = r
return cache[args]
return wrap
@cache
def f(n):
if n == 1:
return 2
elif n > 1:
return f(n - 1) + n + 1
print(f(23023))
Этот код работает и работает быстро. Обработка ошибок увеличивает время в два раза по сравнению с воображаемым вариантом в котором нет ограничений на рекурсию. Раскомментируйте print и получите сорок шесть перехваченных ошибок о переполнении стека и вычисленное в конце концов значение функции:
$ python f.py RecursionError, len(stack) 499 RecursionError, len(stack) 997 RecursionError, len(stack) 1495 ... RecursionError, len(stack) 21913 RecursionError, len(stack) 22411 RecursionError, len(stack) 22909 265063799
Способ универсален, будет работать для любой чистой рекурсивной функции. Наивное вычисление чисел Фибоначчи:
...
@cache
def fib(n):
if n <= 1:
return n
return fib(n - 1) + fib(n - 2)
print(fib(1000))
$ python fib.py RecursionError, len(stack) 499 RecursionError, len(stack) 997 4346655768....6849228875
Наивное вычисление биномиального коэффициэнта требует обработки 501 ошибки:
@cache
def cnk(n, k):
if k < 0 or n < k:
return 0
if k == 0 or k == n:
return 1
return cnk(n - 1, k - 1) + cnk(n - 1, k)
print(cnk(1000, 500))
$ python cnk.py RecursionError, len(stack) 499 RecursionError, len(stack) 997 RecursionError, len(stack) 997 ... RecursionError, len(stack) 501 RecursionError, len(stack) 500 RecursionError, len(stack) 499 2702882409...9821216320
Не пытайтесь повторить
Хотя способ рабочий, не надо его использовать. Пока ваша программа не содержит ошибок, обёртка будет работать и радовать вас результатами. Если в программе есть ошибка с бесконечной рекурсией (вы ошиблись в описании условия завершения рекурсии или вызвали функцию с аргументами за пределами области определения), отладка превратится в неприятное занятие: программа будет зависать, исчерпывать память (список stack растёт неограниченно), компьютер будет тормозить из-за свопа памяти на диск пока процесс не завершится из-за нехватки памяти. У меня не всегда хватает терпения чтобы дождаться завершения процесса, иногда приходится перезагружать компьютер.
Другие
Рекурсию можно переписать на древовидную, но код получится ужасным. Так что если вы хотите чтобы это была именно рекурсия, проще всего заполнять кэш.
Если можно отказаться от рекурсии, то цикл решает проблему:
def f(n):
return sum(i + 1 for i in range(1, n + 1))
print(f(23023))
Ещё можно вспомнить формулу арифметической прогрессии и получить такой код:
def f(n):
return n * (n + 3) // 2
print(f(23023))