Python rekursiver Funktionsfehler: "maximale Rekursionstiefe überschritten"

Ich löste Problem 10 des Projektes Euler mit dem folgenden Code, der durch rohe Gewalt arbeitet:

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 mit einem Satz von Primzahlen für einen bestimmten Bereich mit Limit 'n' zurück und;
  3. SumPrimes fasst die Werte aller Zahlen in einer Liste zusammen. (Diese letzte Funktion ist nicht nötig, aber ich mochte die Klarheit davon, besonders für einen Anfänger wie mich.)

Ich schrieb dann eine neue Funktion, primeListRec , die genau das Gleiche wie primeList macht , um mir besser zu helfen, Rekursion 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, aber nur für sehr kleine Werte, wie '500'. Die Funktion hat mein Programm zum Absturz gebracht, als ich in '1000' stelle. Und wenn ich einen Wert wie '2000' einlegte, gab mir Python:

RuntimeError: maximale Rekursionstiefe überschritten .

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

5 Solutions collect form web for “Python rekursiver Funktionsfehler: "maximale Rekursionstiefe überschritten"”

Rekursion ist nicht die idiomatischste Art, Dinge in Python zu tun, da es keine Schwanzrekursionsoptimierung hat, wodurch die Verwendung von Rekursion als Ersatz für Iteration unpraktisch wird (auch wenn in Ihrem Beispiel die Funktion nicht schwanzrekursiv ist, 'T helfen sowieso). Grundsätzlich bedeutet das, dass du es nicht für Dinge verwenden solltest, die eine Komplexität haben, die größer als linear ist, wenn du erwartest, dass deine Eingaben groß sind (immer noch ist es ok, Dinge zu tun, die eine logarithmische Rekursionstiefe haben, wie Trenn- und Eroberungsalgorithmen als QuickSort ).

Wenn du diesen Ansatz ausprobieren möchtest, benutze eine Sprache, die besser geeignet ist, um funktionale Programmierung zu machen, wie Lisp, Scheme, Haskell, OCaml usw .; Oder geben Sie einen Versuch, Stackless Python, das hat breitere Grenzen in Stack-Nutzung und hat auch Schwanz Rekursion Optimierung 🙂

Übrigens könnte ein schwanzrekursives Äquivalent Ihrer Funktion sein:

 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 anderer "by the way", solltest du nicht eine Liste konstruieren, wenn du es benutzt hast, um nur die Werte zu addieren … Die Pythonische Möglichkeit, das 10. Problem von Project Euler zu lösen, ist:

 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 spalte es in verschiedenen Zeilen wäre noch mehr Pythonic, aber ich liebe ein Liner ^ _ ^)

Nun, ich bin kein Python-Experte, aber ich vermute, Sie haben die Stack- Grenze getroffen. Das ist das Problem mit der Rekursion, es ist toll, wenn man nicht sehr oft wiederkehren muss, aber nicht gut, wenn die Anzahl der Rekursionen sogar mäßig groß wird.

Die ideale Alternative ist, Ihren Algorithmus umzuschreiben, um stattdessen Iteration zu verwenden.

Bearbeiten: Tatsächlich sahen Sie näher an Ihren spezifischen Fehler, den Sie an ihm vorbeigehen können, indem Sie sys.getrecursionlimit ändern. Das bringt dich nur so weit. Irgendwann bekommst du eine Stackoverflow-Ausnahme, die mich zurück zu meinem ursprünglichen Punkt bringt.

Du isst über n Zahlen und wiederholt bei jedem Schritt. Deshalb definiert die Rekursionsgrenze von Python Ihre maximale Eingangsnummer. Das ist offensichtlich unerwünscht Vor allem, weil die Euler-Probleme typischerweise mit ziemlich großen Zahlen umgehen.

Wie schon gesagt, in Sprachen, die nicht mit tiefen Stacks umgehen können, ist es besser, einen iterativen Ansatz zu machen. In Ihrem Fall ist es am besten, den verwendeten Algorithmus zu ändern. Ich schlage vor, das Sieb von Eratosthenes zu benutzen, um die Liste der Primzahlen zu finden. Es wird ganz schneller sein als dein aktuelles Programm.

Sie können es in einer schmutzigen Weise tun:

 try: function() except: function() 
  • Ich versuche, eine Funktion zu machen, die max aus verschachtelter Liste zurückgibt?
  • Warum gibt meine rekursive Funktion keine?
  • Finde alle Index mit Rekursion
  • Lösen von vollständig versteckten Ausdrücken mit Rekursion
  • Das max-Element in einer Sequenz mit Rekursion zu finden
  • Merkwürdiges Rekursionsverhalten in Python
  • Rekursionsfunktion funktioniert nicht richtig
  • Rekursiv finden Sie alle Münzkombinationen, die eine bestimmte Menge produzieren
  • Python Recursive Funktion für Collatz Conjecture
  • Python-Funktion kehrt nach Rekursion nicht zurück
  • Rekursive Funktion gibt keine in Python zurück [doppelte]
  • Python ist die beste Programmiersprache der Welt.