Iteration versus Rekursion
Rekursion in der Informatik:
Einen Funktion f ist rekursiv wenn sie sich selbst aufruft. Die Funktion heißt indirekt-rekursiv wenn sie sich selbst aufruft über den Umweg einer anderen Funktion (oder mehrerer anderer Funktionen).
Beispiel einer indirekten Rekursion:
foo ---> bar ---> foo
ruft auf ruft auf
Entscheidende Eigenschaften der Rekursion
- Jeder Aufruf einer rekursiven Funktion f hat sein eigenes Set von lokalen Variablen, d.h. der rekursive Aufruf hat die gleichen Anweisungen auszuführen, aber er hat seine eigenen Daten. Betrachten wir z.B. die rekursive Funktion
def f(n):
r = f(n-1)
... # weiterer Code
return r
- Für ein gegebenes n erhalten wir die Aufrufkette:
f(n) 1.Ebene
f(n-1) 2.Ebene
f(n-2) 3.Ebene
...
- Die Funktionsaufrufe der verschiedenen Ebenen werden so ausgeführt, als ob wir für jede Ebene eine eigene Funktion f1(n1), f2(n2), f3(n3) usw. definiert hätten:
f1(n1) 1.Ebene ---> n1 = n
f2(n2) 2.Ebene ---> n2 = n1-1
f3(n3) 3.Ebene ---> n3 = n2-1 = n1-2 = n-2
...
- Die Funktionen f1(n1), f2(n2), f3(n3) enthalten alle den gleichen Code, aber mit unterschiedlich benannten Variablen n1, n2, n3. Durch diese Umbenennungen sollte die obige Aussage deutlich werden.
- Jede rekursive Funktion muß mindestens einen nicht-rekursiven Zweig haben. Dieser Zweig wird als Basisfall oder Rekursionsabschluss bezeichnet.
- Jeder rekursive Aufruf muß über endlich viele Stufen 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).
- Die Anzahl der rekursiven Aufrufe bis zum Rekursionsabschluss bezeichnet man als Rekursionstiefe d.
- Jede rekursive Funktion kann in eine iterative Funktion umgewandelt werden, die statt rekursiver Aufrufe eine Schleife enthält. Wir beschreiben dies unten anhand von Beispielen.
Arten der Rekursion
Die Arten der Rekursion sind hier nicht vollständig angegeben, es gibt noch weitere. Aber die hier folgenden sind für die Programmierung am wichtigsten.
Lineare Rekursion
- Jeder Ausführungspfad durch die Funktion f enthält höchstens einen rekursiven Aufruf.
- Höchstens einen, weil mindestens ein Pfad existieren muss, der keinen rekursiven Aufruf enthält (der Basisfall).
- ⇒ Das Ergebnis der Aufrufe ist eine 1-dimensionale "Rekursionskette".
Baumrekursion
(auch Kaskadenrekursion)
- Mindestens ein Ausführungspfad durch die Funktion enthält mindestens 2 rekursive Aufrufe.
- Baumrekursion ist damit das Gegenteil der linearen Rekursion.
- ⇒ Das Ergebnis der Aufrufe ist ein verzweigter "Rekursionsbaum". Ein baum-rekursiver Algorithmus ist deshalb häufig ineffizient: Wird der Pfad mit mehreren rekursiven Aufrufen mindestens Ω(d)-mal ausgeführt (wobei d die Rekursionstiefe) ist, entsteht ein Rekursionsbaum mit O(2d) Knoten, also ein Algorithmus mit exponentieller Komplexität.
Course-of-values recursion
- Das Ergebnis des rekursiven Aufrufes für Argument n hängt nur von den Ergebnissen der letzten p-Aufrufe, also für Argument n-1,n-2,...,n-p ab (wobei p eine Konstante ist).
Primitive Rekursion
- Spezialfall der course-of-values recursion mit p=1.
- ⇒ Das ist auch ein Spezialfall der linearen Rekursion, denn wenn das Ergebnis nur von einem rekursiven Aufruf abhängt, kann kein Rekursionsbaum entstehen.
Endrekursion
- In jedem rekursiven Ausführungspfad ist der rekursive Aufruf der letzte Befehl vor dem return-Befehl.
- ⇒ Das ist ein Spezialfall der linearen Rekursion, denn es kann nur einen letzten Befehl vor jedem return geben, ein zweiter rekursiver Aufruf könnte allenfalls der vorletzte Befehl sein.
Beispiele und Umwandlung in Iteration
Beispiel für alle Rekursionsarten: Fibonacci-Zahlen
Wir verdeutlichen die verschiednenen Rekursionsarten und ihre Umwandlung in iterative Algorithmen am Beispiel der Fibonacci-Zahlen.
- Fibonacci-Zahlen
- Die n-te Fibonacci-Zahl ist gemäß der folgenden Rekursionsformel definiert.
- f0=0
- f1=1
- fn=fn-1+fn-2
- Es ergibt sich die Folge:
- fk=0, 1, 1, 2, 3, 5, 8, 13,....., (⇒ Die Reihe wächst exponentiell an.)
Im folgenden zeigen wir 5 verschiedene Algorithmen zu Berechnung der n-ten Fibonacci-Zahl:
1. Version: Naive rekursive Implementation
Implementiert man einfach die rekursive Formel der Definition, erhält man:
def fib1(n): # Funtion berechnet die n-te Fibonacci-Zahl
if n <= 1:
return n # Rekursionsabschluss
return fib1(n-1) + fib1(n-2) # Baumrekursion
Die Funktion fib1(n) ist ein Beispiel für eine Baumrekursion mit exponentieller Komplexität. Der Aufrufbaum sieht dann wie folgt aus:
fib1(n)
/ \
/ \
/ \
/ \
fib1(n-1) fib1(n-2)
/ \ / \
/ \ / \
/ \ / \
fib1(n-2) fib1(n-3) fib1(n-3) fib1(n-4)
Im Falle der Fibonacci-Zahlen ist dies ein ungünstiger Algorithmus, weil viele Teilergebnise wiederholt berechnet werden (z.B. fn-2 und fn-3). Aber einige Probleme sind echt Baumrekursiv, z.B. das Ausrechnen der möglichen Züge beim Schachspiel.
- Es gilt folgender grundlegender Satz
Jeder rekursiver Algorithmus kann mit Hilfe eines Stacks in einen iterativen Algorithmus umgewandelt werden (d.h. mit einer Schleife statt einer Rekursion). Das bedeutet, dass rekursive Programme gleichmächtig sind wie Programme mit Schleifen (z.B. WHILE-Programme, siehe erste Vorlesung), d.h. gleichmächtig wie die Turing-Maschine. Die Komplexität des Algorithmus ändert sich durch die Umwandlung nicht.
2. Version: Umwandlung in einen iterativen Algorithmus mit Stack
def fib2(n):
stack = [n] # der Stack enthält als erstes Teilproblem das ursprüngliche Problem "n-te Fibonacci-Zahl berechnen"
f = 0 # f wird später die Lösung enthalten
while len(stack) > 0: # solange noch was auf dem Stack liegt, ist noch Arbeit zu tun
k = stack.pop() # Teilproblem von Stack entnehmen und lösen
if k <= 1:
f += k # entweder: Teilergebnis zur Lösung addieren (das war vorher der Rekursionsabschluss)
else:
stack.append(k-1) # oder: zwei neue Teilprobleme auf dem Stack ablegen
stack.append(k-2) # (das waren vorher die rekursiven Aufrufe)
return f
3. Version: Course-of-values recursion
Wie man unmittelbar aus der Definitione erkennt, ist die Berechnung der Fibonacci-Zahlen Course-of-values rekursiv mit p=2. Eine entsprechende Implementation verwendet eine Hilfsunfktion, die immer die Ergebnisse der p letzten Aufrufe zurückgibt:
def fib3(n):
if n == 0: return 0 # Rekursionsabschluss
f1,f2 = fib3Impl(n) # Hilfsfuntion, f1 ist die Fibonacci-Zahl von n und f2 ist dei Fibonacci-Zahl von (n-1)
return f1
Die Hilfsfunktion enthält jetzt die eigentliche Rekursion. Sie berechnet die Fibonacci-Zahlen fk und fk-1 aus den Zahlen fk-1 und fk-2:
def fib3Impl(n):
if n == 1: return 1, 0 # gebe die Fibonacci-Zahl von 1 und die davor zurück
else: # rekursiver Aufruf
f1,f2 = fib3Impl(n-1) # f1 ist Fibonacci-Zahl von (n-1), f2 die von (n-2)
return f1 + f2, f1 # gebe neue Fibonacci-Zahl fn=f1+f2 und die vorherige (fn-1=f1) zurück.
⇒ Diese Implementation ist jetzt linear-rekursiv (aber nicht endrekursiv). Sie hat damit lineare Komplexität und nicht exponentielle wie die beiden vorherigen Versionen.
- Es gilt folgender Satz
Jede Course-of-values Rekursion kann in Endrekursion umgewandelt werden.
4. Version: Endrekursiv
Man gelangt von der Course-of-values recursion zur Endrekursion, indem man einfach die Berechnungsreihenfolge umkehrt: statt rückwärts von fn nach f0 zu arbeiten, arbeitet man vorwärts von f0 nach fn. Dazu muss der Hilfsfunktion eine Zählvariable übergeben werden, die angibt, wie viele Schritte noch bis zum Ziel fn verbleiben. Außerdem erhält die Hilfsfunktion die beiden vorherigen Fibonacci-Zahlen als Argument übergeben:
def fib4(n)
if n == 0: return 0
else:
return fib4Impl(0, 1, n)
Die Hilfsfunktion:
def fib4Impl(f1, f2, counter)
if counter == 1: return f2
else:
return fib4Impl(f2, f1+f2, n-1) # f2 ist die vorletzte Fibonacci-Zahl,
# f1+f2 wird die neue Fibonacci-Zahl und wir müssen n um 1 herunterzählen
Beispiel mit n=3:
| f1 | f2 | n | |
| fib4Impl 1.Aufruf | 0 | 1 | 3 |
| fib4Impl 2.Aufruf | 1 | 1 | 2 |
| fib4Impl 3.Aufruf | 1 | 2 | 1 ⇒ Rekursionsabschluss ⇒ return 2 |
⇒ Ergebnis von fib4(3) (die 3. Fibonacci-Zahl) ist 2.
- Es gilt folgender grundlegender Satz
Jede endrekursive Funktion kann ohne Stack in eine iterative Funktion umgewandelt werden.
Bei einigen Programmiersprachen (z.B. Lisp, Scheme) wird dies von Compiler sogar automatisch erledigt (als Programmoptimierung, weil Iteration im allgemeinen schneller ist als Rekursion).
5. Version: Umwandlung in einen iterativen Algorithmus ohne Stack
def fib5(n):
f1, f2 = 0, 1
while n > 0:
f1, f2 = f2, f1+f2
n -= 1
return f1
Das ist genau das gleiche wie fib4Impl. Aber anstelle eines rekursiven Aufrufes werden einfach die Variablen f1 und f2 wiederverwendet (mit den neuen Werten überschrieben). Dies ist möglich, weil die originalen Werte nicht mehr benötigt werden, denn der rekursive Aufruf bei fib4Impl war der letzte Befehl vor dem return (Endrekursion!).
Beispiel für die Umwandlung von Rekursion in Iteration: treeSort
Input:
- ein balancierter Binärbaum, repräsentiert durch seinen Wurzelknoten root
- ein leeres dynamisches Array a, das später die sortierten Elemente des Baums enthalten wird
Aufgerufen wird:
treeSort(root,a) # kopiert Elemente des Baums sortiert in Array a
Wiederholung des rekursiven Algorithmus (vergleiche Abschnitt "Sortieren mit Hilfe eines selbst-balancierenden Suchbaums"):
def treeSort(node,a):
if node is None:
return
treeSort(node.left,a)
a.append(node.key)
treeSort(node.right,a)
Dieser Algorithmus ist baumrekursiv, was nicht weiter überrascht, denn die Rekursion dient ja zur Traversierung eines Baumes. In diesem Fall führt Baumrekursion nicht zu exponentieller Komplexität, weil die Tiefe des Baum nur O(log N) ist. Dadurch benötigt treeSort nur O(2log N) = O(N) Schritte zum Auslesen des Baumes (das Füllen das Baumes benötigt allerdings O(N log N) Schritte und dominiert den Algorithmus).
Die Implementation als iterative Funktion erfolgt mit Hilfe eines Stacks und einer Hilfsfunktion traverseLeft, die den Stack füllt:
def treeSortIterative(root, a):
stack = []
traverseLeft(root, stack) # fülle Stack mit den Knoten des linken Teilbaums von root
while len(stack) > 0:
node = stack.pop()
a.append(node.key)
traverseLeft(node.right, stack) # fülle Stack mit den Knoten des linken Teilbaums von node.right
Hilfsfunktion:
def traverseLeft(node, stack):
while node is not None:
stack.append(node)
node = node.left
Auflösung rekursiver Gleichungen
Komplexitätsberechnung rekursiver Algorithmen
<math>\underbrace{T(n)}_{Anzahl der Befehle} = \underbrace{ a_1T\left(\frac{n}{b_1}\right)+a_2T\left(\frac{n}{b_2}\right)+\cdots+a_kT\left(\frac{n}{b_k}\right) }_{rekursives Teilproblem}
+\underbrace{f(n)}_{nicht-rekursiver Teil}</math>
Bemerkung: Aufrunden von <math>\lceil\frac{n}{b_i}\rceil</math> oder abrunden von <math>\lfloor\frac{n}{b_i}\rfloor</math> spielen für die Auflösung der Formeln i.a. keine Rolle.
Spezialfall: k = 1, d.h. alle Unterprobleme haben die gleiche Größe.
<math>T(n) = aT\left(\frac{n}{b}\right)+f(n)</math>
In diesem Fall muss folgender Rekursionsexponent eingeführt werden:
<math>\boldsymbol{\rho}=log_ba</math>
==> Master-Theorem
Master-Theorem
Fall 1:
<math>f(n) \in O(n^{\rho-\epsilon}) , \epsilon>0</math>
==> das bedeutet: die Kosten der Rekursion überwiegen
==><math>\boldsymbol{T(n) =\Theta(n^{\rho})}</math>
Fall 2:
<math>f(n) \in \Theta(n^{\rho}) </math>
==> das bedeutet: die Kosten von f und Rekursion addieren sich
==><math>\boldsymbol{T(n) =\Theta(n^{\rho}*logn})</math>
Fall 3:
<math>f(n) \in \Omega(n^{\rho+\epsilon})</math>
==> das bedeutet: die Kosten von f überwiegen
==><math>\boldsymbol{T(n) =\Theta(f(n))}</math>
es muß ausserdem noch gelten:
<math>a*f\left(\frac{n}{b}\right)\le c*f(n)</math> für c<1
Beispiel: Merge Sort
<math>T(n) = \underbrace{ 2T\left(\frac{1}{2}\right)}_{rekursiver Aufruf von MergeSort}+\underbrace {\Theta(n)}_{Merge}</math>
a=2, b=2 ==> <math>\rho=log_22 =1</math>
==> das ist Fall 2: <math>f(n) = \Theta(n) = O(n^{\rho}) </math>
==> Komplexität von MergeSort: <math>T(n) \in \Theta(n^\rho*logn) </math>
Fälle die nicht durch das Master-Theorem abgedeckt sind:
- wenn <math>k \ > 1</math>: rekursive Teilprobleme verschiedener Grösse
- wenn <math>f(n) \in O\left(\frac{n^\rho}{logn}\right)</math>
- wenn <math>f(n) \in \Omega\left(n^\rho*logn\right)</math>
Wo das Master-Theorem nicht anwendbar ist:
Beispiel ist die folgende Rekursion:
<math>T(n) = \underbrace{ T\left(\frac{n}{3}\right)}_{\frac{1}{3} der Daten}+\underbrace {T\left(\frac{2n}{3}\right)}_{\frac{2}{3} der Daten}+O(n)</math>
Rekursionsbaum:
n --> wächst mit c*n
/ \
/ \
/ \
/ \
/ \
(n/3) (2n/3)
/ \ / \
/ \ / \
/ \ / \
(n/9) (2n/9) (2n/9) (4n/9)
==> <math>c*\left(\frac{n}{9}+\frac{2n}{9}+\frac{2n}{9}+\frac{4n}{9}\right)=c*n</math>
Rekursion endet wenn: <math>\left(\frac{2}{3}\right)^d*n=1</math> wird, wobei d die Tiefe des Baums ist.
<math>n=\left(\frac{3}{2}\right) ---> d=log_\frac{3}{2}n</math>
Vermutung:
<math>T(n) \in O\left(log_\frac{3}{2}n*c*n\right)</math>
nach den Regeln der O-Notation ist das: 0(n*logn), d.h unsere Vermutung stimmt.
Ungleiche Aufteilung in Teilprobleme ändert nicht dei Komplexität, falls das Teilungsverhältnis konstant ist.
Beweis durch Substitution:
<math>T(n)\le T\left(\frac{n}{3}\right)+ T\left(\frac{2n}{3}\right)+ c\,n</math>
<math>\le d\left(\frac{n}{3}\,\log\frac{n}{3}\right)+ d\left(\frac{2n}{3}\,\log\frac{2n}{3}\right)+ c\,n</math>
<math> = d\frac{n}{3}\,\log n-d\,\frac{n}{3}\,\log 3+d\,\frac{2}{3}\,n\,\log n-d\,\frac{2}{3}\,n\,\log\frac{3}{2}+c\,n</math>
<math> = d\,n\,\log n-d\underbrace{\left( \frac{n}{3}\,\log 3+\frac{2n}{3}\,\log\frac{3}{2}\right) }_{\frac{n}{3}\,\log 3+\frac{2n}{3}\,\log 3-\frac{2n}{3}\,\log 2}+c\,n</math>
<math> = d\,n\,\log n-d\,n\left(\log 3-\frac{2}{3}\right)+c\,n</math>
<math> \le d\,n\,\log n</math> falls <math>c\,n-d\,n\left(\log 3-\frac{2}{3}\right)< 0</math>
<math> \Longleftrightarrow d \ge \frac{c}{\log 3-\frac{2}{3}}</math>
