Rekursionstiefe feststellen

[Leonidas]

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?

Scheme-Implementationen sind verpflichtet TCO anzubieten um sich Scheme zu nennen, das ist bei C nicht der Fall, also kann man nicht einfach so davon ausgehen dass Endrekursion optimiert wird. Damit ist TCO Teil der Sprache in Scheme aber nicht in C, wo es eben Implementationsabhängig ist.

[BlackJack]

@lunar: C Compiler können TCO vielleicht machen, es gibt aber von Seiten der Sprachdefinition keinerlei Garantien.

[BlackVivi]

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.

Nein, nein, nein, nein! Ich meinte, dass ICH mir nicht sicher bin, ob das gemacht wird oO' So ein "Ohne Gewähr!"... Will keine Halbwahrheiten erzählen, ohne es 100% zu wissen ._.

Verzeih, undeutlich ausgedrückt!

[bords0]

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.

Das war aber nicht der Fall, denn
a) main() wurde für jede Belegung von liste aufgerufen
b) es gäbe kein Problem mit dem Zähler, wenn main() nicht zurückkehren würde
c) das Problem würde nicht durch Herabsetzen des Zählers gelöst werden können

Der Name main war IMO einfach nur sehr unkonventionell (und daher schlecht).

[bords0]

@bords0: Was fehlt jetzt noch bei meiner Version?

Man kann die Originalversion z.B. so aufrufen:

Code: Alles auswählen

abc(3)

Dann bleiben liste[0], liste[1] und liste[2] unverändert. Das kann deine Version nicht.

Und letztendlich fand ich es schon relativ trivial die Funktionalität iterativ zu schreiben.

Zu lesen finde ich es aber schwieriger. Sind die -1en immer richtig? Passen reverse, Schleifenanzahl und Indizierung zusammen?

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

Allerdings! (Unabhängig von rekursiv/iterativ).

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

Vielleicht lernt der OP bei der ganzen Diskussion ja wenigstens itertools besser kennen, dann hat sich der Thread doch noch gelohnt

[Monty Python]

was ich machen will/wollte (wie auch immer) ist/war: in einer beliebig langen liste sollen alle möglichen kombinationen durchprobiert werden, bei denen ein element in der liste eine zahl von 1 bis 12 sein kann. weil das jetzt blöd ausgedrückt war, hier noch beispiele:

länge der liste = 1:
liste:
[1]
[2]
...
[11]
[12]
länge der liste = 2:
liste:
[1,1]
[1,2]
...
[1,11]
[1,12]
[2,1]
...
[12,12]
länge der liste = 3:
[1,1,1]
[1,1,2]
...
[12,12,12]
und so weiter

und bei jeder neuen kombination soll main() aufgerufen werden

[bords0]

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.

Aber die vorgestellte iterative Version macht ja mehr Funktionsaufrufe (xrange, reversed und vor allem divmod). Sie ist auch langsamer, sogar als die IMHO schlecht geschriebene Version des OP. Sie ruft sogar main() auf, was Blackjack "wegoptimiert" hat. abc2 ist dann Blackjacks Version. abc3 ist eine rekursive Version, leicht optimiert, ohne main():

Code: Alles auswählen

from timeit import Timer
setup = """liste = range(5)

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

def abc2(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

def abc3(liste, zaehler, length):
    if zaehler < length:
        for liste[zaehler] in xrange(1, 13):
            abc3(liste, zaehler + 1, length)

"""
print Timer("abc(0)", setup=setup).timeit(100)
print Timer("abc2(liste)", setup=setup).timeit(100)
print Timer("abc3(liste, 0, len(liste) - 1)", setup=setup).timeit(100)

ergibt bei mir

Code: Alles auswählen

2.14144395447
8.58113614999
1.32978150854

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

Argh! Fakultät doch nicht! Überhaupt nicht schöner!

[BlackVivi]

Natürlich sieht Fakultät rekursiv schöner aus als iterativ o_o Vielleicht liegt das ein bisschen im Auge des Betrachters, aber normalerweise....

[BlackJack]

@bords0: Tja, der letzte Beitrag vom OP ist der Grund, warum ich bei meiner ersten Implementierung nicht so ganz auf die Feinheiten eingegangen bin. Dachte mir schon dass das "Original" fehlerhaft war.

Bei Deiner letzten Lösung gefällt mir die API nicht. Das ist zu sehr auf "optimieren" getrimmt. Dem Aufrufer als drittes Argument "Länge der Liste - 1" aufzubürden finde ich nicht gut. Ich würde es dann eher so schreiben:

Code: Alles auswählen

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

Wobei mich dieses "Mikrobenchmarking" nicht überzeugt, denn alleine der Aufruf einer Funktion, die nichts tut, aus diesem Konstrukt heraus schlägt bei mir bei `abc4` ca. 20% drauf. Wenn da auch noch irgend etwas sinnvolles passiert, bleibt die Frage wieviel, oder auch wie wenig, das zur Gesamtzeit beiträgt.

[ms4py]

Zu was gibts itertools, damit braucht keiner Rekursion.

Code: Alles auswählen

from timeit import Timer
setup = """liste = range(5) 
from itertools import product
        
def main(): pass 

def abc3(liste, zaehler, length): 
    if zaehler < length: 
        for liste[zaehler] in xrange(1, 13): 
            abc3(liste, zaehler + 1, length)
            main()

def abc5(length):
    for liste in product(range(1,13), repeat=length):
        main()

""" 
print Timer("abc3(liste, 0, len(liste) - 1)", setup=setup).timeit(100)
print Timer("abc5(4)", setup=setup).timeit(100)

Code: Alles auswählen

1.95250013462
0.961583572211

Hinweis: Für Python < 2.6 steht eine mögliche Implementierung in der Doku http://docs.python.org/library/itertool ... ls.product