Ошибка рекурсивной функции Python: “максимальная глубина рекурсии превысила” [копируют]
Этот вопрос уже имеет ответ здесь:
Я решил проблему 10 из Euler Проекта со следующим кодом, который работает через грубую силу:
def isPrime(n):
for x in range(2, int(n**0.5)+1):
if n % x == 0:
return False
return True
def primeList(n):
primes = []
for i in range(2,n):
if isPrime(i):
primes.append(i)
return primes
def sumPrimes(primelist):
prime_sum = sum(primelist)
return prime_sum
print (sumPrimes(primeList(2000000)))
Три функции работают следующим образом:
- isPrime проверяет, является ли число началом;
- primeList возвращает список, содержащий ряд простых чисел для определенного диапазона с пределом 'n', и;
- sumPrimes подводит итог значений всех чисел в списке. (Эта последняя функция не необходима, но мне понравилась ясность ее, специально для новичка как я.)
Я затем записал новую функцию, primeListRec, который делает точно то же самое как primeList, чтобы помочь мне лучше понять рекурсию:
def primeListRec(i, n):
primes = []
#print i
if (i != n):
primes.extend(primeListRec(i+1,n))
if (isPrime(i)):
primes.append(i)
return primes
return primes
Вышеупомянутая рекурсивная функция работала, но только для очень маленьких значений, как '500'. Функция заставила мою программу отказывать, когда я вставил '1000'. И когда я вставил значение как '2 000', Python дал мне это:
RuntimeError: максимальная глубина рекурсии превышена.
Что я делал неправильно с моей рекурсивной функцией? Или есть ли некоторый особенный метод избежать предела рекурсии?
4 ответа
Рекурсия - не самый идиоматичный способ делать вещи в Python, поскольку в нем нет хвостовой рекурсии оптимизации, что делает непрактичным использование рекурсии в качестве замены итерации (даже если в вашем примере функция не является хвостовой рекурсией, это все равно не поможет). В принципе, это означает, что вы не должны использовать его для вещей, которые имеют сложность больше линейной, если вы ожидаете, что ваши входные данные будут большими, (тем не менее, это нормально для вещей, которые имеют логарифмическую глубину рекурсии, например, алгоритмы "разделяй и властвуй", как QuickSort).
Если вы хотите попробовать этот подход, используйте язык, более подходящий для функционального программирования, например, Lisp, Scheme, Haskell, OCaml и т.д.; или попробуйте Stackless Python, который имеет более широкие ограничения на использование стека, а также оптимизацию хвостовой рекурсии :-)
Кстати, хвостовой рекурсивный эквивалент вашей функции может быть таким:
def primeList(n, i=2, acc=None):
return i > n and (acc or []) or primeList(n, i+1, (acc or []) + (isPrime(i) and [i] or []))
Еще одно "кстати", вам не следует строить список, если вы используете его только для сложения значений.... Питонический способ решения 10-й проблемы проекта Эйлера таков:
print sum(n for n in xrange(2, 2000001) if all(n % i for i in xrange(2, int(n**0.5)+1)))
(ОК, возможно, разбить его на несколько строк было бы еще более питоническим, но я люблю однострочники ^_^)
Вы перебираете n чисел и выполняете рекурсию на каждом шаге. Поэтому предел рекурсии в Python определяет ваше максимальное входное число. Это явно нежелательно. Особенно потому, что проблемы Эйлера обычно имеют дело с довольно большими числами.
Я не эксперт по питону, но полагаю, вы достигли предела стека . В этом проблема рекурсии: это здорово, когда вам не нужно повторять много раз, но бесполезно, когда количество рекурсий становится даже умеренно большим.
Идеальная альтернатива - переписать алгоритм, чтобы вместо этого использовать итерацию.
Изменить: На самом деле, внимательно присмотревшись к вашей конкретной ошибке, вы можете обойти ее, изменив sys.getrecursionlimit . Но на этом вы пока не закончите. В конце концов вы получите исключение stackoverflow, которое вернет меня к исходной точке.
Как уже было сказано, для языков, которые не могут работать с глубокими стеками, лучше использовать итеративный подход. В частности, в вашем случае лучше всего изменить используемый алгоритм. Я предлагаю использовать Сито Эратосфена , чтобы найти список простых чисел. Это будет намного быстрее, чем ваша текущая программа.