Iteration versus Rekursion - Revision history

Ukoethe: /* Version 4: Endrekursiv */

2012-06-13T14:49:32Z

‎Version 4: Endrekursiv

Ukoethe: /* Version 3: Course-of-values recursion */

2012-06-13T14:46:36Z

‎Version 3: Course-of-values recursion

Ukoethe: /* Entscheidende Eigenschaften der Rekursion */

2012-06-13T14:41:34Z

‎Entscheidende Eigenschaften der Rekursion

Ukoethe: /* Version 3: Course-of-values recursion */

2012-06-13T09:30:27Z

‎Version 3: Course-of-values recursion

Ukoethe: /* Version 4: Endrekursiv */

2012-06-13T09:27:58Z

‎Version 4: Endrekursiv

Ukoethe: /* Version 5: Umwandlung in einen iterativen Algorithmus ohne Stack */

2012-06-13T09:23:03Z

‎Version 5: Umwandlung in einen iterativen Algorithmus ohne Stack

Ukoethe: /* Version 5: Umwandlung in einen iterativen Algorithmus ohne Stack */

2012-06-13T09:22:50Z

‎Version 5: Umwandlung in einen iterativen Algorithmus ohne Stack

Ukoethe: /* Version 3: Course-of-values recursion */

2012-06-13T09:12:10Z

‎Version 3: Course-of-values recursion

79.211.55.26: Link zum nächsten Thema hinzugefügt

2008-07-22T21:37:02Z

Link zum nächsten Thema hinzugefügt

Ukoethe: /* Rekursionsbäume und Substitutionsmethode */

2008-07-22T00:08:33Z

‎Rekursionsbäume und Substitutionsmethode

@@ Line 164: / Line 164: @@
   def fib4(n):
-      if n == 0:
+      return fib4Impl(1, 0, n)
 Die Hilfsfunktion:
@@ Line 177: / Line 174: @@
          return fib4Impl(f1+f2, f1, counter-1)   # f1 ist die letzte Fibonacci-Zahl,
                                                  # f1+f2 wird die neue Fibonacci-Zahl und wir müssen counter um 1 herunterzählen
 Beispiel mit n=3:

@@ Line 150: / Line 150: @@
       else:                          # rekursiver Aufruf
          f1, f2 = fib3Impl(n-1)      # f1 ist Fibonacci-Zahl von n, f2 die von (n-1)
-         return f1 + f2, f1          # gebe neue Fibonacci-Zahl f<sub>n+1</sub>  =f1+f2 und die vorherige (f<sub>n</sub> = f1) zurück.
+         return f1 + f2, f1          # gebe neue Fibonacci-Zahl f<sub>n+1</sub> = f1+f2 und die vorherige (f<sub>n</sub> = f1) zurück.
 &rArr; Diese Implementation ist jetzt linear-rekursiv (aber nicht endrekursiv). Sie hat damit lineare Komplexität und nicht exponentielle wie die beiden vorherigen Versionen.

@@ Line 33: / Line 33: @@
 * Jede rekursive Funktion muß <u>mindestens '''einen''' nicht-rekursiven</u> Zweig haben. Dieser Zweig wird als '''Basisfall''' oder '''Rekursionsabschluss''' bezeichnet.
-* Jeder rekursive Aufruf muß über <u>endlich viele Stufen</u> auf einen Basisfall zurückgeführt werden, denn sonst erhält man eine Endlosrekursion (und das ist fast so übel wie eine Endlosschleife -- "fast" deshalb, weil die Endlosrekursion spätestens dann abbricht wenn der Speicher voll ist --> siehe Übung 7 Aufgabe 1).
+* Jeder rekursive Aufruf muß über <u>endlich viele Stufen</u> auf einen Basisfall zurückgeführt werden, denn sonst erhält man eine Endlosrekursion (und das ist fast so übel wie eine Endlosschleife -- "fast" deshalb, weil die Endlosrekursion spätestens dann abbricht wenn der Speicher voll ist --> siehe Übung 8 Aufgabe 2a).
 * Die Anzahl der rekursiven Aufrufe bis zum Rekursionsabschluss bezeichnet man als '''Rekursionstiefe d'''.

@@ Line 140: / Line 140: @@
   def fib3(n):
-     if n == 0: return 0     # Rekursionsabschluss
+      f1, f2 = fib3Impl(n)    # Hilfsfunktion, f1 ist die Fibonacci-Zahl von (n+1) und f2 ist die Fibonacci-Zahl von n
-      f1, f2 = fib3Impl(n)    # Hilfsfunktion, f1 ist die Fibonacci-Zahl von n und f2 ist die Fibonacci-Zahl von (n-1)
+      return f2
 Die Hilfsfunktion enthält jetzt die eigentliche Rekursion. Sie berechnet die Fibonacci-Zahlen f<sub>k</sub> und f<sub>k-1</sub> aus den Zahlen f<sub>k-1</sub> und f<sub>k-2</sub>:
   def fib3Impl(n):
-      if n == 1: return 1, 0         # gebe die Fibonacci-Zahl von 1 und die davor zurück
+      if n == 0:
       else:                          # rekursiver Aufruf
-         f1, f2 = fib3Impl(n-1)      # f1 ist Fibonacci-Zahl von (n-1), f2 die von (n-2)
+         f1, f2 = fib3Impl(n-1)      # f1 ist Fibonacci-Zahl von n, f2 die von (n-1)
-         return f1 + f2, f1          # gebe neue Fibonacci-Zahl f<sub>n</sub>=f1+f2 und die vorherige (f<sub>n-1</sub>=f1) zurück.
+         return f1 + f2, f1          # gebe neue Fibonacci-Zahl f<sub>n+1</sub>  =f1+f2 und die vorherige (f<sub>n</sub> = f1) zurück.
 &rArr; Diese Implementation ist jetzt linear-rekursiv (aber nicht endrekursiv). Sie hat damit lineare Komplexität und nicht exponentielle wie die beiden vorherigen Versionen.

@@ Line 163: / Line 163: @@
 Man gelangt von der Course-of-values Rekursion zur Endrekursion, indem man einfach die Berechnungsreihenfolge umkehrt: statt rückwärts von f<sub>n</sub> nach f<sub>0</sub> zu arbeiten, arbeitet man vorwärts von f<sub>0</sub> nach f<sub>n</sub>. Dazu muss der Hilfsfunktion eine Zählvariable übergeben werden, die angibt, wie viele Schritte noch bis zum Ziel f<sub>n</sub> verbleiben. Außerdem erhält die Hilfsfunktion die beiden vorherigen Fibonacci-Zahlen als Argument übergeben:
-  def fib4(n)
+  def fib4(n):
       if n == 0:
          return 0
       else:
-         return fib4Impl(0, 1, n)
+         return fib4Impl(1, 0, n)
 Die Hilfsfunktion:
-  def fib4Impl(f<sub>1</sub>, f<sub>2</sub>, counter)
+  def fib4Impl(f1, f2, counter):
-      if counter == 1:
+      if counter == 0:
-         return f<sub>2</sub>
+         return f2
       else:
-         return fib4Impl(f<sub>2</sub>, f<sub>1</sub>+f<sub>2</sub>, counter-1)   # f<sub>2</sub> ist die vorletzte Fibonacci-Zahl,
+         return fib4Impl(f1+f2, f1, counter-1)   # f1 ist die letzte Fibonacci-Zahl,
-                                                 # f<sub>1</sub>+f<sub>2</sub> wird die neue Fibonacci-Zahl und wir müssen counter um 1 herunterzählen
+                                                 # f1+f2 wird die neue Fibonacci-Zahl und wir müssen counter um 1 herunterzählen
 Beispiel mit n=3:
@@ Line 188: / Line 188: @@
 |-
 | fib4Impl 1.Aufruf
 |align="center"| 0
 |align="left"| 3
 |-
@@ Line 198: / Line 198: @@
 |-
 | fib4Impl 3.Aufruf
 |align="center"| 1
-|align="center"| 2
+|align="left"| 1
-| 1 &rArr; Rekursionsabschluss &rArr; return 2
+|-
 |}

@@ Line 217: / Line 217: @@
       f1, f2 = 1, 0                # f1 ist die Fibonaccizahl für n=1, f2 die für n=0
       while n > 0:
-          f1, f2 = f1 + f2, f1     # berechne die nächste Fibnaccizahl in f1 und speichere die letzte in f2
+          f1, f2 = f1 + f2, f1     # berechne die nächste Fibonaccizahl in f1 und speichere die letzte in f2
           n -= 1
       return f2

@@ Line 215: / Line 215: @@
   def fib5(n):
-      f<sub>1</sub>, f<sub>2</sub> = 0, 1
+      f1, f2 = 1, 0                # f1 ist die Fibonaccizahl für n=1, f2 die für n=0
       while n > 0:
-          f<sub>1</sub>, f<sub>2</sub> = f<sub>2</sub>, f<sub>1</sub>+f<sub>2</sub>
+          f1, f2 = f1 + f2, f1     # berechne die nächste Fibnaccizahl in f1 und speichere die letzte in f2
           n -= 1
-      return f<sub>1</sub>
+      return f2
 Das ist genau das gleiche wie <tt>fib4Impl</tt>. Aber anstelle eines rekursiven Aufrufes werden einfach die Variablen f<sub>1</sub> und f<sub>2</sub> wiederverwendet (mit den neuen Werten überschrieben). Dies ist möglich, weil die originalen Werte nicht mehr benötigt werden, denn der rekursive Aufruf bei <tt>fib4Impl</tt> war der letzte Befehl vor dem return (Endrekursion!).

← Older revision		Revision as of 21:37, 22 July 2008
Line 373:		Line 373:
	:::<math>T(n) = T(p) + T(n-p) + c\cdot n</math>		:::<math>T(n) = T(p) + T(n-p) + c\cdot n</math>
	und das Teilungsverhältnis wird umso schlechter, je größer n wird. Dies ist gerade der ungünstige Fall bei Quicksort, und wir haben gesehen, dass sich die Komplexität hier auf O(n<sup>2</sup>) verschlechtert.		und das Teilungsverhältnis wird umso schlechter, je größer n wird. Dies ist gerade der ungünstige Fall bei Quicksort, und wir haben gesehen, dass sich die Komplexität hier auf O(n<sup>2</sup>) verschlechtert.
		+
		+	[[Generizität\|Nächstes Thema]]

@@ Line 354: / Line 354: @@
 (wir haben hier willkürlich Logarithmen zu Basis 2 eingesetzt -- die Basis in der O-Notation ist bekanntlich beliebig). Einsetzen in die Rekursionsformel liefert
 :::<math>T(n) \le T\left(\frac{n}{3}\right)+ T\left(\frac{2n}{3}\right)+ c\,n \le d\,\frac{n}{3}\,\mbox{ld}\left(\frac{n}{3}\right)+ d\,\frac{2n}{3}\,\mbox{ld}\left(\frac{2n}{3}\right)+ c\,n</math>
-Durch Ausmultiplizieren der Klammern und Trennen der Logarithmen von Quotionten in Differenzen von Logarithmen erhalten wir
+Durch Ausmultiplizieren der Klammern und Trennen der Logarithmen von Quotionten erhalten wir
 :::<math> T(n) \le d\frac{1}{3}\,n\,\mbox{ld}(n)-d\,\frac{1}{3}\,n\,\mbox{ld}(3)+d\,\frac{2}{3}\,n\,\mbox{ld}(n)+d\,\frac{2}{3}\,n\,\mbox{ld}(2)-d\,\frac{2}{3}\,n\,\mbox{ld}(3)+c\,n</math>
 Unter Beachtung von ld(2)=1 können wir die Terme wie folgt zusammenfassen