Iteration versus Rekursion

Definition 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 (oder mehreren) Funktion.

Beispiel einer indirekten Rekursion:

   foo  --->  bar  --->  foo
      ruft auf    ruft auf

entscheidende Punkte:

• jeder Aufruf von 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

z.B.:  f(n):            1.Ebene
          f(n-1):       2.Ebene
               f(n-2):  3.Ebene

Wenn wir jetzt die Funktion f(n) haben, dann ist es in wirklichkeit so als ob wir eine Funtion f1(n1), f2(n2), f3(n3) usw. haben.
Also eine Funktion f1, die die Variable n1 hat, eine Funktion f2, die die Variable n2 hat usw..
Beim Aufruf von der Funktion f2(n2) hätte n2 den Wert n1-1. Und f3(n3) hätte den Wert n2-1=n1-2
        
        def f(n)
       
        def f1(n1))
        def f2(n2)) ---> n2=n1-1
        def f3(n3)) ---> n3=n2-1 = n1-2

• jede rekursive Funktion muß mindestens ein 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, und fast nur, weil bei Rekursionen der Compiler abbricht wenn der Speicher voll ist --> Aufgabenblatt7 Übung1).

• Die Anzahl der rekursiven Aufrufe bis zum Rekursionsabschluss bezeichnet man als Rekursionstiefe d.

Arten der Rekursion

Die Arten der Rekursion ist hier nicht vollständig. Es gibt noch weitere Rekursionsarten. 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
  

=> das Ergebnis ist eine "Rekursionskette" die 1-dimensional ist

Baumrekursion

(auch Kaskadenrekursion)

• Baumrekursion ist das Gegenteil der linearen Rekursion
• mindestens ein Pfad enthält mindestens 2 rekursive Aufrufe.
  

Bedingung: und dieser Pfad wird O(d)-mal ausgeführt, wobei O(d) die Rekursionstiefe ist.
=> das Ergebnis ist ein "Rekursionsbaum", und der ist verzweigt.

  Nachteil: Falls dieser Pfad O(d)häufig ausgeführt wird, führt das zu exponentieller Komplexität des Algorithmus.

Course-of-values recursion

• 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).

primitiv Rekursion

• Hier ist p=1;
  

=> Das ist ein Spezialfall der linearen Rekursion.

Endrekursion

• Alle rekursiven Aufrufe sind der letzte Befehl vor dem return-Befehl.
  

=> Das ist ein Spezialfall der linearen Rekursion

Implementationen

Als Beispiel nehmen wir die Fibonacci-Zahl:
Definition: f₀=0, f₁=1,...., f_n=f_n-1+f_n-2
Es ergibt sich folgende Reihe: f_k=0, 1, 1, 2, 3, 5, 8, 13,....., (=>die Reihe wächst exponentiell an).

1. Version: Implementation Rekursiv - naive Implementation:

def fib1(n):                      # Funtion berechnet die n-te Fibonacci-Zahl
    if n <= 1: return n           # Rekursionsabschluss
    return fib1(n-1) + fib1(n-2)

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)

Das ist natürlich ein ungünstiger Algorithmus, weil wiederholte Berechnungen gemacht werden.
Aber einige Probleme sind echt Baumrekursiv, z.B. das Ausrechnen der möglichen Züge beim Schachspiel.

Es gilt folgender Satz:
Jeder rekursiver Algorithmus kann mit einem Stack in iterativen Algorithmus umgewandelt werden (d.h. mit einer Schleife statt einer Rekursion). Das bedeutet, dass die Rekursion gleichmächtig ist wie die Schleife, d.h. gleichmächtig wie die Turing-Maschine. Die Komplexität ändert sich nicht.

2. Version: iterartiv mit einem Stack

def fib2(n):
    stack = [n]   # unser Array
    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(-1)        # wenn etwas auf dem Stack liegt, dann nehme vom Stack herunter
          if k <= 1:               # Abschluss der Schleife
               f += k
          else:                    # Umwandlung der Rekursion in Iteration
               stack.append(k-1)   
               stack.append(k-2)
    return f

3. Version: Course-of-values

Fibonacci ist Course-of-values rekursiv (folgt unmittelbar aus der Definition) mit p=2.

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:

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 f1+f2 und die vorherige (f1) zurück

==> Diese Implementation ist jetzt linear-rekursiv und hat damit auch lineare Komplexität und nicht exponentielle wie die vorherigen Versionen.

Es gilt folgender Satz:
Jede Course-of-values Rekursion kann in Endrekursion umgewandelt werden.

4. Version: Endrekursiv

def fib4(n)
    if n == 0: return 0    
    else:                    
       return fib4Impl(0,1,n) 

Die Hilfsfunktion:

def fib4Impl(f1,f2,n)
    if n == 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=2:

	f1	f2	n	return
fib4Impl 1.Aufruf	0	1	2	1
fib4Impl 2.Aufruf	1	1	1	1

==> Ergebnis von 2.Fibonacci-Zahl ist: 1

Es gilt folgender Satz:
Jede endrekursive Funktion kann ohne Stack in eine iterative Funtion umgewandelt werden.

5. Version: iterativ ohne Stack

def fib5(n):
    if n == 0: return 0
    f1,f2 = 0,1
    k = 1
    while k < n:
        f1,f2 = f2,f1+f2
        k += 1
    return f2

Das ist genau das gleiche wie fib4 nur das bei fib4 das n rückwärts gezählt wird und hier das k vorwärts. Das könnte man auch so schreiben:

while n > 0:
  f1,f2 = f2,f1+f2
  n -= 1

Beispiel: treeSort

Input:
-ein balancierter Binärbaum root
-ein leeres dynamisches Array a

Aufgerufen wird: treeSort(root,a) # kopiert Elemente des Baums sortiert in Array a

Wiederholung:

def treeSort(node,a):
   if node is None: return
   treeSort(node.left,a)
   a.append(node.key)
   treeSort(node.right,a)

Implementation als iterative Funktion:

def treeSortIterative(node,a):
   stack = []
   traverseLeft(node,stack)   # Hilfsfuntion, füllt Stack
   while len(stack) > 0:
       node = stack.pop(-1)
       a.append(node.key)
       traverseLeft(node.right,stack)

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}*logn-d*\frac{n}{3}*log3+d*\frac{2}{3}*n*logn-d*\frac{2}{3}*n*log\frac{3}{2}+c*n</math>

<math> = d*n*logn-d\underbrace{\left( \frac{n}{3}*log3+\frac{2n}{3}*log\frac{3}{2}\right) }_{\frac{n}{3}*log3+\frac{2n}{3}*log3-\frac{2n}{3}*log2}+c*n</math>

<math> = d*nlogn-d*n\left(log3-\frac{2}{3}\right)+c*n</math>

<math> \le d*nlogn</math> falls <math>c*n-d*n\left(log3-\frac{2}{3}\right)< 0</math>

<math> \Longleftrightarrow  d \ge \frac{c}{log3-\frac{2}{3}}</math>