wake-up-neo.com

Rekursiver Funktionsfehler von Python: "maximale Rekursionstiefe überschritten"

Ich habe Problem 10 von Project Euler mit dem folgenden Code gelöst, der durch Brute Force funktioniert:

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)))

Die drei Funktionen funktionieren wie folgt: 

  1. isPrime prüft, ob eine Zahl eine Primzahl ist;
  2. primeList gibt eine Liste zurück, die eine Menge von Primzahlen für einen bestimmten Bereich mit Limit 'n' enthält; 
  3. sumPrimes summiert die Werte aller Zahlen in einer Liste. (Diese letzte Funktion ist nicht erforderlich, aber ich mag die Klarheit, besonders für einen Anfänger wie mich.)

Ich schrieb dann eine neue Funktion, primeListRec , die genau dasselbe tut wie primeList , um die Rekursion besser zu verstehen:

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

Die obige rekursive Funktion funktionierte nur für sehr kleine Werte wie '500'. Die Funktion hat mein Programm zum Absturz gebracht, wenn ich '1000' eingebe. Und wenn ich einen Wert wie '2000' eingebe, gab mir Python folgendes: 

RuntimeError: maximale Rekursionstiefe überschritten .

Was habe ich mit meiner rekursiven Funktion falsch gemacht? Oder gibt es einen bestimmten Weg, um ein Rekursionslimit zu vermeiden? 

18
anonnoir

Rekursion ist nicht der idiomatischste Weg, Dinge in Python zu tun, da es keine tail reursion -optimierung gibt, was die Rekursion als Ersatz für die Iteration unpraktisch macht (selbst wenn die Funktion in Ihrem Beispiel kein tail ist. rekursiv, das würde sowieso nicht helfen). Im Grunde bedeutet dies, dass Sie es nicht für Dinge verwenden sollten, deren Komplexität größer als die lineare ist, wenn Sie erwarten, dass Ihre Eingaben groß sind (es ist jedoch in Ordnung, wenn Sie Dinge mit einer logarithmischen Rekursionstiefe ausführen, wie beispielsweise Algorithmen zum Teilen und Erobern als QuickSort) ).

Wenn Sie diesen Ansatz ausprobieren möchten, verwenden Sie eine Sprache, die besser für die Funktionsprogrammierung geeignet ist, z. B. LISP, Scheme, Haskell, OCaml usw .; oder versuchen Sie es mit Stackless Python, das hat breitere Grenzen bei der Stack-Nutzung und auch die Optimierung der Schwanzrekursion :-)

Übrigens könnte ein rekursives Äquivalent Ihrer Funktion lauten:

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 []))

Ein weiteres "Übriges", sollten Sie keine Liste erstellen, wenn Sie nur die Werte summieren ... Der Pythonic-Weg, um das 10. Problem von Project Euler zu lösen, lautet:

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

(OK, vielleicht wäre das Aufteilen in verschiedene Zeilen noch mehr Pythonic, aber ich liebe einen Liner ^ _ ^)

26
fortran

Wie bereits gesagt, ist es in Sprachen, die mit Deep Stacks nicht umgehen können, eine iterative Vorgehensweise. In Ihrem Fall ist es am besten, den verwendeten Algorithmus zu ändern. Ich schlage vor, das Sieat von Eratosthenes zu verwenden, um die Liste der Primzahlen zu finden. Es wird ziemlich schneller sein als Ihr aktuelles Programm.

1
Thiago Chaves

Nun, ich bin kein Python-Experte, aber ich gehe davon aus, dass Sie das Stack Limit erreicht haben. Das ist das Problem der Rekursion, es ist großartig, wenn Sie nicht oft rekursieren müssen, aber nicht gut, wenn die Anzahl der Rekursionen nur mäßig groß wird.

Die ideale Alternative ist, Ihren Algorithmus so umzuschreiben, dass er stattdessen die Iteration verwendet.

Edit: Wenn Sie Ihren spezifischen Fehler genauer betrachtet haben, können Sie ihn umgehen, indem Sie sys.getrecursionlimit ändern. Das bringt dich allerdings nur so weit. Irgendwann erhalten Sie eine Stackoverflow-Ausnahme, die mich wieder an meinen ursprünglichen Punkt bringt.

1
Adrian

Sie durchlaufen n Zahlen und rekursieren bei jedem Schritt. Daher definiert das Rekursionslimit von Python Ihre maximale Eingabezahl. Das ist natürlich unerwünscht. Vor allem, weil die Euler-Probleme in der Regel mit ziemlich großen Zahlen zu tun haben.

0
Johannes Charra