iterativ und rekursiv

[muskel]

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.

[Leonidas]

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.

[numerix]

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]

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]

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]

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

[Qubit]

Und Fakultät iterativ:

Jeder rekursive Algorithmus lässt sich auch iterativ formulieren

[DasIch]

Jeder rekursive Algorithmus lässt sich auch iterativ formulieren

Er hat eine iterative Formulierung gezeigt

[ichbinsisyphos]

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.

[numerix]

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]

@ichbinsisyphos: Insbesondere bei rekursiven Datenstrukturen wie Bäumen sind rekursive Funktionen ein "natürlicher" Ansatz.

[Leonidas]

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.

[numerix]

Neben dem schon beschriebenen gibt es auch Sprachen die gar keine Schleifen haben sondern nur Rekursion bieten.

Könntest du ein Beispiel geben?

[DasIch]

Könntest du ein Beispiel geben?

Fast alle funktionalen Sprachen mit tail-call-optimization wie z.B. Scheme.

[Leonidas]

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.

[BlackJack]

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

[Y0Gi]

Deswegen könnte man es auch besser einfach "funktional" als "iterativ" nennen