| #include <pronix.de> |
|
 |
|
|
|
|
12.14. Funktion mit Wertübergabe (call-by-value)
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Hinweis |
|
Ein Prozess ist ein Programm während seiner Ausführung. |
|
12.17. Funktionen der Laufzeitbibliothek
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
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:
- Editieren und Kompilieren dauern länger.
- Quelltext wird unübersichtlich und schwieriger zu verstehen.
- Teamarbeit wird erschwert.
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
12.19. Rekursive Funktionen
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
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
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
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
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
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
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
© 2000 - 2003 Jürgen Wolf