11.20 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 Variablen 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).
11.20.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.
11.20.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:
Hier klicken, um das Bild zu Vergrößern
Abbildung 11.5
Erster Rekursiver Aufruf
Auf den 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).
Hier klicken, um das Bild zu Vergrößern
Abbildung 11.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 (siehe Abbildung 11.7).
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)
Hier klicken, um das Bild zu Vergrößern
Abbildung 11.7
Stack nach vier rekursiven Aufrufen
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:
Hier klicken, um das Bild zu Vergrößern
Abbildung 11.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.
Hier klicken, um das Bild zu Vergrößern
Abbildung 11.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:
/* divide.c */
#include <stdio.h>
#include <stdlib.h>
int main(void) {
int x = 8, y = 2;
printf("%d ", x/y);
if(x % y)
printf("Rest = %d\n",x%y);
return EXIT_SUCCESS;
}
Dieses 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.
11.20.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:
/* fakul.c */
#include <stdio.h>
#include <stdlib.h>
long fakul(long n) {
if(n)
return n * fakul(n-1);
return 1;
}
int main(void) {
printf("Fakultät von 5 = %ld\n",fakul(5));
printf("Fakultät von 9 = %ld\n",fakul(9));
return EXIT_SUCCESS;
}
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;
}
11.20.4 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:
/* fibo.c */
#include <stdio.h>
#include <stdlib.h>
long fibo(long n) {
if(n)
return (n <= 2) ? n : fibo(n-2) + fibo(n-1);
}
int main(void) {
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 EXIT_SUCCESS;
}
11.20.5 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:
/* ggt1.c */
#include <stdio.h>
#include <stdlib.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(void) {
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 EXIT_SUCCESS;
}
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:
Hier klicken, um das Bild zu Vergrößern
Abbildung 11.10
Rekursive Ermittlung des größten gemeinsamen Teilers
Eine alternative direkte Lösung wäre gewesen:
/* ggt2.c */
#include <stdio.h>
#include <stdlib.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(void) {
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 EXIT_SUCCESS;
}
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 ich 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:
/* ggt3.c */
#include <stdio.h>
#include <stdlib.h>
unsigned long ggt(unsigned long a, unsigned long b) {
if(b == 0)
return a;
return ggt(b, a % b);
}
int main(void) {
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 EXIT_SUCCESS;
}
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.
Als letztes Beispiel will ich Ihnen zeigen wie Sie eine rekursive Funktion zum Umwandeln von Dezimalzahlen nach Dualzahlen verwenden können. Um bspw. aus der Zahl 10 die entsprechende Dualzahl 1010 zu machen, ist folgender Vorgang nötig:
-> Solange die Zahl ungleich Null ->
-> Zahl % 2 = kein Rest dann 0 oder = Rest dann 1 ->
-> Zahl = Zahl / 2
Auf die Zahl 10 angewendet sieht dieser Vorgang wie folgt aus:
10/2 = 5 kein Rest -> 0
5/2 = 2 Rest 1 -> 1
2/2 = 1 kein Rest -> 0
1/2 = 0 Rest 1 -> 1
Damit liegen auf dem Stack (umgekehrte Reihenfolge):
1
0
1
0
Hier das Beispiel dazu:
/* dez2bin.c */
#include <stdio.h>
#include <stdlib.h>
#define ulong unsigned long
void dez2bin(ulong dez) {
if(dez) {
dez2bin(dez / 2);
printf("%lu", dez % 2);
}
}
int main(void) {
ulong dezimal;
printf("Dezimalzahl in Dualzahl konvertieren\n");
printf("Welche Zahl : ");
scanf("%lu",&dezimal);
printf("Dezimal = %lu Dual = ",dezimal);
dez2bin(dezimal);
printf("\n");
return EXIT_SUCCESS;
}
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.
|
