Rekursionstiefe feststellen

[Monty Python]

Hallo,
ich habe ein Problem mit der Rekursion (wie schon so viele ...):
Ich habe eine Funktion, in der eine for-Schleife vorkommt und in dieser wird die Funktion wieder aufgerufen. Die for-Schleife soll nicht ausgeführt werden, wenn eine bestimmte Rekursionstiefe erreicht ist.

bis jetzt sieht es so aus:

Code: Alles auswählen

def abc():
    global zaehler
    if zaehler < len(liste):
        for liste[zaehler] in xrange(1,13):
            zaehler += 1
            abc()
    else:
        main()

Das Problem ist eindeutig der Zähler (zaehler), der bei einem beendeten Schleifendurchgang nicht verkleinert wird, also habe ich mich gefragt, ob man die Rekursionstiefe irgendwie feststellen lassen kann, das würde ich dann als Ersatz für den Zähler verwenden.

[BlackJack]

Du solltest grundsätzlich den Ansatz überdenken und die Rekursion sein lassen. Warum ist das keine Schleife über die `liste`. Und wo kommt die überhaupt her? Auf Modulebene sollte so etwas nicht rumliegen. Ebenso wie der `zaehler`. Wenn Du einen bei einer Rekursion mitführen willst, dann mach das als Argument, aber nicht ``global``. Das Schlüsselwort solltest Du am besten komplett vergessen.

Das `main()` sieht auch nach Rekursion aus, dass ist auf jeden Fall eine schlechte Idee. Oder die Funktion hat den falschen Namen.

[Monty Python]

ich hab's rausgefunden:

Code: Alles auswählen

def abc(zaehler):
    if zaehler+1 < len(liste):
        for liste[zaehler] in xrange(1,13):
            zaehler += 1
            abc(zaehler)
            zaehler -= 1
    else:
        main()

tja, so einfach ist das

[EyDu]

Du meinst sicher:

Code: Alles auswählen

def abc(zaehler):
    if zaehler+1 < len(liste):
        for liste[zaehler] in xrange(1,13):
            abc(zaehler+1)
    else:
        main()

Wie BlackJack aber schon sagte, deine Code sieht nicht besonders vertrauenserweckend aus.

[Monty Python]

nein, ich meinte:

Code: Alles auswählen

def abc(zaehler):
    if zaehler+1 < len(liste):
        for liste[zaehler] in xrange(1,13):
            zaehler += 1
            abc(zaehler)
            zaehler -= 1
    else:
        main()

(das ist schon ok so [deins geht auch, aber ich nehm meins {auch wenns mehr text ist}])

[name]

nein, ich meinte:

Code: Alles auswählen

def abc(zaehler):
    if zaehler+1 < len(liste):
        for liste[zaehler] in xrange(1,13):
            zaehler += 1
            abc(zaehler)
            zaehler -= 1
    else:
        main()

(das ist schon ok so [deins geht auch, aber ich nehm meins {auch wenns mehr text ist}])

Sinnloscode und Sinnlosrekursion ftw!

[Monty Python]

vor allem absolut sinnlos, wenns haargenau so funktioniert, wie's soll ...
ich weiß, dass rekursion nicht schön aussieht, aber wenns halt nur so geht, dann gehts halt nur so

[BlackJack]

@Monty Python: Rekursion sieht sehr schön aus, wenn man sie auf Probleme anwendet, die sich eleganter als Rekursion ausdrücken lassen als durch iterativen Code. Was Du da machst ist eine ziemlich hässliche Mischung, denn dass es ohne das erhöhen und verringern des Zählers geht, wurde ja gezeigt.

Ausserdem kann man *jede* Rekursion auch iterativ ausdrücken (und umgekehrt). In einer imperativen Sprache wie Python, die dazu in der Standardimplementierung bei der erlaubten Rekursionstiefe noch ein gewisses Handycap hat, ist eine Rekursion, die sich einfach vermeiden liesse, eine "Sinnlosrekursion" und unschön. Das ein Code *funktioniert* sagt nichts über dessen Eleganz oder die Sinnhaftigkeit der gewählten Umsetzung aus.

[Monty Python]

na dann machs mal iterativ, das würd ich jetzt gern mal sehen

(außerdem ging es mir nicht um eleganz in meinem programm, sondern darum, dass es "*funktioniert*")

[Leonidas]

na dann machs mal iterativ, das würd ich jetzt gern mal sehen

Was ist denn das Problem was du lösen willst?

[BlackJack]

Bitteschön, einmal iterativ:

