Seite 1 von 1

Verfasst: Samstag 26. Januar 2008, 11:10
von Leonidas
BlackJack hat geschrieben: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 :D

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

Verfasst: Samstag 26. Januar 2008, 12:31
von sma
Leonidas hat geschrieben: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

Verfasst: Samstag 26. Januar 2008, 12:52
von 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.

Verfasst: Samstag 26. Januar 2008, 13:00
von Leonidas
BlackJack hat geschrieben:@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.