Funktionen werden nicht nur in C, sondern auch in vielen anderen Programmiersprachen verwendet. Wenn Sie von einer anderen Sprache nach C gewechselt haben, kennen Sie Funktionen möglicherweise auch unter den Namen Subroutine, Unterprogramm, Subfunktion oder ähnlich. C C++ C/C++ Funktionen Subroutine Unterprogramm Rückgabewert Parameter Argument call by value Funktionen - Subroutine Unterprogramm Rückgabewert call by value Parameter Argument Rekursion Kapitel 12: Funktionen

12.14. Funktion mit Wertübergabe (call-by-value)            zurück  Ein Kapitel tiefer  zum Inhaltsverzeichnis

Es folgt ein Beispiel, wie Sie einer Funktion Daten übergeben können:

#include <stdio.h>

void verdoppeln(int);
void halbieren(int);

void halbieren(int zahl)
{
   zahl/=2;
   printf("Halbiert: %d\n",zahl);
}

void verdoppeln(int zahl)
{
   zahl*=2;
   printf("Verdoppelt: %d\n",zahl);
}

int main()
{
   int wahl, z;
   printf("Bitte geben Sie eine Zahl ein : ");
   scanf("%d",&z);

   printf("Wollen Sie diese Zahl\n");
   printf("\t1.)verdoppeln\n\t2.)halbieren\n\nIhre Wahl : ");
   scanf("%d",&wahl);

   switch(wahl)
      {
         case 1 : verdoppeln(z);
                  break;
         case 2 : halbieren(z);
                  break;
         default: printf("Unbekannte Eingabe\n");
      }
   return 0;
}

An der Deklaration der Funktionen können Sie schon erkennen, dass die Funktion einen Parameter vom Datentyp int verwendet. Außerdem fällt auf, dass die globale Variable verschwunden ist und in der main()-Funktion wieder auftaucht. Ein Blick auf eine Funktion:

void halbieren(int zahl)
{
   zahl/=2;
   printf("Halbiert: %d\n",zahl);
}

Es handelt sich also um eine Funktion, die als Parameter einen int-Wert übernimmt. Das bedeutet, dass Sie die Funktion halbieren() nur mit einem Argument vom Typ int aufrufen können. Andernfalls meldet der Compiler einen Fehler.

Aufgerufen wird diese Funktion (von einer anderen Funktion aus) mit einem Argument, auch formaler Parameter genannt. Im gezeigten Beispiel sieht der Funktionsaufruf mit Argument folgendermaßen aus:

halbieren(zahl);

Dann wird für die aufrufende Funktion ein Stack-Rahmen (dynamischer Speicherbereich) angelegt. In diesem Speicherbereich wird Speicher für diejenigen Parameter reserviert, welche die Funktion beinhaltet. Der Parameter, den Sie der Funktion durch das Argument übergeben haben, wird auch initialisiert. Damit steht der Funktion das Argument z auch mit dem gleichen Wert für die Funktion halbieren(), nur mit dem Namen zahl, als Kopie zur Verfügung. Die Funktion kann nun mit den Parametern ganz normal arbeiten. Der Parameter einer Funktion ist bei einer so genannten Call-by-value-Übergabe eine Kopie des Werts, mit dessen Argument Sie die Funktion aufgerufen haben. Nochmals die vier Schritte, wie der Datenfluss bei Übergabe von Argumenten abläuft:

  1. Bei der Funktionsdefinition wird die Parameterliste festgelegt (formale Parameterliste).
  2. Die Funktion wird von einer anderen Funktion mit dem Argument aufgerufen (muss mit dem Typ des formalen Parameters übereinstimmen).
  3. Für die Funktion wird ein dynamischer Speicherbereich (im Stack) angelegt.
  4. Jetzt kann die Funktion mit den Parametern arbeiten.

Neben call-by-value existiert auch call-by-reference, womit statt einem Wert eine Adresse kopiert wird. Diese Art des Aufrufs wird im Zusammenhang mit Zeigern näher besprochen (Kapitel 15).

Natürlich können Sie auch mehrere Parameter in einer Funktion verwenden. Als Anwendungsbeispiel soll im Folgenden der gregorianische Kalender zum julianischen umgerechnet werden. Dieses Verfahren wird vorwiegend in der Astronomie und Raumfahrt genutzt.

Der julianische Kalender beginnt mit der ägyptischen Berechnung seit dem 1.1.4713 vor Christus. Mit dem julianischen Datum lässt sich sehr gut die Sonnen- bzw. Mondfinsternis berechnen:

#include <stdio.h>

/*Umrechnung vom gregorianischen zum julianischen Datum*/