Code: Alles auswählen

def abc(liste, n=13):
    length = len(liste)
    for i in xrange(n**length):
        for j in reversed(xrange(length)):
            i, liste[j] = divmod(i, n)

[bords0]

Bitteschön, einmal iterativ:

Code: Alles auswählen

def abc(liste, n=13):
    length = len(liste)
    for i in xrange(n**length):
        for j in reversed(xrange(length)):
            i, liste[j] = divmod(i, n)

Das macht aber was anderes, z.B. wird nicht mal main() aufgerufen. Und die 0 kann auch in liste[j] auftauchen. Und das letzte Element von liste wird überschrieben, obwohl es erhalten bleiben soll.

[BlackJack]

@bords0: Au weia, dass ist ja jetzt etwas *tootaaal* anderes.

Code: Alles auswählen

def abc(liste, n=12):
    length = len(liste) - 1
    for i in xrange(n**length):
        for j in reversed(xrange(length)):
            i, k = divmod(i, n)
            liste[j] = k + 1

Und ich weigere mich `main()` am Ende "aufzurufen", weil ich befürchte, dass das als "Sprung" missbraucht wird, und das wäre total daneben. Das wäre nicht einmal mehr eine Stilfrage, sondern ein Speicherleck und damit schlicht ein Programmierfehler.

Ausserdem bin ich mir gar nicht so sicher, dass das letzte Element der Liste erhalten bleiben sollte, oder ob das nicht einfach nur ein Fehler in dem gezeigten Beispiel war. Denn für echten Quelltext ist das ein bisschen zu sinnlos.

[bords0]

@bords0: Au weia, dass ist ja jetzt etwas *tootaaal* anderes.

Code: Alles auswählen

def abc(liste, n=12):
    length = len(liste) - 1
    for i in xrange(n**length):
        for j in reversed(xrange(length)):
            i, k = divmod(i, n)
            liste[j] = k + 1

Und ich weigere mich `main()` am Ende "aufzurufen", weil ich befürchte, dass das als "Sprung" missbraucht wird, und das wäre total daneben. Das wäre nicht einmal mehr eine Stilfrage, sondern ein Speicherleck und damit schlicht ein Programmierfehler.

Ausserdem bin ich mir gar nicht so sicher, dass das letzte Element der Liste erhalten bleiben sollte, oder ob das nicht einfach nur ein Fehler in dem gezeigten Beispiel war. Denn für echten Quelltext ist das ein bisschen zu sinnlos.

Für main() (schlechter Name) stelle ich mir so etwas vor wie

Code: Alles auswählen

def main():
    print sum(liste), liste.count(liste[-1])

Das Hauptprogramm kann ja nicht in main stehen, denn main wird ja für jede Belegung von liste aufgerufen werden (nicht "am Ende"). Der übliche Fehler, auf den du wohl anspielst, wäre aber, am Ende der Funktion das Hauptprogramm aufzurufen und nie wieder zurückzukehren. Dann hätte Monty Python aber gerade kein Problem mit dem Wiederheruntersetzen von zaehler gehabt.

Irgendwas wird man am Ende deiner äußeren Schleife noch aufrufen wollen (bei Monty Python: main()), sonst könnte man es ja gleich so schreiben:

Code: Alles auswählen

def abc(liste, n=12):
    liste[:-1] = [n] * (len(liste) - 1)

Die Funktionalität des Originals, die ersten zaehler Positionen von liste unverändert zu lassen, fehlt noch bei deiner Version. Klar kannst du das noch einbauen - darum geht es nicht.

Ich will nur zum Ausdruck bringen, dass es in diesem Beispiel keineswegs trivial ist, die Funktionalität exakt iterativ nachzubauen. Eigentlich bin ich sogar der Meinung, dass Rekursion hier ziemlich sinnvoll ist. Die Rekursive Version ist lesbarer und bietet mehr Funktionalität. (Vermutlich ist sie auch schneller - aber möglicherweise könnte man eine iterative Version schreiben, die noch schneller ist.)

[BlackVivi]

Rekursion ist nur ganz selten schneller. Du darfst nicht vergessen, dass jeder Funktionsaufruf auf einen Funktionsstack gepackt wird und sowas. Ein Funktionsaufruf ist keine triviale Angelegenheit - eine Schleife in Relation dazu schon.

Selbst Sprachen die stark optimiert sind wie C oder Java sind nicht sonderlich effektiv wenn es um Rekursion geht. (Tails-Recursion mal abgesehen, aber die wird sowieso in eine iterative Variante vom Compiler umgewandelt, oder? Nicht sonderlich sicher)

