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




Auswertung rekursiver FunktionenBearbeiten

In diesem Kapitel wird die Auswertung rekursiver Funktionen behandelt.

Erweiterung der FunktionsdefinitionBearbeiten

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

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:

 

DefiniertheitBearbeiten

Gegeben ist folgender Algorithmus:

 

Auf welchen Eingaben ist der Algorithmus definiert?

Auswertung:

 
 
 
 
  Diese Auswertung terminiert nicht!

Somit gilt:

 

LiteraturBearbeiten

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.