Spezielle Konzepte der strukturierten Programmierung in C++: call by reference, Rekursion, Function Templates

Funktionsaufrufe können in C++ entweder mit call by value oder call by reference realisiert werden; beide werden vorgestellt und diskutiert. Rekursionen ermöglichen oft schlanke Quelltexte, die aber schwerer verständlich sind als die entsprechende Implementierung mit Schleifen; einige Beispiele sollen an die Verwendung von Rekursionen heranführen. Die sogenannten Function Templates werden in der C++-Standard-Bibliothek oft eingesetzt; sie sind in einem gewissen Sinn eine Verallgemeinerung des Überladens von Funktionen.

walter

06 Jun. 2018

Function Templates strukturierte Programmierung call by value call by reference Rekursion C++ Referenz

Inhaltsverzeichnis

Einordnung des Artikels

Einführung in die Informatik
- C++: Fortgeschrittene Syntax
  - Spezielle Konzepte der strukturierten Programmierung in C++: call by reference, Rekursion, Function Templates

In den beiden vorhergehenden Kapiteln C++: Strukturierte Programmierung mit Funktionen und Weitere Konzepte der strukturierten Programmierung in C++: Einsatz von Vektoren, Gültigkeitsbereiche wurde ein kleines Statistik-Projekt vorbereitet. Mit diesem wird hier weitergearbeitet und daran werden die neuen Konzepte erläutert.

Call by value und call by reference

Funktionsaufruf mit call by value

Mit dem Verständnis für die Gültigkeitsbereiche von Variablen (siehe Der Gültigkeitsbereich einer Variable (''scope'') im Kapitel Elementare Syntax: Schleifen) ist auch besser zu verstehen, was beim Aufruf einer Funktion geschieht.

Die Funktion mean() soll wieder folgendermaßen implementiert sein:

// Implementierung der Funktion mean()
double mean(double x1, double x2)                           
{
    double mean = (x1 + x2) / 2;
    return mean;
}

Was passiert beim Aufruf der Funktion mean() — etwa aus der main()-Methode heraus — durch:

double meanValue = mean(1, 7);

Die Abarbeitung der main()-Methode unterbricht und im Prozessor wird die Funktion mean() abgearbeitet. Damit dies geschehen kann, müssen aber zunächst die beiden lokalen Variablen x1 und x2 mit den Werten 1 und 7 belegt werden. Das heißt aber nichts anderes als dass diese Werte in die entsprechenden Register kopiert werden müssen. Man nennt diesen Mechanismus eines Funktionsaufrufes, der immer mit dem Kopieren von Werten verbunden ist, call by value.

Oben wurde aber auch schon mit der überladenen Funktion mean() gearbeitet, die auch in folgender Version verwendet wurde (hier nur die Deklaration):

// Berechnet den Mittelwert eines Vektors (Zufallsfolge randomSequence = rs)
double mean(std::vector<int> rs);

Beim Aufruf dieser Funktion muss ein Vektor kopiert werden.

Funktionsaufruf mit call by reference

Der Mechanismus call by value stößt irgendwann an seine Grenzen: Werden beim Aufruf einer Funktion sehr große Objekte übergeben (groß in dem Sinn, dass sie viel Speicherplatz belegen), ist dies immer mit aufwendigen Kopiervorgängen verbunden. Gibt es dafür eine effektivere Lösung?

Am Beispiel der swap()-Funktion soll nun ein anderer Mechanismus vorgestellt werden. Die swap()-Funktion wurde bisher nur im Pseudocode vorgestellt (siehe Lösung der Aufgabe zum Sortieren dreier Zahlen in Lösungshinweise zu den Aufgaben aus Bedingung, Alternative und Mehrfachalternative). Sie dient dem Vertauschen der Werte zweier Variablen:

int a {1};
int b {2};

swap(a, b);

cout << a << endl;          // 2
cout << b << endl;          // 1

Das Beispiel zeigt, wie man die swap()-Funktion einsetzen möchte: Nach ihrem Aufruf (Zeile 4) sind die Werte von a und b vertauscht (Zeile 6 und 7). Doch wie wird die swap()-Funktion realisiert?