void greg2jul(int tag, int monat, int jahr)
{
   int k,l,jd;
   k=(monat-14)/12;
   l=jahr+k+4800;
   jd=tag-32075+1461*l/4 + 367*
      ((monat-2-12*k)/12)-3*((l+100)/100)/4;
   printf(" sind %d Tage vergangen\n",jd);
}

int main()
{
   int tag,monat,jahr;

   printf("Eingabe (Tag)  : ");
   scanf("%d",&tag);
   printf("Eingabe (Monat): ");
   scanf("%d",&monat);
   printf("Eingabe (Jahr) : ");
   scanf("%d",&jahr);

   printf("Seit dem 1.1.4713 v.Chr. bis %2d.%2d.%4d"
           ,tag,monat,jahr);
   greg2jul(tag,monat,jahr);
   return 0;
}

Wichtig ist dabei, dass Sie darauf achten, die Argumente beim Funktionsaufruf in der richtigen Reihenfolge anzugeben. Vertauschte Werte führen zu falschen Berechnungen. Die Parameter könnten auch von unterschiedlichen Datentypen sein, was der Compiler im Fall der Vertauschung in den meisten Fällen aber moniert:

#include <stdio.h>

void mixed(int x, char y, float z)
{
   printf("Stückzahl : %d ",x);
   printf("Klasse    : %c ",y);
   printf("Preis     : %.2f Euro\n",z);
}

int main()
{
   mixed(6, 'A', 5.5f);
   mixed(9, 'B', 4.3f);
   return 0;
}

12.15. Rückgabewert von Funktionen            zurück  Ein Kapitel tiefer  Ein Kapitel höher  zum Inhaltsverzeichnis

Jetzt haben Sie gesehen, wie es möglich ist, Daten an eine Funktion zu übergeben. Nun wollen Sie natürlich noch wissen, wie eine Funktion so geschrieben wird, dass diese Daten an den Aufrufer zurückgibt. Zunächst benötigen Sie eine Funktionsdefinition mit einem Rückgabewert. Als Rückgabewert können Sie jeden beliebigen Datentyp verwenden. Zum Beispiel:

int bignum(int a, int b)
{
   if(a > b)
      return a;
   else if(a < b)
      return b;
   else
      return 0; /* beide Zahlen gleich groß */
}

Sie erkennen an dieser Funktion durch das Voranstellen des Datentyps, dass hier der Rückgabewert ein Integer ist. Und in der Funktion selbst wird mit der Anweisung

return WERT; 

ein Wert an die aufrufende Funktion zurückgeliefert. Diese return-Anweisung dient aber nicht nur dazu, der aufrufenden Funktion einen Wert zurückzuliefern, sondern setzt zugleich das Ende einer Funktion fest. Bei return wird also die Kontrolle an die aufrufende Funktion zurückgegeben. Dabei kann ein Wert zurückgegeben werden. Jetzt wird noch der Aufrufer selbst mit seinen Argumenten benötigt:

int big;
…
big = bignum(wert1, wert2);

Damit wird der Variable big, die zwingend vom Datentyp int sein muss, der Rückgabewert der Funktion bignum() zugewiesen. Das vollständige Programm sähe dann folgendermaßen aus:

#include <stdio.h>

int bignum(int a, int b)
{
   if(a > b)
      return a;
   else if(a < b)
      return b;
   else
      return 0; /* beide Zahlen sind gleich groß */
}

int main()
{
   int wert1, wert2, big;
   printf("Bitte einen Wert eingeben: ");
   scanf("%d",&wert1);
   printf("Bitte noch einen Wert eingeben: ");
   scanf("%d",&wert2);

   big = bignum(wert1, wert2);
   if(big != 0)
      printf("%d ist die größere der beiden Zahlen\n",big);
   else
      printf("Beide Zahlen haben denselben Wert\n");
   return 0;
}

Im weiteren Verlauf werden Sie einige Möglichkeiten von Funktionen mit verschiedensten Rückgabewerten kennen lernen.

12.16. Die Hauptfunktion main()            zurück  Ein Kapitel tiefer  Ein Kapitel höher  zum Inhaltsverzeichnis

Gemäß dem ANSI C-Standard muss mindestens eine Funktion in einem Programm den Namen main() besitzen. Diese Funktion ist auch die erste, die beim Programmstart ausgeführt wird. Geben Sie der main()-Funktion einen anderen Rückgabewert als int, könnte ein C99-Standard-konformer Compiler ein undefiniertes Verhalten zeigen. In einigen (vorwiegend älteren) Büchern finden Sie die main()-Funktion mitunter in folgender Schreibweise:

void main()
{
}

