Rekursive Funktionsdefinition für die Fakultät

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.
polynux
User
Beiträge: 11
Registriert: Sonntag 9. Mai 2004, 21:03

Rekursive Funktionsdefinition für die Fakultät

Beitragvon polynux » Mittwoch 2. Juni 2004, 15:17

hallo python-forum,

ich bin's mal wieder. Ich bin gerade dabei mir die Unterschiede und Vorzüge der Rekursiven bzw. Iterativen Programmierung klar zu machen. Dabei bin ich auf die mathematische Fakultät gestoßen, die man jeweils rekursiv und iterativ als Funktion programmieren kann. Unter folgendem Link stehen beide Versionen:

http://www.way2python.de/themen/kochbuch.html#fakul

Bei der rekursiven Version ist mir jedoch aufgefallen, dass da eigentlich eine Anweisung fehlt. Müsste der Code nicht eigentlich so lauten?

Code: Alles auswählen

 def fakul2(n):
    if n == 1 or n == 0:
        return 1
    else:
        return n * fakul2(n-1)


Denn mathematisch ist ja 0! = 1. Die Version, die auf der Website steht, wird aber auch immer auf anderen Seiten benutzt. Zudem ensteht ja eine endlose Rekursion, falls man die Zahl 0 einsetzen würde, und man nicht noch die obige Anweisung ergänzen würde. Was haltet ihr davon, liege ich da irgendwo falsch?

P.S.: Kennt ihr vielleicht einige gute Internetseiten über Rekursion und Iteration (entweder mit bezug zu Python oder auch allgemein).

Gruß

polynux
Benutzeravatar
Dookie
Python-Forum Veteran
Beiträge: 2010
Registriert: Freitag 11. Oktober 2002, 18:00
Wohnort: Salzburg
Kontaktdaten:

Beitragvon Dookie » Mittwoch 2. Juni 2004, 15:44

Hi polynus,

eine kenn ich da http://python.sandtner.net/viewtopic.ph ... hlight=fak ;)


Gruß

Dookie
Milan
User
Beiträge: 1078
Registriert: Mittwoch 16. Oktober 2002, 20:52

Beitragvon Milan » Mittwoch 2. Juni 2004, 15:47

Hi. Ja, eigentlich müsste er so lauten, aber es ging wohl mehr ums Prinzip, denn ansonsten ginge auch der iterative code noch viel effektiver zu schreiben (s.u.) und man könnte sagen, die Fakultät ist nur für positive Zahlen definiert :wink: :

Code: Alles auswählen

der faku(x):
    erg=1
    for i in xrange(2,x+1):
        erg*=i
    return erg


Ansonsten: google weiß viel und kennt viel...
polynux
User
Beiträge: 11
Registriert: Sonntag 9. Mai 2004, 21:03

Beitragvon polynux » Donnerstag 3. Juni 2004, 17:34

ich hab noch eine Frage:
wie kann man eine rekursive Funktion in Python schreiben, die die Quersumme einer Zahl berechnet? also zum Beispiel quersumme(n) für die Zahl n.
Milan
User
Beiträge: 1078
Registriert: Mittwoch 16. Oktober 2002, 20:52

Beitragvon Milan » Donnerstag 3. Juni 2004, 17:45

Hi. Das würde ich nicht rekursiv machen, da es mir einer einfachen while schleife genauso leicht geht :wink: . Aber zum Verständnis von Rekursion erklär ich es trotzdem gern mal, weil ich mich noch sehr gut dran erinner, wie ich das erste mal mit Rekursion zurecht gekommen bin... :roll:
Das wichtigste ist nat. immer eine Zahl abzutrennen, das geht sehr gut durch ganzzahlige division durch 10.

Code: Alles auswählen

def q(n):
    if n<10:
        return n
    return (n%10)+q(n/10)
def q2(n):
    erg=0
    while n!=0:
        n,rest=divmod(n,10)
        erg+=rest
    return erg
polynux
User
Beiträge: 11
Registriert: Sonntag 9. Mai 2004, 21:03

Beitragvon polynux » Donnerstag 3. Juni 2004, 18:14

danke für die schnelle Antwort. :wink:

mit der while-Schleife hab ich es auch schon hinbekommen, nur nicht rekursiv. Mit der Rekursion hab ich noch ziemliche Probleme. Hattest du die auch, ja? Seit wann beschäftigst du dich denn mit Python? Du scheinst hier im Forum einer derer zu sein, die am fitesten in Python sind. Hast du vielleicht irgendwelche Tipps, damit ich die Rekursion besser anwenden kann?

Gruß

polynux
Benutzeravatar
Dookie
Python-Forum Veteran
Beiträge: 2010
Registriert: Freitag 11. Oktober 2002, 18:00
Wohnort: Salzburg
Kontaktdaten:

Beitragvon Dookie » Donnerstag 3. Juni 2004, 19:05

Hi polynux,

bin zwar nicht milan, aber auch relativ fit in Python und allgemein im Programmieren :)
Leider werden in Büchern sehr oft wenig brauchbare Beispiele zur Rekursion gezeigt, die sich oft besser durch Iteration lösen lassen, wie auch Dein Beispiel mit der Quersumme. Durch Recursion werden die Beispiele dann oft komplizierter als erforderlich.

Eine Ausnahme bildet das die Fakultätsfunktion, hier sind sowohl die rekursive als auch die iterative Variante recht klar zu lesen.

Ich würde die rekursive Falkultätsfunktion allerdings so formulieren:

Code: Alles auswählen

def fakul2(n):
    if n > 2:
        return n * fakul2(n-1)
    else:
        return n

So braucht nur eine Bedingung geprüft zu werden und für 0 und 1 ergibt sich auch das richtige Ergebnis.

Rekursive Methoden/Funktionen bieten sich besonders an bei Datenstrukturen die ihrerseits schon rekursiv definiert sind, wie z.B. bei Bäumen. Ich hab hier mal ein kleines Beispiel gecodet:

Code: Alles auswählen

class node(object):
    """ Klasse für eine einfache Baumstruktur """

    __slots__ = ["left","right","value"]

    def __init__(self, value):
        """ Neuen Knoten des Baumes initialisieren """
        self.left = None
        self.right = None
        self.value = value

    def insert(self, value):
        """ Wert in Baumstruktur einfügen """
        if value < self.value:
            if self.left:
                self.left.insert(value)
            else:
                self.left = node(value)
        else:
            if self.right:
                self.right.insert(value)
            else:
                self.right = node(value)

    def print_tree(self, indent=0):
        """ Baumstruktur darstellen, die Einrückung stellt die Tiefe im Baum dar """
        if self.left:
            self.left.print_tree(indent+1)
        print ("  "*indent)+self.value
        if self.right:
            self.right.print_tree(indent+1)
           
    def inorder(self):
        """ Baum "inorder" als Liste zurückgeben """
        result = [self.value]
        if self.left:
            result = self.left.inorder()+result
        if self.right:
            result = result+self.right.inorder()
        return result

    def preorder(self):
        """ Baum "preorder" als Liste zurückgeben """
        result = [self.value]
        if self.left:
            result = result+self.left.preorder()
        if self.right:
            result = result+self.right.preorder()
        return result

    def postorder(self):
        """ Baum "postorder" als Liste zurückgeben """
        if self.left:
            result = self.left.postorder()
        else:
            result = []
        if self.right:
            result += self.right.postorder()
        result.append(self.value)
        return result


if __name__ == "__main__":
    tree = node("d")
    tree.insert("c")
    tree.insert("f")
    tree.insert("a")
    tree.insert("b")
    tree.insert("e")
    tree.insert("g")
    tree.print_tree()
    print tree.inorder()
    print tree.preorder()
    print tree.postorder()


Ausser der __init__ Methode sind alle anderen Methoden rekursiv. Diese Methoden iterativ zu realisieren stellt selbst bei dieser einfachen Struktur schon einen relativ grossen Aufwand dar.


Gruß