Der Mechanismus call by value kopiert die Werte von a und b in den Funktions-Körper von swap(); aber von dort aus können die Variablen a und b (aus Zeile 1 und 2, also im Gültigkeitsbereich außerhalb der swap()-Funktion) nicht verändert werden.

Die Implementierung der swap()-Funktion sieht folgendermaßen aus:

void swap(int & x, int & y){

    int temp;
    temp = x;
    x = y;
    y = temp;
}

Dass die Eingabewerte hier vom Datentyp int sind ist irrelevant, man könnte auch double oder beliebige andere Datentypen wählen.

Das wirklich Neue an der Funktion swap() sind die & -Zeichen in der Parameter-Liste, die bisher noch nicht besprochen wurden (Zeile 1); das & -Zeichen hat nichts mit dem logischen UND zu tun. Man sollte

int & x

folgendermaßen lesen: x ist eine Referenz auf eine int-Variable, nämlich diejenige Variable, die beim Aufruf der Funktion swap() an erster Stelle in den runden Klammern stand.

Gemeint ist damit, dass durch den Aufruf von swap(a, b) wie im Beispiel oben, die Möglichkeit geschaffen wird, im Funktionskörper von swap() auf die Variablen a und b zuzugreifen, die eigentlich ihren Gültigkeitsbereich außerhalb der Funktion haben. Die beiden Variablen x und y, mit denen im Funktionskörper von swap() gearbeitet wird, sind also Stellvertreter für a und b; man sagt daher auch, eine Referenz ist ein Alias-Name für eine Variable, als ein neuer Name, unter dem die Variable angesprochen werden kann.

Man muss sich an dieser Stelle unbedingt klarmachen, dass die Berechnungen, die im Funktionskörper von swap() mit x und y ausgeführt werden, die Variablen a und b verändern. Jedes Erzeugen von Referenzen muss also gut bedacht sein, da man damit Seiteneffekte erzeugen kann, die womöglich unerwünscht sind. Gerade bei verschachtelten Funktionsaufrufen kann man leicht die Kontrolle verlieren, welche Variable durch welche Aktion verändert wird.

Und man beachte, dass am Aufruf einer Funktion niemals erkennbar ist, ob es sich um call by reference oder call by value handelt; je nachdem besteht die Möglichkeit, dass im Funktionskörper die Variablen aus dem Funktionsaufruf verändert werden oder nicht. Mit welchem Mechanismus eine Funktion arbeitet erkennt man nur an der Deklaration der Funktion (die Argumente, die ein & -Zeichen enthalten, sind Referenzen).

Nachdem geklärt ist, was unter einer Referenz auf eine Variable zu verstehen ist, ergibt sich sofort, dass eine Funktion wie swap() nur mit Variablen aber niemals mit Zahlen aufgerufen werden kann:

int a {1};
int b {2};

swap(a, b);         // korrekt
swap(1, 2);         // Compiler-Fehler

Zeile 4: korrekter Aufruf mit Variablen, deren Werte vertauscht werden.

Zeile 5: Zahlen entsprechen nicht dem Datentyp, der für die Argumente der swap()-Funktion verlangt wird.

Man beachte den Unterschied zu einer Funktion, die den Aufruf der Argumente mit call by value realisiert, wie zum Beispiel die mehrfach diskutierte Funktion mean() zur Mittelwert-Berechnung:

int a {1};
int b {2};

mean(a, b);         // korrekt
mean(1, 2);         // korrekt

Hier sind beide Aufrufe syntaktisch korrekt.

Nach dem was früher zum Überladen von Funktionen geasgt wurde, könnte man erwarten, dass zusätzlich zur oben definierten swap()-Funktion eine weitere Funktion mit anderer Signatur angeboten werden darf:

void swap(int & x, int & y);
void swap(int x, int y);

Dies ist nicht erlaubt, da jetzt der Aufruf der swap()-Funktion nicht mehr eindeutig ist, wenn er mit zwei Variablen erfolgt.

Einsatz von call by reference

Zugriff auf Variable außerhalb der Funktion

Die swap()-Funktion oben war ein erstes Beispiel, wie man den Mechanismus call by reference einsetzen kann (oder muss): möchte man aus einer Funktion heraus auf außerhalb definierte Variable zugreifen, müssen diese Variablen per Referenz an die Funktion übergeben werden. Die Gefahr dabei ist natürlich, dass man Seiteneffekte erzeugt, die nicht erwünscht oder schwer kontrollierbar sind.

Vermeiden von Kopiervorgängen

Der Einsatz von call by reference wird dann empfohlen, wenn man Kopiervorgänge vermeiden möchte.

Beispiel:

Es wurde schon mehrfach die Mittelwert-Berechnung mit Hilfe der Funktion mean() besprochen:

double mean(double x1, double x2)
{
    return (x1 + x2) / 2;
}

Man möchte diese Funktion eventuell anbieten als eine Mittelwert-Berechnung für zwei Vektoren (Implementierung angedeutet):

vector<double> mean(vector<double> x1, vector<double> x2)
{
    // neuen Vektor v definieren
    // Mittelwert komponentenweise berechnen und den Komponenten von v zuordnen
    // return v;    
}

Um die Kopiervorgänge zu vermeiden, kann man dies auch mit call by reference realisieren:

// Mittelwert zweier Vektoren mit call by reference
void mean(vector<double> & x1, vector<double> & x2, vector<double> & result)
{
    int n = x1.size();                  // besser: alle drei Dimensionen abfragen und n = Minimum setzen
    for (int i = 0; i < n; i++)
    {
        result[i] = mean(x1[i], x2[i]);         // Rückgriff auf die bekannte mean()-Funktion
    }
}

// Aufruf in main():
vector<double> x {1, 3, 5};             // Initialisierungsliste für Vektor x
vector<double> y {5, 3, 1};             // Initialisierungsliste für Vektor y

vector<double> m(3);                    // Deklaration des Vektors, der den Mittelwert annehmen soll

mean(x, y, m);                  // m = (3, 3, 3)

Zur Erklärung:

Die neue mean()-Funktion besitzt jetzt drei Eingabewerte, die alle als Referenzen auf Vektoren definiert sind (Zeile 2).
In der Implementierung werden diese drei Vektoren behandelt wie bereits definierte Vektoren (dass es sich um Referenzen handelt, ist nicht zu erkennen).
Es wird kein Rückgabewert berechnet, dieser ist in der Referenz des Vektors result enthalten; der Vektor wird in Zeile 7 mit neuen Werten belegt.
In Zeile 7 wird dazu auf die bereits bekannte mean()-Funktion zurückgegriffen, die hier nicht nochmal aufgeführt wird.
Zum Aufruf der neuen mean()-Funktion werden zuerst zwei Vektoren initialisiert (mit Hilfe der Initialisierungsliste, Zeile 12 und 13).
Der Vektor m, der später den Mittelwert der beiden Vektoren x und y repräsentieren soll, wird nur deklariert, aber nicht initialisiert (Zeile 15).

Das Schlüsselwort const: Vermeidung von Seiteneffekten

Die drei Vektoren x1, x2, result in der Funktion mean() oben unterscheiden sich grundlegend:

Auf die Vektoren x1 und x2 wird nur lesend zugegriffen, sie werden während der Abarbeitung der Befehle von mean() nicht verändert.
Dagegen wird auf result schreibend zugegriffen: der Vektor wird sogar erst innerhalb von mean() initialisiert. Und diese Initialisierung muss dort sichtbar werden, von wo aus die Funktion mean() aufgerufen wurde.

Um diesen Unterschied auszudrücken und vor allem um zu vermeiden, dass innerhalb von mean() die Vektoren x1 und x2 verändert werden, kann man x1 und x2 in der Definition on mean() als const kennzeichnen:

void mean(const vector<double> & x1, const vector<double> & x2, vector<double> & result);            // Deklaration von mean()

Versucht man jetzt in der Implementierung von mean() schreibend auf eine der const-Variablen zuzugreifen, erhält man einen Compiler-Fehler (siehe Zeile 7 unten); man kann so unerwünschten Seiteneffekten vorbeugen.

void mean(const vector<double> & x1, const vector<double> & x2, vector<double> & result)
{
    int n = x1.size();
    for (int i = 0; i < n; i++)
    {
        result[i] = mean(x1[i], x2[i]);
        x1[i] = 0;                  // Compiler-Fehler: Zuweisung an read-only-Variable
    }
}

Rekursion

Bisher wurden Funktionen so eingesetzt, dass ihnen Konstanten (meist Zahlen) oder Variablen übergeben werden. Wenn es der Prototyp der Funktion erlaubt, kann natürlich eine Funktion auch sich selbst aufrufen; man spricht in diesem Fall von einer rekursiven Funktion oder kurz Rekursion.

Die Fakultät

Paradebeispiel einer rekursiven Funktion ist die Fakultät, die für natürliche Zahlen definiert ist:

n! = n · (n - 1)!

Diese Formel sieht zunächst nichtssagend aus. Ergänzt man sie aber um eine Abbruchbedingung:

n! = n · (n - 1)! , 1! = 1,

so sieht man leicht (indem man die Formel immer wieder in sich selbst einsetzt, bis man bei 1 ankommt), dass die Fakultät auch iterativ berechnet werden kann:

n! = n · (n - 1) · ... · 2 · 1.

Man kann dieses sich selbst Aufrufen einer Funktion auch in C++ realisieren:

int factorial(int n)
{
    if (n == 1)
        return 1;
    
    return n * factorial(n - 1);
}

Umwandlung einer Dezimalzahl in eine Dualzahl

Rekursionen können Fluch und Segen zugleich sein: Einerseits lassen sich viele Algorithmen sehr kurz implementieren, andererseits entstehen dabei oft Quelltexte, die ohne ausführlichen Kommentar nicht zu verstehen sind.

Die folgende Funktion decToBin() wandelt eine gegebene Dezimalzahl in eine Dualzahl um; die Dualzahl wird sofort auf der Konsole ausgegeben und nicht als Variable abgespeichert.

#include <iostream>
using namespace std;

void decToBin(int n)
{
    if (n < 2)
    {
        cout << n;
        return;
    }

    decToBin(n / 2);
    cout << n % 2;
}

Aufgaben:

1. Trockentest: Führen Sie de Berechnungen der Funktion decToBin() für n = 13 am Schreibtisch durch!

2. Warum liefert das Programm die falsche Ausgabe, wenn Zeile 12 und 13 vertauscht werden? Machen Sie wieder den Trockentest!

3. Schreiben Sie das entsprechende Programm, das eine Dezimalzahl in eine Oktalzahl (Basis 8) verwandelt!

Berechnung der Determinante mit dem Laplaceschen Entwicklungssatz

Der Laplacesche Entwicklungssatz reduziert das Problem der Berechnung einer Determinante (einer n × n-Matrix A) auf die Berechnung von n (kleineren) Determinanten (jetzt von (n - 1) × (n - 1)-Matrizen). Bei der Entwicklung nach der ersten Spalte entsteht folgende Rekursionsformel:

det (A) = ∑_k (-1)^k+1 · a_k1 · det (A_k1)

(der Summationsindex k läuft von 1 bis n)

Dabei ist a_k1 das Element der Matrix A in der k-ten Zeile und ersten Spalte; und A_k1 ist die (n - 1) × (n - 1)-Matrix, die entsteht, wenn man in A die k-te Zeile und die erste Spalte streicht. (Hier wird wie in der Mathematik üblich von 1 bis n durchnumeriert. Und eine 1 × 1-Matrix ist eine reelle Zahl, die zugleich die Determinante ist.)

Eine Matrix kann in C++ als Vektor von Vektoren dargestellt werden, also durch den Datentyp:

vector<vector<double>>

Die folgende Funktion realisiert den rekursiven Aufruf der Determinanten-Berechnung aus dem Laplaceschen Entwicklungssatz:

// Berechnung der Determinante nach dem Laplaceschen Entwicklungssatz
// rekursiver Aufruf bis 1x1 Matrix
double getDeterm(vector<vector<double>> matrix)
{
    if (matrix.size() == 1)         // 1x1 Matrix
    {
        return matrix [0][0];
    }

    double summe = 0;
    int faktor = 1;                 // Für Vorzeichen-Wechsel
    
    for (int i = 0; i < matrix.size(); i++)         // Entwicklung nach der ersten Spalte
    {
        summe += faktor * matrix [0][i] * getDeterm(getSubMatrix(matrix, 0, i));
        faktor *= -1;
    }
    return summe;
}

