Rekursions-Limit umgehen

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
windner
User
Beiträge: 76
Registriert: Freitag 19. Oktober 2007, 11:25

Rekursions-Limit umgehen

Beitragvon windner » Mittwoch 17. Dezember 2008, 13:36

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!
audax
User
Beiträge: 830
Registriert: Mittwoch 19. Dezember 2007, 10:38

Beitragvon audax » Mittwoch 17. Dezember 2008, 13:51

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)
Darii
User
Beiträge: 1177
Registriert: Donnerstag 29. November 2007, 17:02

Beitragvon Darii » Mittwoch 17. Dezember 2008, 14:09

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)
windner
User
Beiträge: 76
Registriert: Freitag 19. Oktober 2007, 11:25

Beitragvon windner » Mittwoch 17. Dezember 2008, 14:45

sys.setrecursionlimit(2000)

:oops:
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?
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

Beitragvon numerix » Mittwoch 17. Dezember 2008, 14:55

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() - :shock: - (deprecated seit 2.3!) noch eval() - :? - vorkommen!
audax
User
Beiträge: 830
Registriert: Mittwoch 19. Dezember 2007, 10:38

Beitragvon audax » Mittwoch 17. Dezember 2008, 15:10

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

Beitragvon BlackJack » Mittwoch 17. Dezember 2008, 15:11

@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.
Benutzeravatar
Leonidas
Administrator
Beiträge: 16023
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Beitragvon Leonidas » Mittwoch 17. Dezember 2008, 15:12

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.
My god, it's full of CARs! | Leonidasvoice vs Modvoice
DasIch
User
Beiträge: 2423
Registriert: Montag 19. Mai 2008, 04:21
Wohnort: Berlin

Beitragvon DasIch » Mittwoch 17. Dezember 2008, 15:33

Da gibt es doch was ;)
Darii
User
Beiträge: 1177
Registriert: Donnerstag 29. November 2007, 17:02

Beitragvon Darii » Mittwoch 17. Dezember 2008, 19:14

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)
audax
User
Beiträge: 830
Registriert: Mittwoch 19. Dezember 2007, 10:38

Beitragvon audax » Mittwoch 17. Dezember 2008, 19:53

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.
abgdf

Beitragvon abgdf » Mittwoch 17. Dezember 2008, 20:42

Bin momentan hauptsächlich mit esoterischen Sprachen beschäftigt

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

SCNR

Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder