Das deutsche Python-Forum

Hallo!

Ich stoße seit einigen Tagen immer wieder an das Rekursionslimit.
Bin momentan hauptsächlich mit esoterischen Sprachen beschäftigt, wo oft
ein Code-Fragment aus dem Netz in Sprache XXX unter Unständen
stark auf Rekursion setzt. Das übertrage ich dann 1:1 nach Python
und stoße eben bald ans Limit.

In vielen Fällen ist es recht einfach, eine Schleife aus der Funktion
zu machen, aber manchmal ist es eher schwierig.
Möchte euch bitten, mir bei der Umgehung zu helfen.

Folgende Möglichkeiten fallen mir ein:

1.) Neu compilen und das Rekursionslimit hinaufsetzen.
(ist aber eigentlich keine Lösung)

2.) Es gibt irgendwo ein Modul, daß einfachen Python-Code nach C
überträgt. Könnte klappen, da in C der Stack nicht so schnell ausgeht.
Ich hätte aber lieber "richtiges" Python.

3.) Ich könnte endrekursive Funktionen suchen und mit der üblichen
Optimierung auf O(1) Speicherverbrauch bringen. Das wäre schon was!

4.) Ich könnte Python patchen. Keine Ahnung, ob das Rekursionslimit
wirklich wichtig ist, aber ich denke nicht, daß es ganz umsonst da ist.

4. wäre schrecklich, und wahrscheinlich zu viel Arbeit.
Mit 2. habe ich keine Erfahrung, ich wäre über Hinweise dankbar.
Allerdings müßte man immer neu compilen, wenn man C-Code erzeugt.

3. wäre sehr toll. Meine Frage zu 3:
Wenn ich solche "metasyntaktischen" Umformungen programmieren will, wo setze ich am besten an?
Wahrscheinlich eher am Syntax-Baum als am
Quelltext. Ist das sehr kompliziert?

Noch ein Beispiel zu 3:

Code: Alles auswählen

def fak(n, a=1):
    if n == 1:
        return a
    else:
        return fak(n - 1, n * a)

# wird zu

def fak(n, a=1):     # a bleibt der Einfachheit halber stehen
    args = n, a
    while not args[0] == 1:
        args = args[0] - 1, args[0] * args[1]
    return args[1]

Ich hoffe, das war halbwegs verständlich.
Danke schon jetzt!

Endrekursion ist immer einfach mit einer while Schleife Machbar und das sollt man auch tun.
Bei allen anderen Fällen kann man den Algorithmus umformen in einen iterativen, was allerdings oft nicht trivial ist.

Code: Alles auswählen

import sys

sys.setrecursionlimit(2000)

Das sollte für einfache Fälle reichen.
Die schlimmen Fälle der Rekursion sind die, die in O(n²) oder schlimmer laufen, aber da ist eben der Algo schuld

fak(n) würde man übrigens so schreiben:

Code: Alles auswählen

def fak(n):
    acc = 1
    while n:
        acc *= n
        n -= 1
    return acc 

print fak(6)

import operator

def fak2(n):
    return reduce(operator.mul, xrange(1,n+1))

print fak2(6)

audax hat geschrieben:
Code: Alles auswählen
import operator

def fak2(n):
    return reduce(operator.mul, xrange(1,n+1))

print fak2(6)

Lieber:

Code: Alles auswählen

import operator

def fak2(n):
    return reduce(operator.mul, xrange(1,n+1)) if n else 1

print fak2(0)

sys.setrecursionlimit(2000)

Und ich hab gedacht, das ist hard-compiled... RTFM windner!

Endrekursion ist immer einfach mit einer while Schleife Machbar und das sollt man auch tun.

Verstehe ich, aber es wäre schon ein kleiner Sieg, wenn das von selbst
gehen würde.

Ich weiß, daß man fak() schöner schreiben kann, wollte aber ein
Beispiel bringen, das man schematisch recht einfach aus der
endrekursiven Variante erzeugen kann.

Die schlimmen Fälle der Rekursion sind die, die in O(n²) oder schlimmer laufen, aber da ist eben der Algo schuld

Genau das sind die Fälle von denen ich spreche. ZB eval und
apply. Wird unter Umständen auch mit 2000 bald knapp.
Was tut man da?

windner hat geschrieben:Genau das sind die Fälle von denen ich spreche. ZB eval und apply. Wird unter Umständen auch mit 2000 bald knapp.
Was tut man da?

Den Code so umschreiben, dass weder apply() -

- (deprecated seit 2.3!) noch eval() -

- vorkommen!

Darii hat geschrieben:
audax hat geschrieben:
Code: Alles auswählen
import operator

def fak2(n):
    return reduce(operator.mul, xrange(1,n+1))

print fak2(6)
Lieber:
Code: Alles auswählen
import operator

def fak2(n):
    return reduce(operator.mul, xrange(1,n+1)) if n else 1

print fak2(0)

Mein fak(0) gibt auch 1.
Für negative Zahlen:

Code: Alles auswählen

def fak2(n):
    if n<0:
        raise ValueError("Negative fak")
    return reduce(operator.mul, xrange(1,n+1))

@windner: Wenn Du in Python programmierst, solltest Du halt auch wirklich in Python programmieren und nicht versuchen die Idiome einer anderen Sprache mit Gewalt an den Python-Interpreter zu verfüttern. Gegen statt mit der jeweiligen Sprache zu programmieren ist einfach keine gute Idee.

Das Rekursionslimit setzen ist IMHO eine eher schlechte Idee wenn man die Möglichkeit hat den Algorithmus iterativ zu schreiben - was bei Python sowieso zu bevorzugen ist.

Da gibt es doch was

audax hat geschrieben:Mein fak(0) gibt auch 1.

Ich kriege da

Code: Alles auswählen

TypeError: reduce() of empty sequence with no initial value

Elegantter wär aber wohl

Code: Alles auswählen

def fak2(n): 
    if n<0: 
        raise ValueError("Negative fak") 
    return reduce(operator.mul, xrange(1,n+1), 1)

Darii hat geschrieben:
audax hat geschrieben:Mein fak(0) gibt auch 1.
Ich kriege da
Code: Alles auswählen
TypeError: reduce() of empty sequence with no initial value

Hast recht, hab mich vertan.

Bin momentan hauptsächlich mit esoterischen Sprachen beschäftigt

http://de.wikipedia.org/wiki/Sanskrit

SCNR

Das deutsche Python-Forum

Rekursions-Limit umgehen

Rekursions-Limit umgehen