Dazu fehlt noch die Funktion

vector<vector<double>> getSubMatrix(vector<vector<double>> matrix, int i, int j));

die aus einer gegebenen Matrix die i-te Zeile und j-te Spalte streicht und die entstehende Submatrix zurückgibt (siehe Aufgaben unten).

Um eine Matrix zu erzeugen, muss ein Objekt Vektor von Vektoren angelegt werden, dazu kann folgende Funktion hilfreich sein:

// Erzeugen einer n x n Matrix mit Tetswerten; hier: obere Dreiecksmatrix
vector<vector<double>> createMatrix(int n)
{
    vector<vector<double>> matrix(n);           // Matrix als Vektor von n Vektoren

    for (int i = 0; i < n; i++)
    {
        // Vektor v erzeugen mit n Komp.
        vector<double> v (n);
        for (int k = 0; k < n; k++)
        {
            // Vektor v: k-tes Element setzen
            if (k >= i)             // obere Dreiecksmatrix
                v[k] = 2;       
            else
                v[k] = 0;            
        }
        matrix[i] = v;      // Matrix aus Vektoren v aufbauen
    }
    return matrix;
}

Die Funktion createMatrix() erzeugt eine n × n-Matrix; hier speziell eine obere Dreiecksmatrix (mit Einträgen 2). Dreiecksmatrizen sind zum Testen besonders gut geeignet, da deren Determinante das Produkt der Einträge auf der Hauptdiagonale ist, hier also 2ⁿ. (Das Programm kennt diesen Sachverhalt aber nicht und berechnet dennoch die Rekursion — das Ergebnis lässt sich also leicht nachprüfen.)

Aufgaben:

1. Schreiben Sie die noch fehlende Funktion getSubMatrix() zum Bilden der Streichmatrix A_ij zu gegebener Matrix A.

2. Wieviele Determinanten-Berechnungen sind nötig, wenn man von einer n × n-Matrix ausgeht?

3. Eine beliebige Matrix kann auch durch Zeilenumformungen auf die Gestalt einer oberen Dreiecksmatrix gebracht werden. Wieviele Zeilenumformungen sind nötig, wenn man wieder von einer n × n-Matrix ausgeht?

4. Lässt sich aus diesen Überlegungen ableiten, welches Verfahren zur Berechnung einer Determinante für große n besser geeignet ist?

Quicksort

Der Algorithmus Quicksort zum Sortieren von Listen kann ebenfalls als Rekursion formuliert werden. Der Algorithmus lautet in umgangssprachlicher Formulierung:

Man geht von einer Liste L von n Zahlen aus.
Das erste Element der Liste sei x₀.
Man vergleicht alle anderen n - 1 Zahlen mit x₀ und bildet zwei Listen L_< und L_>, wobei in der ersten Liste alle Zahlen sind, die kleiner sind als x₀, und in der zweiten Liste alle Zahlen, die größer sind als x₀.
Die Liste L wird ersetzt durch die Liste (L_<, x₀, L_>).
Die beiden Listen L_< und L_> sind noch nicht sortiert und werden nach dem selben Verfahren sortiert (Rekursion).

Aufgabe:

Schreiben Sie ein Programm, das den Quicksort-Algorithmus umsetzt.

Function Templates

Oftmals benötigt man mehrere Funktionen, die identische Aufgaben erledigen, aber dies mit Variablen von unterschiedlichen Datentypen. Hier hilft zwar das Überladen von Funktionen, die Mehrfach-Implementierungen sind aber fehleranfällig, wenn sie abgeändert werden müssen: man darf keine Implementierung vergessen, man kann Implementierungen erzeugen, die leicht voneinander abweichen und so weiter.

Um diese Fehler zu vermeiden, werden sogenannte Function Templates angeboten (template = Schablone).

Beispiel:

Möchte man etwa zwei Varianten der mean()-Funktion anbieten, einmal mit int und einmal mit double, so muss man nicht beide Funktionen implementieren, wie das folgende Beispiel zeigt:

