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.
Antworten
söan
User
Beiträge: 2
Registriert: Freitag 25. Januar 2008, 17:57

Hallo,
wir haben gerade in der Schule im Fach INFO mit dem Thema Rekursionen
in Python angefangen und auch schon gleich eine hausaufgabe aufbekommen. Doch bei dieser steh ich etwas auf dem Schlauch und wollte deßhalb einmal hier nachfragen.
Undzwar haben wir in Python ein kleines Programm programmiert, das diesen Algorithmus forsetzt (1,1,2,3,5,8,13,21...) und unsere Hausaufgabe dabei ist es uns Gedanken zu machen dies in eine Rekursion zu setzen oder so.
Doch ich habe keinerlei Ahnung wie dies in Python geht.
Ich kenne nur noch Rekursionen von LOGO.

Dies ist unser Programm:

Code: Alles auswählen

def fib ():
     a=1
     b=1
     for n in range (0, 50):
          c=a+b
          a=b
          b=c
print b
fib()
Ich hoffe einmal ihr könnt damit etwas anfangen.
Wäre sehr lieb, wenn mir jemand helfen könnte.
Falls Fragen bestehen, bitte Posten.
Danke im vorraus.

Mit freundlichen Grüßen

Söan

Edit (BlackJack): Code in Code-Tags gesetzt.
Nikolas
User
Beiträge: 102
Registriert: Dienstag 25. Dezember 2007, 22:53
Wohnort: Freiburg im Breisgau

Du solltest die

Code: Alles auswählen

y[/b]]
-Tags benutzen.

Wo liegt denn eigentlich das Problem?
Erwarte das Beste und sei auf das Schlimmste vorbereitet.
Imperator
User
Beiträge: 275
Registriert: Montag 20. August 2007, 14:43
Kontaktdaten:

Ihr habt doch bestimmt was dazu aufgeschrieben im heft. Also schau doch einfach nach. :wink:
söan
User
Beiträge: 2
Registriert: Freitag 25. Januar 2008, 17:57

Ne das ist ja gerade das Problem, wir haben dazu noch nichts aufgeschrieben :(
EyDu
User
Beiträge: 4881
Registriert: Donnerstag 20. Juli 2006, 23:06
Wohnort: Berlin

Schaffst du es nicht mal Fibonacci und Rekursion bei Google einzugeben? Da hast du gleich tausend fertige Lösungen.
Nikolas
User
Beiträge: 102
Registriert: Dienstag 25. Dezember 2007, 22:53
Wohnort: Freiburg im Breisgau

Das Programm funktioniert doch. Was ist denn eigentlich die Frage?
Erwarte das Beste und sei auf das Schlimmste vorbereitet.
Benutzeravatar
Craven
User
Beiträge: 223
Registriert: Dienstag 24. Januar 2006, 13:37

Nikolas hat geschrieben:Das Programm funktioniert doch. Was ist denn eigentlich die Frage?
Wie man das Programm mit Rekursion gestalten könnte.
[code]q = 'q = %s; print q %% repr(q)'; print q % repr(q) [/code]
Imperator
User
Beiträge: 275
Registriert: Montag 20. August 2007, 14:43
Kontaktdaten:

http://de.wikipedia.org/wiki/Rekursion

Das dürfte dir weiterhelfen
DarXun
User
Beiträge: 21
Registriert: Montag 21. Januar 2008, 00:44

EyDu hat geschrieben:Schaffst du es nicht mal Fibonacci und Rekursion bei Google einzugeben? Da hast du gleich tausend fertige Lösungen.
Das ist doch nicht der Sinn der Sache bei einer Hausaufgabe...
Er möchte doch Hilfestellungen und keine ganzen Lösungen...

@Topic:

Du setzt zu Anfang der Funktion a und b jedes Mal auf 0.
Bei einer Rekursiven Lösung solltest du bei jedem Funktionsaufruf vllt. die neuen Werte von a und b übergeben, und sie nicht immer wieder auf 0 setzen ;-)

Wenn du noch Fragen hast, ... ... dann frag :D
BlackJack

@Nikolas: Nachdem ich das Programm in Code-Tags gesetzt habe, sieht's nicht mehr so aus als wenn's funktioniert.

@söan: Wenn Du Rekursion von Logo kennst, dann sehe ich jetzt das Problem bei Python nicht. Das Konzept "Rekursion" ist sprachunabhängig. ``OUTPUT`` von Logo heisst in Python ``return``. Arbeite das Python-Tutorial aus der Dokumentation durch bis Du alles über Funktionen weisst, und dann übertrage das Wissen von Logo einfach auf Python.
EyDu
User
Beiträge: 4881
Registriert: Donnerstag 20. Juli 2006, 23:06
Wohnort: Berlin

DarXun hat geschrieben:Das ist doch nicht der Sinn der Sache bei einer Hausaufgabe...
Er möchte doch Hilfestellungen und keine ganzen Lösungen...
Für mich hört sich der Post aber ganz anders an: "Hier habt hier meinen Code, ich brauche eine rekursive Lösung, wenn ihr Fragen zur Aufgabe habt könnt ihr mich fragen, sonst stellt einfach das Ergebnis online."

Und sich das bißchen selbst zu erarbeiten ist wirklich keine Schwierigkeit.
Nikolas
User
Beiträge: 102
Registriert: Dienstag 25. Dezember 2007, 22:53
Wohnort: Freiburg im Breisgau

@ BlackJack: Das es nicht funktioniert könnte auch daran liegen, dass du das print b eine Einrücktung zu weit links gesetzt hast. :lol:
Erwarte das Beste und sei auf das Schlimmste vorbereitet.
BlackJack

@Nikolas: Nein das habe ich nicht getan, das war schon so. Ich habe nur die Code-Tags gesetzt.
DarXun
User
Beiträge: 21
Registriert: Montag 21. Januar 2008, 00:44

Also ich will nochmal einen kleine Tipp geben.
Ich hab diese Aufgabe so gelöst:

1.) Deine Funktion kopiert
2.) Überlegungen: Rekursive Funktionen rufen sich selber auf und haben eine Abbruchbedingung, d.h. die Variablen a und b dürfen nicht bei jedem Aufruf neu auf 1 gesetzt werden ( wie oben bereits gesagt)
3.) Die Schleife muss ersetzt werden
4.) Abbruchbedingung: falls n 50 ist ( n ist die Zählervariable)

So... Die Tipps sollten eigentlich reichen <.<
Ist ja schon fast die Lösung... :P
BlackJack

Wobei man vielleicht auch einfach durch die Definition der Fibonacci-Zahlen zu einer Rekursiven Lösung kommt. So wie die normalerweise mathematisch definiert werden, hat man die Lösung ja im Grunde schon auf dem Silbertablett serviert.

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.
Leonidas
Python-Forum Veteran
Beiträge: 16025
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

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 (former) Modvoice
sma
User
Beiträge: 3018
Registriert: Montag 19. November 2007, 19:57
Wohnort: Kiel

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

@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
Python-Forum Veteran
Beiträge: 16025
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

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 (former) Modvoice
Antworten