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.
Immer wieder komme ich ins Zweifeln, wenn ich denke, ich hätte es endlich verstanden.
iterativ und rekursiv
-
- Python-Forum Veteran
- Beiträge: 16025
- Registriert: Freitag 20. Juni 2003, 16:30
- Kontaktdaten:
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.
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 (former) Modvoice
Genau. Beispiel Fibonacci-Zahlen. Spricht für sich.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.
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
Iterativ wäre:
Rekursiv:
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.
Code: Alles auswählen
while True:
print "Hello, World!"
Code: Alles auswählen
def foo():
print "Hello, World!"
foo()
foo()
-
- User
- Beiträge: 120
- Registriert: Montag 4. Juni 2007, 19:19
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))
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.
Und Fakultät funktional:
Edit: "iterativ" in "funktional" umbenannt, um Yogi glücklich zu machen
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
Zuletzt geändert von derdon am Dienstag 11. November 2008, 20:49, insgesamt 1-mal geändert.
-
- User
- Beiträge: 120
- Registriert: Montag 4. Juni 2007, 19:19
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.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.
Gelegentlich lässt sich auch die Idee eines Algorithmus durch die rekursive Umsetzung klarer abbilden.
@ichbinsisyphos: Insbesondere bei rekursiven Datenstrukturen wie Bäumen sind rekursive Funktionen ein "natürlicher" Ansatz.
-
- Python-Forum Veteran
- Beiträge: 16025
- Registriert: Freitag 20. Juni 2003, 16:30
- Kontaktdaten:
Neben dem schon beschriebenen gibt es auch Sprachen die gar keine Schleifen haben sondern nur Rekursion bieten.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.
My god, it's full of CARs! | Leonidasvoice vs (former) Modvoice
-
- Python-Forum Veteran
- Beiträge: 16025
- Registriert: Freitag 20. Juni 2003, 16:30
- Kontaktdaten:
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.numerix hat geschrieben:Könntest du ein Beispiel geben?Leonidas hat geschrieben:Neben dem schon beschriebenen gibt es auch Sprachen die gar keine Schleifen haben sondern nur Rekursion bieten.
Daher sind auch die verschiedenen map-Funktionen, reduce, filter etc. so praktisch.
My god, it's full of CARs! | Leonidasvoice vs (former) Modvoice
Haskell wäre auch ein Beispiel für eine Programmiersprache die "nur" Rekursion bietet.
@derdon: Dein iteratives Beispiel ist aber nur eines weil Du eine ``for``-Schleife drum herum gebastelt hast. Denn das `reduce()` intern eine Schleife und keine Rekursion verwendet ist ein Implementierungsdetail. :-=
@derdon: Dein iteratives Beispiel ist aber nur eines weil Du eine ``for``-Schleife drum herum gebastelt hast. Denn das `reduce()` intern eine Schleife und keine Rekursion verwendet ist ein Implementierungsdetail. :-=