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

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):=ifg(x,y)thenh(x+y)elseh(x-y)$

$g(x,y):=(x==y)\vee odd(y)$

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

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

Die Auswertung dieser Funktion lautet:

$f(1,2)\to ifg(1,2)thenh(1+2)elseh(1-2)$

$\to if1==2\vee odd(2)thenh(1+2)elseh(1-2)$

$\to if1==2\vee falsethenh(1+2)elseh(1-2)$

$\to iffalse\vee falsethenh(1+2)elseh(1-2)$

$\to iffalsethenh(1+2)elseh(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):=ifx=0thenyelse($

$ifx>0thenf(x-1,y)+1$

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

Die Auswertung dieser Funktion lautet:

$f(0,y)\to yfueralley$ 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+nfuerallen\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+yfuerallex,y\in int$

Definiertheit

Gegeben ist folgender Algorithmus:

$f(x):=ifx==0then0elsef(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\mathrm{\forall }x\in int,x>0$

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

Somit gilt:

$f(x):=\{\begin{array}{cc}0& fallsx\ge 0\\ \mathrm{\perp }& sonst\end{array}$

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.