Kurs:Algorithmen und Datenstrukturen/Vorlesung/Auswertung von rekursiven Funktionen

Startseite

Vorlesung

1.Einleitung

2. Theoretische Grundlagen

2.1 Programmierparadigmen

2.2. Laufzeitanalysen

2.3. Entwurfsmuster

3. Suchen

3.1 Suchen in sortierten Folgen

3.2 Suchen in Texten

4. Sortieren

4.1 Algorithmen für vergleichsbasiertes Sortieren

4.2 Weitere Sortierprobleme

5. Dynamische Datenstrukturen

5.1 Binäre Suchbäume

5.2 AVL Bäume

5.3 2-3-4-Bäume und Rot-Schwarz Bäume

5.4 Heaps

5.5 Hashtabellen

6. Graphen

6.1 Einführung

6.2 Breitensuche

6.3 Tiefensuche

6.4 Topologisches Sortieren

6.5 Berechnung kürzester Wege

6.6 Berechnung maximaler Flüsse

6.7 Spannbäume

7. Optimierung

7.1 Grundlagen

7.2 Kombinatorische Optimierung

7.4 Lineare Optimierung

7.5 Simplex Verfahren

Auswertung rekursiver Funktionen

In diesem Kapitel wird die Auswertung rekursiver Funktionen behandelt.

Erweiterung der Funktionsdefinition

• Erweiterung der Definition von Termen
• Neu: Aufrufe definierter Funktionen sind Terme
• Eine Funktionsdefinition f heißt rekursiv, wenn direkt oder indirekt (über andere Funktionen) ein Funktionsaufruf f(...)in ihrer Definition auftritt.

Gegeben ist die folgende Funktion:

$f(x,y):=~if~g(x,y)~then~h(x+y)~else~h(x-y)$

$g(x,y)~:=~(x==y)~\lor ~odd(y)$

$h(x)~:=~j(x+1)*j(x-1)$

$j(x)~:=~2x-3$

Die Auswertung dieser Funktion lautet:

$f(1,2)~\to ~if~g(1,2)~then~h(1+2)~else~h(1-2)$

$\to ~if~1==2~\lor ~odd(2)~then~h(1+2)~else~h(1-2)$

$\to ~if~1==2~\lor ~false~then~h(1+2)~else~h(1-2)$

$\to ~if~false~\lor ~false~then~h(1+2)~else~h(1-2)$

$\to ~if~false~then~h(1+2)~else~h(1-2)$

$\to ~h(1-2)$

$\to ~h(-1)$

$\to ~j(-1+1)*j(-1-1)$

$\to ~j(0)*j(-1-1)$

$\to ~j(0)*j(-2)$

$\to ~(2*0-3)*j(-2)$

$\to ~(-3)*(-7)$

$\to ~21$

Auswertung rekursive Funktionsdefinition

Gegeben ist folgende rekursive Funktion:

$f(x,y):=if~x=0~then~y~else($

$if~x>0~then~f(x-1,y)+1$

$else~-f(-x,-y))$

Die Auswertung dieser Funktion lautet:

$f(0,y)\to y~fuer~alle~y$ Hier greift die erste Zeile der Funktionsdefinition. Da x=0 ist nehmen wir y

$f(1,y)\to f(0,y)+1\to y+1$ Hier greift die zweite Zeile der Funktionsdefinition. Da x>0 ist haben wir f(1-1,y)+1. Da x nach diesem Schritt null ist, greift nun die erste Zeile und wir erhalten y+1.

$f(2,y)\to f(1,y)+1\to (y+1)+1\to y+2$ Hier greift ebenfalls die zweite Zeile der Funktionsdefinition. Da x>0 ist haben wir f(2-1,y)+1. Anschließend wenden wir noch einmal die zweite Zeile an, da x immer noch größer ist als null und wir erhalten f(1-1,y+1)+1. Da x nun null ist greift die erste Zeile der Funktionsdefinition und wir erhalten y+2.

...

Hier lässt sich bereits abschätzen, dass das Ergebnis der Funktion immer weiter hochgezählt wird und es lässt sich allgemein sagen:

$f(n,y)\to y+n~fuer~alle~n\in int,~n>0$

Ist unser x negativ, entwickelt sich die Auswertung wie folgt:

$f(-1,y)\to -f(1,-y)\to -(-y+1)\to y-1$ Hier greift die dritte Zeile der Funktionsdefinition. Da x<0 ist werden die Vorzeichen umgekehrt. Nun, da x=1 ist, greift die zweite Zeile und wir erhalten -f(1-1,-y)+1. Da x nun null ist greift wieder die erste Zeile und wir erhalten y-1.

$f(-2,y)\to -f(2,-y)\to -f(1,-y)+1\to -(-y+2)\to y-2$

...

Auch hier lässt sich bereits abschätzen, wie sich die Funktion einwickelt und es lässt sich allgemein sagen:

$f(x,y)\to x+y~fuer~alle~x,y\in int$

Definiertheit

Gegeben ist folgender Algorithmus:

$f(x):=if~x==0~then~0~else~f(x-1)$

Auf welchen Eingaben ist der Algorithmus definiert?

Auswertung:

$f(0)\to 0$

$f(1)\to f(0)\to 0$

$f(2)\to f(1)\to f(0)\to 0$

$f(x)\to 0\forall x\in int,x>0$

$f(-1)\to f(-2)\to ...$ Diese Auswertung terminiert nicht!

Somit gilt:

$f(x):=\left\{{\begin{array}{ll}0&falls~x\geq 0\\\bot &sonst\end{array}}\right.$

Literatur

Da die Vorlesungsinhalte auf dem Buch Algorithmen und Datenstrukturen: Eine Einführung mit Java von Gunter Saake und Kai-Uwe Sattler aufbauen, empfiehlt sich dieses Buch um das hier vorgestellte Wissen zu vertiefen. Die auf dieser Seite behandelten Inhalte sind in Kapitel 3.2.4 zu finden.