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.