Nach dem älteren C89-Standard ist dies auch richtig. Läuft ein Compiler aber nach dem C99-Standard, sollte dann eine Warnung ausgegeben werden, dass die main()-Funktion einen Rückgabewert erwartet. Die main()-Funktion lautet (nach C99) richtig:

int main()
{
   return 0;
}

Weiterhin ist auch eine Variante mit zwei Parametern erlaubt:

int main(int argc, char *argv[])
{
   return 0;
}

Näheres zu dieser Schreibweise erfahren Sie ein paar Kapitel später.

Der Rückgabewert, der der main()-Funktion zugewiesen wird, dient dazu, dass der Startup-Code dem Betriebssystem und der Umgebung mitteilt, ob das Programm ordnungsgemäß beendet wurde oder nicht (abhängig vom Rückgabewert). In folgenden Fällen liegt ein undefiniertes Verhalten beim Beenden der main()-Funktion vor:

Wichtig ist in diesem Zusammenhang die Bedeutung des Begriffs "Startup-Code". Der Startup-Code wird zu Beginn des Prozesses erzeugt (meist in Assembler) und dient der Beendigung eines Prozesses. Bei Beendigung der main()-Funktion mittels return 0 wird wieder zum Startup-Code zurückgesprungen. Er ruft dann die exit()-Funktion auf. Die exit()-Funktion führt dann noch einige Aufräumarbeiten aus (z.B. Freigabe des Speicherplatzes von benutzten Variablen des Programms). Zuletzt wird der Prozess mit der Funktion _exit() endgültig beendet. Hier eine bildliche Darstellung des Programmablaufs bei Beendigung des Programms:

Abbildung 12.3: Vom Start bis zum Ende eines Programms
Abbildung 12.3: Vom Start bis zum Ende eines Programms



Hinweis
 

Ein Prozess ist ein Programm während seiner Ausführung.

12.17. Funktionen der Laufzeitbibliothek            zurück  Ein Kapitel tiefer  Ein Kapitel höher  zum Inhaltsverzeichnis

Funktionen wie printf() oder scanf() sind solche, wie Sie sie in den Kapiteln zuvor schon gesehen und verwendet haben. Dies sind zum Beispiel Funktionen der Laufzeitbibliothek <stdio.h>, welche jedem Compiler beigefügt ist. Diese Funktionen werden bereits als Objektcode mit Ihrem Compiler mitgeliefert, sie müssen dem Compiler jedoch trotzdem bekannt gemacht werden, und zwar mit den Headerdateien der Funktionen:

#include <stdio.h> 

Natürlich gibt es außer den Funktionen printf() und scanf() noch eine Menge mehr Funktionen in der Headerdatei <stdio.h>. Alle können in einem Programm verwendet werden, sobald die entsprechende Headerdatei inkludiert wurde. Es ist gängige Praxis, nachzusehen, welche nützlichen Funktionen einer Headerdatei in einem Programm verwendet werden können, bevor Funktionen selbst neu programmiert werden. Sehen Sie sich die stdio.h ruhig einmal näher mit einem Editor an. Sie ist unter Linux/UNIX für gewöhnlich im Verzeichnis /USR/INCLUDE und unter Windows oft im Verzeichnis C:\Pfad_zum_Compiler\INCLUDE zu finden. Auch gibt es bei ANSI C Compilern noch eine Menge mehr Headerdateien, die wiederum fertige Funktionen beinhalten. Den entsprechenden Objektcode zu den Headerdateien der Laufzeitbibliothek finden Sie im LIB-Verzeichnis des Compilers. Welche das sind, erfahren Sie noch im Verlauf dieses Buchs.

Wenn Sie die Headerdatei <stdio.h> mit einem Texteditor ansehen, werden Sie darin die Funktionsdefinitionen von z.B. printf() finden:

int printf(const char *format, ...); 

Der dem Compiler nachgeschaltete Linker sorgt dafür, dass diese Funktionen automatisch in das Programm mit eingebunden werden.

12.18. Getrenntes Compilieren von Quelldateien            zurück  Ein Kapitel tiefer  Ein Kapitel höher  zum Inhaltsverzeichnis

Für kleinere Programme, deren vollständiger Quelltext in einer Datei geschrieben wurde, können Sie beim Kompilieren weiterhin wie bisher verfahren. Bei zunehmend größeren Programmen könnten jedoch folgende Probleme auftreten:

Deshalb ist ein getrenntes Kompilieren von Quelldateien zu empfehlen, das ich anhand des GNU-Compilers gcc demonstrieren werde. Mit anderen Compilern dürfte dieser Vorgang ähnlich ablaufen. Bei Entwicklungsumgebungen müssen Sie dabei ein neues Projekt anlegen und die einzelnen Quelldateien zum Projekt hinzufügen. Im Folgenden ein Beispiel zum getrennten Kompilieren mit drei Progammmodulen, die aus Demonstrationszwecken sehr kurz gehalten sind:

