Frage zur Rekursion!

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

Beitragvon Leonidas » Samstag 26. Januar 2008, 11:10

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.
My god, it's full of CARs! | Leonidasvoice vs Modvoice
sma
User
Beiträge: 3018
Registriert: Montag 19. November 2007, 19:57
Wohnort: Kiel

Beitragvon sma » Samstag 26. Januar 2008, 12:31

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
BlackJack

Beitragvon BlackJack » Samstag 26. Januar 2008, 12:52

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

Beitragvon Leonidas » Samstag 26. Januar 2008, 13:00

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.
My god, it's full of CARs! | Leonidasvoice vs Modvoice

Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder