Programmieren

Im Grunde ist im Artikel über Funktionen das Wesentliche über Funktionen gesagt – mit einer Ausnahme: rekursive Funktionen. Rekursivität ist eines der mächtigsten Mittel beim Programmieren: Rekursivität ermöglicht einfache Programme, deren Korrektheit oft bereits aus einer geeigneten, ebenfalls rekursiven Spezifikation des Problems ersichtlich ist.

Vorher aber geht es noch um die in vielen Programmier­sprachen vorhandene Möglichkeit, den gleichen Funktions­namen für verschiedene, aber ähnliche Funktionalitäten zu vergeben, das sogenannte Überladen des Funktions­namens.

Und ferner geht es noch um Funktionen mit variabler Anzahl von Parametern – eine praktische Sache in manchen Fällen.

Überladen von Funktionsnamen

Gleiche Namen für Verschiedenes

Die Bank vor der Bank – aus dem Zusammenhang lässt sich erahnen, dass mit der ersten Bank eine Sitzgelegenheit und mit der zweiten Bank ein Geldinstitut gemeint ist. Wenn zwei unterschiedliche Dinge mit dem gleichen Namen bezeichnet werden, kann die Unter­scheidung nur aus dem Zusammenhang, dem Kontext, erfolgen.

Bei dem Namen Bank ist es zufällig, dass damit zwei völlig unterschiedliche Dinge gemeint sind. Oft aber wird der gleiche Name absichtlich auch für Unter­schiedliches gewählt, etwa Anhänger. Ein Anhänger kann an einem Auto hinten an hängen, oder aber er kann ein Mensch sein, der einer politischen Partei anhängt. Das Anhängen ist in beiden Fällen gegeben. Aus dem Kontext ist jedoch ersichtlich, welcher Anhänger gemeint ist.

Überladen in Java

In diesem letzteren Sinne werden auch in der Pro­grammierung häufig Funktionen, die Ähnliches tun, mit dem gleichen Namen versehen. Beispiels­weise ist es sinnvoll, eine Funktion, die das Maximum von mehreren Zahlen berechnet, immer mit dem Namen max zu bezeichnen, ganz gleich, ob sie das Maximum von zwei, drei, vier oder mehr Zahlen berechnet.

Gleicher­maßen ist es sinnvoll, die Funktion max zu nennen, ganz gleich, ob sie das Maximum von zwei ganzen Zahlen oder von zwei Kommazahlen berechnet.

In Java ist dies möglich. Die Verwendung des gleichen Funktions­namens für unterschiedliche Funktionen wird als Überladen (engl.: overloading) bezeichnet.

Im Folgenden sind drei Versionen der Funktion max angegeben. Java entscheidet beim Aufruf anhand der Anzahl und des Typs der Parameter, welche der drei Funktions­definitionen verwendet wird.

Beim Aufruf von max(3, 4) wird die erste Funktions­definition verwendet, beim Aufruf von max(3, 4, 2) die zweite (die wiederum intern die erste aufruft), beim Aufruf von max(3.0, 4.0) die dritte. Und beim Aufruf von max(3, 4.0) ?

Dann wird der ganzzahlige Wert 3 automatisch in die Kommazahl 3.0 umgewandelt, und es wird die dritte Funktions­definition angewendet.

Funktionen mit variabler Anzahl von Parametern

Was ist aber, wenn das Maximum von vier ganzzahligen Werten berechnet werden soll? Es gibt keine Funktion int max(int a, int b, int c, int d).

Aber es gibt die Möglichkeit, eine variable Anzahl von Parametern gleichen Typs vorzusehen. Die Syntax hierfür geht aus dem folgenden Beispiel hervor. Der Parameter a wird im Funktions­körper wie ein Array behandelt.

Und wenn gleichzeitig noch die Funktion int max(int a, int b) vorhanden ist? Welche Funktions­definition wird verwendet, wenn max(3, 4) aufgerufen wird? Dann wird die speziellere Funktions­definition, in diesem Fall also int max(int a, int b), verwendet.

Rekursive Funktionen

Innerhalb einer Funktions­definition kann ein Aufruf derselben Funktion vorkommen. Eine Funktion kann sich also selbst aufrufen. Man bezeichnet eine solche Funktion als rekursive Funktion.