Dookie
polynux
User
Beiträge: 11
Registriert: Sonntag 9. Mai 2004, 21:03

Beitragvon polynux » Freitag 4. Juni 2004, 15:46

@dookie

warum welche Programmiersprachen kannst du denn noch?
Benutzeravatar
Dookie
Python-Forum Veteran
Beiträge: 2010
Registriert: Freitag 11. Oktober 2002, 18:00
Wohnort: Salzburg
Kontaktdaten:

Beitragvon Dookie » Freitag 4. Juni 2004, 16:14

angefangen hab ich an einem C64 mit Basic, Pascal, 6502-Assembler, dann am Amiga 68k-Assembler, Modula2, Oberon2 und erste Schritte in C, danach am Mac Applescript, HTML/Javascript, C++, PHP und etwas in Java reingeschnuppert. Mit Linux bin ich dann auf Python gestossen und ich bleib bis auf weiteres auch dabei, besonders da sich für zeitkritische Sachen Module in C sehr leicht einbinden lassen.


Gruß

Dookie
Seb

Beitragvon Seb » Freitag 4. Juni 2004, 16:17

es ist wahr, rekursion wird in den meisten büchern sehr schlecht behandelt.

drei dinge finde ich sehr wichtig für ein verständnis:

1. programmiersprachen sind nicht automatisch in der lage ein rekursives programm auszuführen. das muss explizit vom designer der sprache eingebaut werden. die tatsache, dass da was im hintergrund abläuft hat es mir erst ermöglicht rekursion richtig zu verstehen.

2. ein schöne bildliche veranschaulichung was bei der rekursion passiert:
Bild
(von http://www-106.ibm.com/developerworks/xml/library/x-xslrecur/)

3. die vereinfachung die die rekursion bringt hinnehmen und einsetzen.
ein sehr schönes beispiel dafür sind die türme von hanoi.
wenn man hier im einzelnen versucht nachzuvollziehen was passiert, kommt man nicht weit. wenn man das ganze aber "von oben" betrachtet und die rekursion "akzeptiert" , dann ... :)
traversierung von bäumen ist natürlcih auch ne klasse sache...

viel spass bei rekursieren!
Milan
User
Beiträge: 1078
Registriert: Mittwoch 16. Oktober 2002, 20:52

Beitragvon Milan » Freitag 4. Juni 2004, 19:26

polynux hat geschrieben:Mit der Rekursion hab ich noch ziemliche Probleme. Hattest du die auch, ja? Seit wann beschäftigst du dich denn mit Python? Du scheinst hier im Forum einer derer zu sein, die am fitesten in Python sind. Hast du vielleicht irgendwelche Tipps, damit ich die Rekursion besser anwenden kann?

Hi. Ja, ich hatte am Anfang auch ziemlich große Probleme mit Rekursion... das war ungefährt ein halbes Jahr nachdem ich das erste mal mit Python programmiert habe (wir haben in der 9. Klasse in der Schule mit Python angefangen. Heute machen wir leider Oberon. :evil: Oberon stinkt!). Angefangen Rekursion zu kapieren hab ich dann, als ich eine Mischung aus Rekursion und Iteration zusammenbauen musste: die Aufgabe war eine Liste umzudrehen, also eine Funktion reverse zu schreiben. Eigentlich eine triviale Sache, aber die Bedingung war, alle Sublisten auch umzudrehen. Und genau da hats dann gegriffen: durch die Iteration hattest du den nötigen Überblick, was in einem Arbeitsschritt passieren muss und dann ist auch automatisch klar, was passieren muss, wenn man eine Ebene tiefer geht.

Code: Alles auswählen

def reverse(liste):
    erg=[]
    for i in liste:
        if type(i)==list:
            i=reverse(i)
        erg.insert(0,i)
    return erg

Mehr ist es eigentlich auch nicht... du musst nur immer wissen, was ein Schritt sein soll und wann du fertig bist / es keine weiteren kleineren Ebenen gibt.
Für den Rest kann ich mich nur dem oben gesagtem anschließen :) .

Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder