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

Aus Wikiversity
Zur Navigation springen Zur Suche springen




Auswertung rekursiver Funktionen[Bearbeiten]

In diesem Kapitel wird die Auswertung rekursiver Funktionen behandelt.

Erweiterung der Funktionsdefinition[Bearbeiten]

  • 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:


Die Auswertung dieser Funktion lautet:

Auswertung rekursive Funktionsdefinition[Bearbeiten]

Gegeben ist folgende rekursive Funktion:


Die Auswertung dieser Funktion lautet:

Hier greift die erste Zeile der Funktionsdefinition. Da x=0 ist nehmen wir y


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.


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 wir und es lässt sich allgemein sagen:


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

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.


...

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

Definiertheit[Bearbeiten]

Gegeben ist folgender Algorithmus:

Auf welchen Eingaben ist der Algorithmus definiert?

Auswertung:

Diese Auswertung terminiert nicht!

Somit gilt:

Literatur[Bearbeiten]

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.


R-0 Discussion R-3