/*main.c*/
#include <stdio.h>

extern modul1(void);
extern modul2(void);

int main()
{
   modul1();
   modul2();
   return 0;
}


/*modul1.c*/
void modul1()
{
   printf("Ich bin das Modul 1\n");
}


/*modul2.c*/
void modul2()
{
   printf("Ich bin Modul 2\n");
}

Jetzt haben Sie drei Dateien, die zusammen kompiliert und gelinkt werden müssen. Zuerst wird hierfür der Schalter -c verwendet. Er bewirkt, dass die einzelnen Dateien zwar übersetzt werden, dabei aber nicht der Linkerlauf gestartet wird:

gcc -c main.c
gcc -c modul1.c
gcc -c modul2.c

Nun befinden sich drei Objektdateien (*.obj oder *.o) im Verzeichnis, in dem kompiliert wurde. Diese drei Objektdateien können Sie mit folgender Anweisung zu einer ausführbaren Datei linken:

gcc main.o modul1.o modul2.o

Im Verzeichnis ist jetzt die Datei a.out. Dies ist die ausführbare Datei, das fertige Programm. Der Name a.out wird standardmäßig vom Compiler verwendet. Mit dem Schalter -o können Sie auch einen eigenen Namen vorgeben:

gcc -o myapp main.o modul1.o modul2.o  

Sollten Sie gcc unter Windows verwenden, fügen Sie dem Programmnamen myapp die Extension *.exe hinzu (myapp.exe). Wenn Sie jetzt die Datei main.c ändern müssen, brauchen Sie diese nur neu zu übersetzen:

gcc -c main.c 

und können anschließend die einzelnen Dateien wieder zusammenlinken:

gcc main.o modul1.o modul2.o

Das nochmalige Kompilieren der anderen Dateien entfällt, da deren Code nicht geändert wurde und deshalb die unveränderten *.o Dateien neu verlinkt werden können. Bei großen und sehr großen Projekten führt dieses Vorgehen zu deutlich kürzeren Kompilier-Zeiten.

Natürlich versteht es sich von selbst, dass sich in einer der Dateien die main()-Funktion befinden muss. Hier der ganze Vorgang noch einmal im Bild:

Abbildung 12.4: Übersetzen mehrerer Quelldateien

Abbildung 12.4: Übersetzen mehrerer Quelldateien

12.19. Rekursive Funktionen            zurück  Ein Kapitel höher  zum Inhaltsverzeichnis

Kurz gesagt ist eine Rekursion eine Funktion, die sich selbst aufruft und sich selbst immer wieder neu definiert. Damit sich aber eine Rekursion nicht unendlich oft selbst aufruft, sondern irgendwann auch zu einem Ergebnis kommt, benötigen Sie unbedingt eine so genannte Abbruchbedingung. Sonst kann es irgendwann passieren, dass Ihr Computer abstürzt, da eine Funktion, die sich immer wieder selbst aufruft, eine Rücksprungadresse, den Wert der Variable und - falls noch nicht freigegeben - den Rückgabewert speichert. Der dafür zur Verfügung stehende Speicher (Stack) wird so aber unweigerlich irgendwann voll sein beziehungsweise überlaufen (Stacküberlauf oder Stack Overflow).

12.19.1 Exkurs: Stack
Der Stack wurde bereits öfters erwähnt. Er soll deshalb im Folgenden näher betrachtet werden.

Der Stack dient dazu, den Speicherbereich für Funktionsaufrufe zu verwalten. Dieser Speicherbereich ist dynamisch, was bedeutet, dass der Speicher bei Bedarf automatisch anwächst und wieder schrumpft. Der Compiler, der diesen Stack verwaltet, legt hier alle Daten ab, die er zur Verwaltung von Funktionsaufrufen benötigt.

Wenn eine Funktion aufgerufen wird, erweitert der Compiler den Stack um einen Datenblock. In diesem Datenblock werden die Parameter, die lokalen Variablen und die Rücksprungadresse zur aufrufenden Funktion angelegt. Dieser Datenblock wird als Stack-Frame oder Stackrahmen bezeichnet.

Der Datenblock bleibt so lange bestehen, bis diese Funktion wieder endet. Wird in ihm aber eine weitere Funktion aufgerufen, wird ein weiterer Datenblock auf den (richtig wäre: unter den) aktuellen gepackt. Der Stack wächst nach unten an. Am Anfang des Stacks befindet sich der Startup-Code, der die main()-Funktion aufruft, welche eine Position unter dem Startup-Code liegt. An unterster Stelle befindet sich immer die aktuelle Funktion, die gerade ausgeführt wird. Eine Position - oder besser: einen Datenblock - darüber liegt die aufrufende Funktion in der Wartestellung. Sie wartet auf die Beendigung der nächsten aufgerufenen Funktion. Mit diesem Wissen über den Stack können Sie sich wieder den Rekursionen widmen.

12.19.2 Rekursionen und der Stack
Mit Rekursionen haben Sie die Möglichkeit, den Computer zu etwas zu bewegen, was ihn intelligenter erscheinen lässt. Ein Beispiel wäre etwa Schach. Wenn Sie einen Zug machen, gehen Sie zuerst alle Möglichkeiten durch, um den Gegner in Bedrängnis bzw. den gegnerischen König in Gefahr zu bringen oder gar schachmatt zu setzen. Das ist eine logische Denkweise des Menschen. Mit einer Rekursion ist es ebenfalls möglich, den Computer eine Situation sooft durchgehen zu lassen, bis er auf eine Lösung kommt oder auch nicht. Man spricht dabei vom "Trial and Error-Verfahren" (Versuch und Irrtum). Ein Beispiel: Sie bedrohen den König des Computers. Der Computer geht dann alle Züge durch, um den König aus dieser Bedrohung zu befreien, und dann, in einem zweiten Schritt, geht er nochmals alle Züge durch, die Sie als Nächstes theoretisch machen könnten. Je nachdem, wie tief die Rekursion gehen soll. Zum besseren Verständnis folgt ein konkretes Beispiel.

Eine Funktion soll zwei Zahlen dividieren. Der ganzzahlige Rest der Division soll angegeben werden. Zum Beispiel: 10/2=5 oder 10/3=3 Rest 1. Das Programm darf aber nicht die Operatoren / und % verwenden. Die Lösung soll die Form einer rekursiven Funktion haben:

int divide(int x, int y)
{
   if(x>=y)
      return (1 + divide(x-y, y));
   if(x)
      printf("Zahl nicht teilbar -> Rest: %d -> ", x);
   return 0;
}

Hier ein Fall, in dem der Funktion beispielsweise die Werte x=8 und y=2 übergeben werden:

/* Funktionsaufruf */
printf("8/2 = Ergebnis : %d\n", divide(8, 2));

Innerhalb der Funktion wird zunächst die Abbruchbedingung überprüft:

if(x >= y) 

Da die Bedingung für x=8 und y=2 wahr ist, wird die nächste Anweisung ausgeführt:

return 1 + divide(x-y,y); 

Die Funktion gibt mittels return die Summe 1+divide(x-y,x) zurück. Damit wird, bevor das Ergebnis endgültig zurückgegeben wird, die Funktion divide erneut aufgerufen. Die Funktion ruft sich also selbst auf. Hiermit beginnt die Rekursion. Aber was passiert jetzt mit dem Rückgabewert 1? Sehen Sie sich das Beispiel zum besseren Verständnis in der Abbildung an:

Abbildung 12.5: Erster Rekursiver Aufruf
Abbildung 12.5: Erster Rekursiver Aufruf

Auf dem Stack wurde zuerst die main()-Funktion gelegt, da diese zuerst die Funktion divide() aufgerufen hat. Hier ist quasi gespeichert, wie Ihr Programm wieder zur main()-Funktion zurückkommt. Sie können sich das etwa so vorstellen: Bei jedem Funktionsaufruf in einem Programm, unabhängig davon, ob rekursiv oder nicht, wird der aktuelle Zustand der main()-Funktion eingefroren und auf dem Stack abgelegt. Damit das Programm weiß, wo die Adresse der main()-Funktion ist, wird auf dem Stack eine Rücksprungadresse mit abgelegt. Zurück zur Programmausführung des konkreten Beispiels. Die Funktion hat sich also selbst aufgerufen mit der Anweisung:

return 1 + divide(x-y,y); 

In Zahlen also divide(8-2,2) mit den Werten x=8 und y=2. Im abermaligen Funktionsaufruf wird erneut überprüft:

if(x >= y)

Da x=6 und y=2 und somit die if-Abfrage wieder wahr ist, geht die Programmausführung wieder in der nächsten Zeile weiter.

Es folgt ein erneuter Selbstaufruf der Funktion divide():

return 1 + divide(x-y,y); 
Also wird Folgendes auf dem Stack abgelegt (siehe Abbildung).

Abbildung 12.6: Zweiter Rekursiver Aufruf
Abbildung 12.6: Zweiter Rekursiver Aufruf