int mean(int x1, int x2)                            // mean() für integer
{
    return (x1 + x2) / 2;
}

double mean(double x1, double x2)                   // mean() für double
{
    return (x1 + x2) / 2;
}

Man kann stattdessen ein template erzeugen und darin einen formalen Typ-Parameter einsetzen — er wird meist mit T bezeichnet, um an Typ zu erinnern. Die Funktion zur Berechnung des Mittelwertes wird — um anzudeuten, dass hier ein neues Konzept eingeführt wird, — als meanValue() bezeichnet:

template <typename T>
T meanValue(T x1, T x2)
{
    T meanValue = (x1 + x2) / 2;        // T wird hier wie ein bekannter Datentyp behandelt, da es als typename eingeführt wurde
    return meanValue;
}

Das Template ersetzt jetzt sämtliche Funktionen, die zwei Eingabewerte von identischem Datentyp T und Typ des Rückgabewertes T besitzen; und wie man in der Implementierung sieht, muss für den Datentyp die Addition + definiert sein.

Die Syntax sollte klar sein:

Das Schlüsselwort template zeigt an, dass ein Funktions-Template folgt (Zeile 1).
Der Typ-Parameter steht in spitzen Klammern und wird mit dem Schlüsselwort typename versehen.
Jetzt kann T wie ein Datentyp eingesetzt werden.
Benötigt man mehrere Datentypen, steht in Zeile 1 etwa:

template <typename T, typename U, typename V>

Je nachdem wie die Funktion meanValue() jetzt aufgerufen wird, erzeugt der Compiler aus dem Template die Implementierung mit demjenigen Datentyp, der im Aufruf angezeigt wurde. Befinden sich etwa in der main()-Methode folgende Aufrufe:

int n {1};
int m {2};
cout << "int: " << meanValue(n, m) << endl;             // int: 1

double x {1};
double y {2};
cout << "double: " << meanValue(x, y) << endl;          // double: 1.5

wird zweimal der Quelltext für die Funktion meanValue() erzeugt, nämlich mit den Implementierungen, die zu Beginn dieses Beispiels angegeben wurden.

Bei üblichen Funktionen ist es ratsam Deklaration und Implementierung in zwei getrennten Dateien abzulegen; so gliedern Sie Ihr Projekt besser und für den Compiler ist es keine zusätzliche Arbeit, da er sowieso Deklaration und Implementierung getrennt verarbeitet (der Compiler bekommt erst Probleme, wenn Sie die include-guards vergessen).

Bei Funktions-Templates ist diese Aufteilung nur eingeschränkt sinnvoll. Denn der Compiler erzeugt aus einem Template erst dann den Quelltext zu einem konkreten Datentyp, wenn ein entsprechender Funktionsaufruf stattfindet. Und erst jetzt findet die Überprüfung der Syntax statt. Daher ist es sinnvoll:

Entweder das vollständige Template (wie das Beispiel oben) in die passende .h-Datei zu schreiben und diese .h-Datei dort zu inkludieren, wo sie aufgerufen wird.
Oder wieder Deklaration und Implementierung zu trennen, aber beide in eine .h-Datei zu schreiben; die .h-Datei wird dort inkludiert, von wo aus die Funktion aufgerufen wird. Die getrennte Deklaration und Implementierung würde im Beispiel wie folgt aussehen:

// Deklaration:
template <typename T>           
T meanValue(T x1, T x2);

// weitere Deklarationen
// ...

// Implementierung:
template <typename T>           
T meanValue(T x1, T x2)
{
    T meanValue = (x1 + x2) / 2;        // T wird hier wie ein bekannter Datentyp behandelt, da es als typename eingeführt wurde
    return meanValue;
}

(Manchmal wird auch empfohlen, für die die Templates eigene .t-Dateien anzulegen.)

Aufgaben

Im Kapitel zur Einführung in C++, Anwendungen, wurden zahlreiche Aufgaben formuliert.

Überarbeiten Sie Ihre Lösungen im Sinne der strukturierten Programmierung. Falls Sie die Aufgaben noch nicht gelöst haben, entwickeln Sie die entsprechenden Programme, aber achten Sie von Anfang an darauf, wie Sie Funktionen geschickt einsetzen können.