Ошибка рекурсивной функции Python: "максимальная глубина рекурсии"

Я решил задачу 10 Project 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". И когда я ввел значение типа "2000", Python дал мне это:

RuntimeError: максимальная глубина рекурсии.

Что я сделал неправильно с моей рекурсивной функцией? Или существует какой-то конкретный способ избежать ограничения рекурсии?

Ответ 1

Рекурсия не является самым идиоматическим способом делать вещи в 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 []))

Другой "кстати", вы не должны создавать список, если используете его только для того, чтобы добавить значения... Пути Pythonic для решения 10-й проблемы Project Euler:

print sum(n for n in xrange(2, 2000001) if all(n % i for i in xrange(2, int(n**0.5)+1)))

(ОК, возможно, расщепление его в разных строках было бы еще более питоническим, но я люблю один лайнер ^ _ ^)

Ответ 2

Ну, я не эксперт по python, но полагаю, вы попали в stack limit. Что проблема с рекурсией, это здорово, когда вам не нужно многократно переписываться, но не хорошо, когда количество рекурсий становится даже умеренно большим.

Идеальная альтернатива заключается в том, чтобы переписать ваш алгоритм для использования итерации.

Изменить: На самом деле, приблизившись к вашей конкретной ошибке, вы можете пройти мимо нее, изменив sys.getrecursionlimit. Это займет только вас. В конце концов вы получите исключение stackoverflow, которое вернет меня к исходной точке.

Ответ 3

Вы повторяете n чисел и повторяетесь на каждом шаге. Поэтому предел рекурсии Python определяет ваш максимальный номер входа. Это явно нежелательно. Тем более, что проблемы Эйлера обычно касаются довольно больших чисел.

Ответ 4

Как уже говорилось, на языках, которые не могут справиться с глубокими стеками, лучше использовать итеративный подход. В вашем случае, в частности, лучше всего изменить используемый алгоритм. Я предлагаю использовать Сито Эратосфена, чтобы найти список простых чисел. Это будет намного быстрее, чем ваша текущая программа.

Ответ 5

Вы можете сделать это грязным способом:

try: function() except: function()