Wikipedia · einfach zusammengefasst · Stand
Abstiegsfunktion
Eine Abstiegsfunktion ist in der Mathematik und in der Informatik eine Funktion, mit der nachgewiesen werden kann, dass eine Rekursion terminiert.
Inhalt4 Abschnitte
Bedeutung und Grundidee
Eine Abstiegsfunktion ist in Mathematik und Informatik ein Hilfsmittel, um zu beweisen, dass eine rekursive Funktion oder Methode terminiert, also nach endlich vielen Aufrufen endet. Sie ordnet jeder Eingabe einen Wert zu, der bei jedem rekursiven Aufruf kleiner wird. Da dieser Wert nicht unbegrenzt weiter sinken kann, sind nur endlich viele Rekursionsschritte möglich.
Nachweis der Terminierung
Zu einer rekursiven Funktion f\colon A\to B wird eine Abstiegsfunktion g\colon A\to D gewählt. Häufig ist D=\mathbb{N}. g(x) kann zum Beispiel die Anzahl der noch verbleibenden Rekursionsschritte beschreiben.
Benötigt die Berechnung von f(x) einen weiteren Aufruf f(x'), muss gelten: g(x')<g(x). Statt der Ordnung < in \mathbb{N} kann jede wohlfundierte Relation verwendet werden. Wohlfundiert bedeutet hier, dass es ein Minimum gibt: Zu einem Wert kann nicht unbegrenzt immer noch ein kleinerer Wert gefunden werden. Weil g bei jedem Rekursionsschritt sinken muss, kann die Rekursion deshalb nicht unendlich fortgesetzt werden.
Mathematisches Beispiel
Gegeben ist
f\colon\mathbb{Z}\to\mathbb{Z}, mit f(x)=f(x-1)+x für x>13 und f(x)=0 sonst.
Als Abstiegsfunktion wird g(x)=x-13 gewählt. Im rekursiven Aufruf gilt x'=x-1. Daher ist g(x-1)<g(x), denn (x-1)-13<x-13. Der Wert der Abstiegsfunktion sinkt also in jedem Rekursionsschritt. Da er in \mathbb{N} nicht endlos sinken kann, terminiert die Rekursion.
Beispiel in Java
Die Java-Methode triangle(String s) gibt zunächst die Zeichenkette s aus. Ist ihre Länge höchstens 1, endet die Methode. Andernfalls ruft sie sich mit s.substring(1) erneut auf, also mit der Zeichenkette ohne ihr erstes Zeichen.
Für die Eingabe „Hallo!“ lautet die Ausgabe: „Hallo!“, „allo!“, „llo!“, „lo!“, „o!“, „!“. Als Abstiegsfunktion dient die Länge der Zeichenkette. Bei jedem rekursiven Aufruf wird ein Zeichen entfernt; die Länge sinkt somit um 1. Weil die Länge nicht unter 0 sinken kann und spätestens bei einer Länge von 1 die Rückkehr erfolgt, terminiert triangle für alle Eingaben.