Das deutsche Python-Forum

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.

Du solltest die

Code: Alles auswählen

y[/b]]

-Tags benutzen.

Wo liegt denn eigentlich das Problem?

Ihr habt doch bestimmt was dazu aufgeschrieben im heft. Also schau doch einfach nach.

Ne das ist ja gerade das Problem, wir haben dazu noch nichts aufgeschrieben

Schaffst du es nicht mal Fibonacci und Rekursion bei Google einzugeben? Da hast du gleich tausend fertige Lösungen.

Das Programm funktioniert doch. Was ist denn eigentlich die Frage?

Nikolas hat geschrieben:Das Programm funktioniert doch. Was ist denn eigentlich die Frage?

Wie man das Programm mit Rekursion gestalten könnte.

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

Das dürfte dir weiterhelfen

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

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

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.

@ BlackJack: Das es nicht funktioniert könnte auch daran liegen, dass du das print b eine Einrücktung zu weit links gesetzt hast.

@Nikolas: Nein das habe ich nicht getan, das war schon so. Ich habe nur die Code-Tags gesetzt.

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

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.

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

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

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

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

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.

Das deutsche Python-Forum

Frage zur Rekursion!

Frage zur Rekursion!