Nun liegt auf dem Stack zweimal der Rückgabewert 1, inklusive der Rücksprungadressen (diese sind hier nicht mit abgebildet). Jetzt wiederholt sich das ganze Spiel noch zweimal, bis es auf dem Stack folgendermaßen aussieht:

Abbildung 12.7: Stack nach vier rekursiven Aufrufen
Abbildung 12.7: Stack nach vier rekursiven Aufrufen

Der Funktionswert für x im Aufruf der Funktion ist mittlerweile auf 2 reduziert worden. Danach wird erneut die Funktion divide() aufgerufen, und zwar mit den Werten:

divide(2-2,2)

Jetzt wird die Abbruchbedingung aktiv:

if(x >= y) 

Denn jetzt ist x=0 und y=2 und somit wird die Programmausführung nicht mehr in der nächsten Zeile ausgeführt. Die nächste Abfrage

if(x)

dient dazu, den Rest auszugeben, falls x ungleich 0 sein sollte. In unserem Beispiel gibt es keinen Rest. Es wird also der Wert 0 (return 0) zurückgegeben. Das Programm muss nun zur nächsten Rücksprungadresse gehen, da sich die Funktion ja beendet hat. Nochmals ein Blick zum Stack:

Abbildung 12.8: Die Abbruchbedingung greift jetzt ein
Abbildung 12.8: Die Abbruchbedingung greift jetzt ein

Der Rückgabewert 0 wurde von dem Funktionsaufruf divide(2-2,2) erzeugt. Dorthin führt auch die Rücksprungadresse, also return 0+1. Die nächste Rücksprungadresse wurde von divide(4-2,2) erzeugt, also folgt return 0+1+1; anschließend return 0+1+1+1 und zuletzt return 0+1+1+1+1. Die main-Funktion bekommt dann den Rückgabewert 0+1+1+1+1, also 4, und das ist auch korrekt, denn 8/2 ist 4.

Abbildung 12.9: Addieren der einzelnen Rückgabewerte auf dem Stack
Abbildung 12.9: Addieren der einzelnen Rückgabewerte auf dem Stack

Sie werden sich möglicherweise fragen, welche Vorteile ein solches Programm gegenüber einem Programm der folgenden Form hat:

#include <stdio.h>

int main()
{
   int x=8,y=2;
   printf("%d ",x/y);
   if(x%y)
      printf("Rest = %d\n",x%y);
   return 0;
}

Dies Programm erfüllt doch denselben Zweck und ist einfacher! Sie haben Recht, das rekursive Programm ist zum einen schwieriger und zum anderen langsamer, da ständig etwas auf dem Stack gepusht und wieder gepopt werden muss. Kurz gesagt: Die rekursive Lösung ist die schlechtere in diesem Beispiel. Schlimmer noch, die rekursive Lösung verbraucht viel Speicherplatz zum Anlegen von Parametern, lokalen Variablen, Rückgabewerten und Rücksprungadressen. Ein Beispiel: Sie wollen die Zahl 1.000.000 durch 2 teilen. Für die zwei Parameter x und y benötigen Sie schon acht Byte pro Aufruf. Für den Rückgabewert (return 1) werden weitere vier Bytes benötigt, genauso wie für die Rücksprungadresse. Das heißt, Sie verwenden für eine Ablage auf dem Stack 16 Byte. Wenn Sie die Zahl 1.000.000 durch 2 teilen, bedeutet dies, dass auf dem Stack 500.000 Werte zu je 16 Bytes liegen. Das sind ca.7,6 Megabytes Arbeitsspeicher, die Sie durch eine rekursive Lösung eines solch einfachen Problems verschwenden.

Warum also Rekursionen anwenden, wenn die direkte Lösung oftmals die bessere ist? In späteren Programmen werden Sie einige Beispiele kennen lernen (so genannte binäre Bäume), die ohne Rekursion nicht so einfach realisierbar wären. Die Rekursion will ich Ihnen anhand von einigen Beispielen noch näher erläutern. Die verwendeten Programme sollen nur die Rekursion verdeutlichen. Es ist einleuchtend, dass die Programme ansonsten auch einfacher und meistens besser lösbar sind. Es sind typische, klassische Beispiele.

12.19.3 Fakultät
Es soll eine Funktion geschrieben werden zum Berechnen der Fakultät der Zahl n. Die Fakultät der Zahl 6 ist zum Beispiel: 1*2*3*4*5*6=720. Die Fakultät von 10 ist 1*2*3*4*5*6*7*8*9*10=3.628.800.

Wie schreiben Sie die Funktion am besten? Zuerst benötigen Sie eine Abbruchbedingung. Es muss lediglich überprüft werden, ob die Zahl, von der Sie die Fakultät berechnen wollen, ungleich 0 ist:

