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

Beispiele

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

der Rest kommt nach