So lässt sich beispiels­weise für n ∈ ℕ₀ die n-te Potenz einer Zahl a rekursiv wie folgt definieren:

a n  =

1     falls n = 0 a · a n-1     sonst

Diese Definition lässt sich unmittelbar in eine rekursive Funktion umsetzen:

Im Funktions­körper der Funktion exp kommt ein Aufruf der Funktion exp vor, d.h. die Funktion ruft sich selbst auf.

Denn um aⁿ zu berechnen, muss zunächst einmal a^n-1 berechnet werden. Und um a^n-1 zu berechnen, muss zunächst a^n-2 berechnet werden usw.

Aufrufstack

Um zu verstehen, wie eine rekursive Funktion arbeitet, betrachten wir den Funktions-Aufrufstack. Ein Stack ist ein Speicher, der wie ein Stapel von Tellern im Küchen­schrank funktioniert: Der Teller, der als letzter auf den Stapel gelegt wurde, wird als erster wieder weggenommen.

Wenn irgendwo in einem Programm die Funktion exp(10, 3) aufgerufen wird, um die Zahl 10³ = 1000 zu berechnen, dann wird, wie bei jedem Funktions­aufruf, als erstes die Rücksprung­adresse auf dem Stack abgelegt. Die Rücksprung­adresse ist der Ort im Programm, von dem aus die Funktion aufgerufen wird. Dort wird dann, wenn die Funktion fertig mit ihrer Berechnung ist, mit dem Wert 1000 weitergearbeitet.

Nachdem die Rücksprung­adresse auf dem Stack gespeichert ist, werden als nächstes die formalen Parameter, in diesem Fall a und n, auf dem Stack abgelegt und mit den Werten der aktuellen Parameter, in diesem Fall 10 und 3, initialisiert. Dann springt das Programm in den Funktions­körper und beginnt die dort befindlichen Anweisungen abzuarbeiten. Sofern dort lokale Variablen deklariert sind, werden diese ebenfalls auf dem Stack abgelegt.

Der Stack enthält also zunächst folgende Einträge:

Hierbei bezeichnet R die Rücksprung­adresse, die hier mit dem fiktiven Wert 12345 belegt ist.

Wenn das Programm bei der Abarbeitung des Funktions­körpers an die Stelle des Aufrufs exp(a, n-1) gelangt, wird erneut die jetzt aktuelle Rücksprung­adresse 67890 auf dem Stack abgelegt, und anschließend die formalen Parameter a und n mit den Werten der jetzigen aktuellen Parameter, also 10 und 2.

Wenn das nächste Mal der Aufruf exp(a, n-1) erreicht wird, geschieht erneut das Gleiche, nun mit den aktuellen Parametern 10 und 1

Beim nächsten Mal hat der Stack folgenden Inhalt:

Wenn dann die Funktion wieder abgearbeitet wird, ist n = 0 und die Funktion gibt mit return den Wert 1 zurück. Dies führt dazu, dass die Funktion an die Rücksprung­adresse 67890 zurückkehrt und dort den Wert 1 abliefert. Die obersten drei Einträge werden aus dem Stack gelöscht.

Technisch gesehen wird beim Aufruf von exp(a, n-1) im Funktions­körper die Rücksprung­adresse an diesen Ort im Stack gespeichert, dann wird an den Anfang der Funktion gesprungen und es werden die Werte der aktuellen Parameter, also a und n-1, an die formalen Parameter a und n übergeben. Dann fängt die Funktion an zu rechnen, bis sie wieder auf den Aufruf exp(a, n-1) stößt. Dann beginnt das Spiel von vorne.

Wichtig ist, dass dies nicht unendlich lange so weitergeht. Sondern es muss, ähnlich wie bei Programm­schleifen, eine Abbruch­bedingung geben. Im obigen Fall ist diese Abbruch­bedingung dann gegeben, wenn n den Wert 0 erreicht hat.

Würde man die Funktion exp mit negativem Parameter n aufrufen, dann käme es zu einer unendlichen Aufrufkette, weil nie die Abbruchbedinging n=0 erreicht wird. Der Computer bricht irgendwann die Berechnung mit der Fehler­meldung stack overflow ab.

Aufgaben

Aufgabe 1:  Setzen Sie folgende rekursive Definition der Fakultäts­funktion in eine rekursive Java-Funktion um.

n!  =

1     falls n = 0 (n-1)! · n     sonst