#include <stdio.h>

long fakul(long n)
{
   if(n)
      return n * fakul(n-1);
   return 1;
}

int main()
{
   printf("Fakultät von 5 = %ld\n",fakul(5));
   printf("Fakultät von 9 = %ld\n",fakul(9));
   return 0;
}

Die Funktion rechnet so lange n*n-1, bis n den Wert 0 hat. Denn n*0 würde sonst das Ergebnis 0 ergeben. Bei fakul(5) wären dies dann 5*4*3*2*1=120, wobei n*1 eigentlich auch eingespart werden kann, denn mit n*1 wird sich der Wert nicht ändern. Natürlich will ich Ihnen die alternative direkte Lösung des Problems nicht vorenthalten:

long fakul(int n)
{
   int x=n;
   while(--x)
      n*=x;
   return n;
}

12.19.4 Spiegeln eines Textes
Ein weiteres rekursives Beispiel ist das Spiegeln eines Textes:

#include <stdio.h>

void reverse(char *s)
{
   if(*s)
      reverse(s+1);
   putchar(*s);   /* putchar gibt ein Zeichen aus */
}

int main()
{
   reverse("\nSome men interpret nine memos");
   reverse("\nHALLO");
   return 0;
}

Bei dieser Rekursion wird jeder einzelne Buchstabe auf den Stack gelegt. Bei HALLO zum Beispiel zuerst das H dann das A usw.
Jede einzelne Ablage auf dem Stack beinhaltet natürlich wie immer den Wert (Buchstabe), den Parameter und die Rücksprungadresse. An diesem Beispiel können Sie erkennen, dass die Rücksprungadresse nach der Rekursion putchar(*s) zum Ausgeben einzelner Zeichen lautet. Anfängern sei gesagt, das Kapitel der Zeichenketten und Zeiger ist nah.

12.19.5 Fibonacci-Zahlen
Die Fibonacci-Zahlen sollen rekursiv berechnet werden. Fibonacci-Zahlen sind z.B. 1, 2, 3, 5, 8, 13, 21 ... Errechnet werden können sie mittels ... 1+2=3, 2+3=5, 3+5=8, 5+8=13. Nach Formel also:

F(n+2)=F(n+1) +F(n)

Hierzu der Code:

#include <stdio.h>

long fibo(long n)
{
   if(n)
      return (n<=2) ?n:fibo(n-2)+fibo(n-1);
}

int main()
{
   long f;
   long i=0;
   printf("Wie viele Fibonacci-Zahlen wollen Sie ausgeben:");
   scanf("%ld",&f);
   while(i++ < f)
      printf("F(%ld) = %ld\n", i, fibo(i));
   return 0;
}

12.19.6 Größter gemeinsamer Teiler (GGT)
Es folgt ein Listing zum Ermitteln des größten gemeinsamen Teilers zweier Zahlen. Natürlich wird dafür der rekursive Weg eingeschlagen. Auch hier muss zuerst eine Abbruchbedingung gefunden werden. Sie haben drei Möglichkeiten zum Errechnen des GGT zweier Zahlen:

ist Zahl1 == Zahl2 dann Ergebnis = Zahl1
ist Zahl1  > Zahl2 dann Ergebnis = ggT(Zahl1-Zahl2, Zahl2)
ist Zahl1  < Zahl2 dann Ergebnis = ggT(Zahl1, Zahl2-Zahl1)

Das Programm sieht folgendermaßen aus:

#include <stdio.h>

unsigned long ggt(unsigned long a, unsigned long b)
{
   if(a==b)
      return a;
   else if(a<b)
      return ggt(a,b-a);
   else
      return ggt(a-b,b);
}

int main()
{
   unsigned long a,b;
   printf("ggt = größter gemeinsamer Teiler\n");
   printf("Zahl 1: ");
   scanf("%lu",&a);
   printf("Zahl 2: ");
   scanf("%lu",&b);
   printf("Der ggT von %lu und %lu ist %lu\n", a, b, ggt(a,b));
   return 0;
}

Beispiel: Sie geben für a=10 und b=3 ein. Folgende Wertepaare werden auf den Stack gelegt, bis das Programm den GGT von 1 zurückgibt:

Abbildung 12.10: Rekursive Ermittlung des größten gemeinsamen Teilers
Abbildung 12.10: Rekursive Ermittlung des größten gemeinsamen Teilers

Eine alternative direkte Lösung wäre gewesen:

#include <stdio.h>

