Frage zur Rekursion!

[Leonidas]

Ist dann zwar nicht endrekursiv, aber effizient ist eine rekursive Lösung in Python ja sowieso nicht, wenn man als Alternative etwas einfaches, iteratives machen kann.

Ich warte nur noch auf eine Python-Implementation die Endrekursiv ist Habe letztens zum Spaß mal ``map()`` rekursiv implementiert, nachdem ich das in ML gesehen habe

Rekursion kann im Kopfweh tun, aber Fibonacci ist auf jeden Fall recht simpel hinzubekommen. Vermutlich sogar einfacher als iterativ.

[sma]

Ich warte nur noch auf eine Python-Implementation die Endrekursiv ist :)

Müsste Stackless das nicht sein? Ansonsten biete ich dir meinen Python-Interpreter als Grundlage an ;)

Ich merke mir dort keine Funktionsobjekte im Frame, aber unter der Annahme, dass es reicht, die Identität von Code-Objekten zu vergleichen, müsste folgendes in `CALL_FUNCTION` ausreichen, um das Erzeugen neuer Frame-Objekte (und damit den rekursiven Abstieg) zu unterdrücken:

Code: Alles auswählen

if func.func_code is self.f_code:
    self.f_locals = f_locals(func, args)
    self.f_lasti = 0
    self.f_stack = []
    return self
return Frame(self, func.func_code, f_locals(func, args)) # todo add kw

Stefan

[BlackJack]

@Leonidas: Du meinst wohl eine Python-Implementierung die Endrekursion erkennt und "tail call optimization" betreibt, also die Rekursion in eine Schleife umwandelt. Dann bleiben immer noch Funktionen die nicht endrekursiv sind und die man auch nicht so einfach in diese Form bringen kann.

[Leonidas]

@Leonidas: Du meinst wohl eine Python-Implementierung die Endrekursion erkennt und "tail call optimization" betreibt, also die Rekursion in eine Schleife umwandelt.

Ja, habe das etwas schlampig ausgedrückt.