Python hat noch ein größeres Problem dabei, weil dort Rekursion halt auch ein gezwungenes Ende hat, ein Rekursionslimit. Außerdem... Rekursion hat auch andere Nachteile. Die Komplexität von Rekursion lässt sich oft nicht einfach ermitteln, jetzt in dem Beispiel nicht unbedingt, aber ich meine allgemein.

Natürlich ist Rekursion insbesondere bei mathematischen Problemen viel schöner. Man stelle einfach mal das trivialbeispiel Fakultät vor. Das sieht rekursiv schon schöner als iterativ...

[Leonidas]

Selbst Sprachen die stark optimiert sind wie C oder Java sind nicht sonderlich effektiv wenn es um Rekursion geht. (Tails-Recursion mal abgesehen, aber die wird sowieso in eine iterative Variante vom Compiler umgewandelt, oder? Nicht sonderlich sicher)

Warum sollte TCO unsicher sein? Natürlich kann das nur Endrekursion optimieren, aber das steht ja schon im Namen.
Außerdem haben weder C noch Java TCO, also stößt man da durchaus auch an ein Limit irgendwann.

[BlackJack]

@bords0: Was fehlt jetzt noch bei meiner Version? Das letzte Element bleibt beim Original unverändert, und bei mir jetzt auch wegen dem ``- 1`` in der zweiten Zeile der Funktion.

Und letztendlich fand ich es schon relativ trivial die Funktionalität iterativ zu schreiben. Verständlicher finde ich es auch, weil man sich jetzt den Rekursionsabstieg zu Laufzeit nicht mehr vorstellen muss, und wie jeder einzelne rekursive Aufruf zum Ergebnis beiträgt.

Äusserst unglücklich finde ich übrigens auch noch dass auf eine globale Liste zugegriffen wird. Für sauberen, verständlichen Code sollte man das auch vermeiden.

Und falls man Python >=2.6 einsetzt, sollte man sich sowieso überlegen, ob man `itertools.combinations()` umbedingt selber noch einmal erfinden möchte.

[Defnull]

Und ich weigere mich `main()` am Ende "aufzurufen", weil ich befürchte, dass das als "Sprung" missbraucht wird, und das wäre total daneben. Das wäre nicht einmal mehr eine Stilfrage, sondern ein Speicherleck und damit schlicht ein Programmierfehler.

Kann mir das mal jemand erklären? Warum ist das ein Sprung (one way) und kein normaler Aufruf (two-way), wie sonst? Wie kann man mit einem Funktionsaufruf Speicherlecks erzeugen? Vor allem bei Python?

[str1442]

BlackJack meint damit (vermutlich ), daß die Funktionen so angelegt sind, das der Aufruf einer bestimmten Funktion (hier der main() Funktion) niemals zurückkehren soll und somit als eine Art "Sprung" dient. Irgendwo tief in den einzelnen "Sprung" Funktionen wird das Programm dann "hart" (mittels sys.exit() oder SystemExit Exception anstatt das Programm "auslaufen" zu lassen) beendet. Das Speicherleck entsteht dann dadurch, das die main() aufrufenden Funktionen niemals aus dem Callstack entfernt werden. In etwa sowas:

Code: Alles auswählen

def sprung1():
    # do something

    # if bla:
    main(0)

def sprung2():
    # ...
    main(1)

def main(flag):
    print "Main"

    if flag == 0:
        raise SystemExit(0)
    elif flag == 1:
        sprung1()
    else:
        sprung2()

if __name__ == "__main__":
    main(2)

Ausgabe:

Code: Alles auswählen

Main
Main
Main

EDIT: Das Programm wird natürlich "hart" beendet und nicht hart.

[lunar]

Selbst Sprachen die stark optimiert sind wie C oder Java sind nicht sonderlich effektiv wenn es um Rekursion geht. (Tails-Recursion mal abgesehen, aber die wird sowieso in eine iterative Variante vom Compiler umgewandelt, oder? Nicht sonderlich sicher)

Warum sollte TCO unsicher sein?

Ich glaube eher, BlackVivi wollte sagen, dass er sich nicht sicher sei, ob Endrekursionen in Iterationen umgewandelt werden.

Außerdem haben weder C [...] TCO, also stößt man da durchaus auch an ein Limit irgendwann.

Was meinst du denn damit? Moderne C-Compiler sollten Endrekursionen doch zu Iterationen optimieren, oder etwa nicht?