unsigned long ggt(unsigned long a, unsigned long b)
{
   unsigned long count;

   if(a==b)
      return a;
   else if((a%b)==0)
      return b;
   else
      for(count=b; count>0; count--)
         {
            if(((a%count) + (b%count)) == 0)
               return count;
         }
}

int main()
{
   unsigned long a,b,c;
   printf("ggt = größter gemeinsamer Teiler\n");
   printf("Zahl 1: ");
   scanf("%lu",&a);
   printf("Zahl 2: ");
   scanf("%lu",&b);
   if(a<b)
      { /*a und b vertauschen*/
         c=a; a=b; b=c;
      }
   printf("Der ggT von %lu und %lu ist %lu\n", a, b, ggt(a,b));
   return 0;
}

Nun soll der größte gemeinsame Teiler von beliebig vielen Zahlen ermittelt werden. Die Schwierigkeit liegt bei diesem Beispiel aber nicht in der rekursiven Funktion, sondern in der main()-Funktion. Sie könnten die Funktion GGT, wie diese eben geschrieben wurde, benutzen, ohne sie zu verändern. Zuvor möchte Ihnen aber noch eine zweite Möglichkeit demonstrieren, wie Sie den GGT ermitteln können. Hier die Funktion:

unsigned long ggt(unsigned long a, unsigned long b)
{
   if(b==0)
      return a;
   return ggt(b, a%b);
}

Jetzt lassen sich womöglich die Vorteile einer Rekursion erkennen. Die rekursive Funktion erfüllt den gleichen Zweck wie die beiden Funktionen GGT zuvor. Mit return ggt(b, a%b) rufen Sie die Funktion erneut auf. Wenn a%b==0 ergibt, haben Sie ja den GGT durch b an a übergeben. Hier die main()-Funktion zum Ermitteln des GGT mehrerer Zahlen:

#include <stdio.h>

unsigned long ggt(unsigned long a, unsigned long b)
{
   if(b==0)
      return a;
   return ggt(b, a%b);
}

int main()
{
   unsigned long a,b;
   printf("ggt = größter gemeinsamer Teiler(mit 0 beenden)\n");
   printf("Zahl> ");
   scanf("%lu", &a);
   printf("Zahl> ");
   scanf("%lu", &b);
   a=ggt(a, b);
   while(1)
      {
         printf("Zahl> ");
         scanf("%lu", &b);
         if(b==0)
            break;
         a=ggt(a, b);
      }
   printf("-------->ggt = %lu\n", a);
   return 0;
}

An dem Programm wurde nicht viel verändert. Es kam lediglich die while-Schleife hinzu, die Sie mit der Eingabe 0 beenden können.

Wichtig ist, dass Sie bei jedem Schleifendurchlauf den größten gemeinsamen Teiler an a und die neue Zahl an b übergeben. Somit wird immer der GGT aller Zahlen aktualisiert.

12.19.7 Dezimalzahl zu Dualzahl
Als letztes Beispiel will ich Ihnen zeigen, wie Sie eine rekursive Funktion zum Umwandeln von Dezimalzahlen in Dualzahlen (auch Binärzahlen) realisieren. Zuerst will ich Ihnen jedoch noch erklären, wie Sie aus der Zahl 10 die Dualzahl 1010 machen:

Wiederhole, solange die Zahl ungleich Null ist:
   Zahl%2 (Zahl modulo 2)
      Falls kein Rest dann 0;
      Falls Rest dann 1;
   Zahl=Zahl/2

In einem konkreten Beispiel angewendet: Die Zahl sei 10.

10/2 = 5 kein Rest also 0
5/2  = 2 Rest 1 also 1
2/2  = 1 kein Rest 0 also 0
1/2  = 0 Rest 1 also 1

Die Werte werden vom Stack wieder in der umgekehrten Reihenfolge ausgegeben (1010). Hierzu jetzt die rekursive Funktion:

#include <stdio.h>

void dez2bin(unsigned long dez)
{
   if(dez)
      {
         dez2bin(dez/2);
         printf("%lu", dez%2);
      }
}

int main()
{
   unsigned long dezimal;
   printf("Dezimalzahl in Dualzahl konvertieren \n");
   printf("Welche Zahl soll konvertiert werden: ");
   scanf("%lu", &dezimal);
   printf("Dezimal = %lu \nDual = ",dezimal);
   dez2bin(dezimal);
   printf("\n");
   return 0;
}

Dies genügt nun zum Thema Funktionen. In einem späteren Kapitel wird es wieder aufgegriffen, wenn es darum geht, Funktionen mit beliebig vielen Parametern zu erstellen. Dafür müssen jedoch zuerst die Zeiger besprochen werden.

Weiter mit Kapitel 13: Präprozessor-Direktiven            zum Inhaltsverzeichnis