iterativ und rekursiv

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.
muskel
User
Beiträge: 6
Registriert: Sonntag 9. November 2008, 19:12

Dienstag 11. November 2008, 15:34

Hallo liebe Leute!

Mich plagt im Moment die genauen Unterschiede zwischen iterative Programmierart und rekursive Programmierart in Python. Ich habe jetzt schon mindestens 5 Erklärungen dazu durchgelesen und kenne nun alle Vor- und Nachteile. Aber wie genau jetzt eine iterative Funktion aussieht oder wie das gleiche Programm rekursiv aussieht, ist mir einfach nicht klar. :cry:
Immer wieder komme ich ins Zweifeln, wenn ich denke, ich hätte es endlich verstanden.
Leonidas
Administrator
Beiträge: 16024
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Dienstag 11. November 2008, 15:44

Wenn die Funktion sich selbst aufruft, ist sie rekursiv. Wenn sie stattdessen Schleifen nutzt, dann ist sie iterativ.

Habe jetzt momentan keine Zeit ein Beispiel zu machen, aber das wird sicher gleich jemand anderes nachliefern.
My god, it's full of CARs! | Leonidasvoice vs Modvoice
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

Dienstag 11. November 2008, 15:48

Leonidas hat geschrieben:Wenn die Funktion sich selbst aufruft, ist sie rekursiv. Wenn sie stattdessen Schleifen nutzt, dann ist sie iterativ.

Habe jetzt momentan keine Zeit ein Beispiel zu machen, aber das wird sicher gleich jemand anderes nachliefern.
Genau. Beispiel Fibonacci-Zahlen. Spricht für sich.

Code: Alles auswählen

def fibo_iterativ(n):
    a = b = 1
    for k in xrange(n-1):
        a, b = a+b, a
    return b

def fibo_rekursiv(n):
    if n>2:
        return fibo_rekursiv(n-1)+fibo_rekursiv(n-2)
    else:
        return 1
DasIch
User
Beiträge: 2462
Registriert: Montag 19. Mai 2008, 04:21
Wohnort: Berlin

Dienstag 11. November 2008, 15:51

Iterativ wäre:

Code: Alles auswählen

while True:
    print "Hello, World!"
Rekursiv:

Code: Alles auswählen

def foo():
    print "Hello, World!"
    foo()
foo()
Rekursion ist eine spezielle Form der Iteration und sollte in Python weitestgehend vermieden werden, da Endrekursion nicht zu iteration optimiert wird. Desweiteren gibt es in Python ein Rekursionslimit dass bei 1000 liegt, kann man erhöhen sollte man aber nicht unbedingt.
ichbinsisyphos
User
Beiträge: 120
Registriert: Montag 4. Juni 2007, 19:19

Dienstag 11. November 2008, 16:12

Code: Alles auswählen

def factorial(x):
        if x == 0:
                return 1
        else:
                return x * factorial(x - 1)

for i in range(20):
        print "%i!\t%i" % (i, factorial(i))
Fakultätsberechnung ist ein Paradebeispiel für eine Rekursion.

Wenn x!=0 ist, dann wird die Funktion innerhalb der Funktion für x-1 nocheinmal aufgerufen, und so weiter, bis das Argument 0 erreicht wird.

Dann gibts keinen neuen Funktionsaufruf, sondern die Zahl 1 wird zurückgegeben, dann erst kann die ganze Schlange aufgelöst werden.
derdon
User
Beiträge: 1316
Registriert: Freitag 24. Oktober 2008, 14:32

Dienstag 11. November 2008, 16:17

Und Fakultät funktional:

Code: Alles auswählen

In [27]: from operator import mul

In [28]: for num in xrange(2, 20):
    print reduce(mul, xrange(1, num))
   ....:     
   ....:     
1
2
6
24
120
720
5040
40320
362880
3628800
39916800
479001600
6227020800
87178291200
1307674368000
20922789888000
355687428096000
6402373705728000
Edit: "iterativ" in "funktional" umbenannt, um Yogi glücklich zu machen :)
Zuletzt geändert von derdon am Dienstag 11. November 2008, 20:49, insgesamt 1-mal geändert.
Qubit
User
Beiträge: 75
Registriert: Dienstag 7. Oktober 2008, 09:07

Dienstag 11. November 2008, 16:44

derdon hat geschrieben:Und Fakultät iterativ:
Jeder rekursive Algorithmus lässt sich auch iterativ formulieren ;-)
DasIch
User
Beiträge: 2462
Registriert: Montag 19. Mai 2008, 04:21
Wohnort: Berlin

Dienstag 11. November 2008, 17:24

Qubit hat geschrieben:Jeder rekursive Algorithmus lässt sich auch iterativ formulieren ;-)
Er hat eine iterative Formulierung gezeigt :P
ichbinsisyphos
User
Beiträge: 120
Registriert: Montag 4. Juni 2007, 19:19

Dienstag 11. November 2008, 17:53

Und was sind die Vorteile von rekursiven Funktionen gegenüber iterativen? Mir wär noch kein Vorteil eingefallen, ausser vielleicht in manchen Fällen kompakterer code.
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

Dienstag 11. November 2008, 17:58

ichbinsisyphos hat geschrieben:Und was sind die Vorteile von rekursiven Funktionen gegenüber iterativen? Mir wär noch kein Vorteil eingefallen, ausser vielleicht in manchen Fällen kompakterer code.
Korrekt. Und manchmal einfach mehr Eleganz.

Gelegentlich lässt sich auch die Idee eines Algorithmus durch die rekursive Umsetzung klarer abbilden.
BlackJack

Dienstag 11. November 2008, 18:07

@ichbinsisyphos: Insbesondere bei rekursiven Datenstrukturen wie Bäumen sind rekursive Funktionen ein "natürlicher" Ansatz.
Leonidas
Administrator
Beiträge: 16024
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Dienstag 11. November 2008, 18:24

ichbinsisyphos hat geschrieben:Und was sind die Vorteile von rekursiven Funktionen gegenüber iterativen? Mir wär noch kein Vorteil eingefallen, ausser vielleicht in manchen Fällen kompakterer code.
Neben dem schon beschriebenen gibt es auch Sprachen die gar keine Schleifen haben sondern nur Rekursion bieten.
My god, it's full of CARs! | Leonidasvoice vs Modvoice
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

Dienstag 11. November 2008, 18:47

Leonidas hat geschrieben:Neben dem schon beschriebenen gibt es auch Sprachen die gar keine Schleifen haben sondern nur Rekursion bieten.
Könntest du ein Beispiel geben?
DasIch
User
Beiträge: 2462
Registriert: Montag 19. Mai 2008, 04:21
Wohnort: Berlin

Dienstag 11. November 2008, 18:58

numerix hat geschrieben:Könntest du ein Beispiel geben?
Fast alle funktionalen Sprachen mit tail-call-optimization wie z.B. Scheme.
Leonidas
Administrator
Beiträge: 16024
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Dienstag 11. November 2008, 19:00

numerix hat geschrieben:
Leonidas hat geschrieben:Neben dem schon beschriebenen gibt es auch Sprachen die gar keine Schleifen haben sondern nur Rekursion bieten.
Könntest du ein Beispiel geben?
Scheme. Natürlich kannst du dir Makros ala LOOP wie in Common Lisp bauen, jedoch musst du dann rechnen von anderen Scheme-Programmierern ausgelacht zu werden.

Daher sind auch die verschiedenen map-Funktionen, reduce, filter etc. so praktisch.
My god, it's full of CARs! | Leonidasvoice vs Modvoice
Antworten