Nächste Seite: 14 Die Parameter von Aufwärts: 0 ist false, alles Vorherige Seite: 12.6 goto Inhalt
Mit Rekursion verhält es sich ähnlich wie mit Zeigern: Eigentlich nicht schwer zu verstehen, aber in der Praxis doch immer wieder undurchsichtig und fehleranfällig25.
Rekursion heißt nur, daß sich eine Funktion selbst wieder aufruft.
Meist geschieht dies direkt, indem in einer Funktion ein Aufruf von sich
selbst steht. Es kann aber auch so geschehen, daß eine Funktion
a() eine weitere Funktion b() aufruft, und die wiederum ruft
a() auf.
In FORTRAN ist Rekursion ausdrücklich verboten, auch wenn es manchmal (mit Einschränkungen) geht. In Pascal ist Rekursion ebenso wie in C zulässig und durchaus sinnvoll einzusetzen.
Ein beliebtes Beispiel für Rekursion ist die Berechnung der
Fakultät einer
gegebenen Zahl. Die Fakultät 
einer positiven Zahl l
kann man (nicht rekursiv, also iterativ) so definieren:
Die Fakultät von l ist also das Produkt aller Zahlen von 1 bis l. Die Fakultät von 0 ist vereinbarungsgemäß 1.
Die Umsetzung in eine C-Funktion und ein kleines Testprogramm ist einfach:
/* refaki.c 30. 7.95 kw
*/
#include <stdio.h>
/* berechnet die Fakultaet einer Zahl l:
*/
unsigned long int fak( unsigned int l )
{
int i;
unsigned long int ergebnis;
ergebnis = 1;
for( i=2; i<=l; i++ )
{ ergebnis *= i;
}
return ergebnis;
}
/* Testprogramm fuer fak():
*/
int main()
{
unsigned int l;
for( l=0; l<10; l++ )
printf( "fak(%u) ist %lu.\n", l, fak(l) );
}
Für die Definition der Fakultät wird aber statt Gleichung
(1) oft eine rekursive Vorschrift angegeben:
Diese Definition verwendet selbst den
Term, den sie definieren soll. Da aber auch eine rekursive Definition
sich nicht selbst an den Haaren aus dem Sumpf ziehen kann, ist eine
Sonderbehandlung für einen Startwert nötig (hier für den Wert 
).
Rekursive Definitionen lassen sich nun in C ebenso wie in Pascal direkt in Funktionen umsetzen:
/* refakr.c 30. 7.95 kw
*/
#include <stdio.h>
/* berechnet die Fakultaet einer Zahl l (rekursiv):
*/
unsigned long int fak( unsigned int l )
{
if( 0==l ) /* Sonderbehandlung */
return 1;
else /* Rekursion */
return fak( l-1 )*l;
}
/* Testprogramm fuer fak():
*/
int main()
{
unsigned int l;
for( l=0; l<10; l++ )
printf( "fak(%u) ist %lu.\n", l, fak(l) );
}
Diese Implementation
von fak() kommt ohne Schleifen aus.
Bei jedem Aufruf mit einem Argument ungleich 0 ruft sich fak()
selbst auf mit einem um 1 verkleinerten Argument und multipliziert das
Ergebnis des Funktionsaufrufs mit seinem eigenen Argument
l. Die mit dem um 1 erniedrigten Argument aufgerufene Funktion
fak() vergleicht ihr eigenes Argument wieder mit 0,
ruft sich gebenenfalls nochmal selbst auf, und so weiter.
Beim Schreiben von rekursiven Algorithmen muß man gut darauf achten,
daß die Aufruffolge beizeiten abbricht (so wie im obigen
fak() beim Erreichen der 0). Ansonsten geht das Programm formal in
eine Endlosschleife
über, da jeder Funktionsaufruf wieder einen weiteren
nach sich zieht. In der Praxis kann ein solches Programm aber nicht
endlos laufen, da bei jedem Funktionsaufruf irgendwo die Programmadresse
hinterlegt wird, an der das Programm nach dem Abarbeiten der Funktion
fortgesetzt
werden soll (Rücksprungadresse).
Dieser Speicherbereich (meist Stack genannt)
wird natürlich irgendwann voll, wenn
eine endlose Rekursion eintritt, und das Programm oder gar der Rechner
verabschieden sich früher oder später26.
Wenn eine rekursiv aufgerufene Funktion lokale automatische Variablen hat, dann hat jede Aufrufebene einen eigenen Satz dieser Variablen. Den Gegensatz dazu bilden Variablen, die mit dem Schlüsselwort static vereinbart sind. Diese static-Variablen existieren auch bei rekursiven Funktionen nur einmal (Attributangaben). Dies liegt daran, daß mit jedem Funktionsaufruf ein eigener stack frame angelegt wird, in dem die automatischen Variablen liegen; jede Rekursionsebene erhält ihren eigenen stack frame (siehe dazu auch Speichermodell eines Prozesses).
Beispiel:
/* rewieof1.c 30. 7.95 kw
*/
void rekursiv( int wieoft )
{
int i;
if( wieoft>0 )
{
i = wieoft;
rekursiv( wieoft-1 );
printf( "i ist %d, wieoft ist %d\n", i, wieoft );
}
}
int main()
{
rekursiv( 10 );
}
Die Funktion rekursiv() wird von main() mit dem
Parameter 10
aufgerufen. rekursiv() ruft sich dann, wenn ihr Parameter
größer ist als 0, mit einem um 1 kleineren Argument wieder selbst auf.
In der lokalen Variablen i wird aber vor dem Aufruf der aktuelle
Wert des Parameters wieoft festgehalten. Nach dem Selbstaufruf
werden der in i gespeicherte Wert und der Parameter wieoft
ausgegeben. Die Programmausgabe
sieht so aus:
i ist 1, wieoft ist 1 i ist 2, wieoft ist 2 i ist 3, wieoft ist 3 i ist 4, wieoft ist 4 i ist 5, wieoft ist 5 i ist 6, wieoft ist 6 i ist 7, wieoft ist 7 i ist 8, wieoft ist 8 i ist 9, wieoft ist 9 i ist 10, wieoft ist 10
Jeder Aufruf der Funktion rekursiv() erzeugt also eine neue
Variable i, da Aufrufe von rekursiv() nach der Zuweisung
an i die Variable nicht mehr verändern.
Man kann aber i stattdessen auch als static
vereinbaren.
Dann verfügen alle Aufrufebenen von rekursiv() nur über eine
gemeinsame Variable, und jede Zuweisung an i verändert diese Variable
auch für die anderen Aufrufebenen sichtbar:
/* rewieof2.c 30. 7.95 kw
*/
void rekursiv( int wieoft )
{
static int i;
if( wieoft>0 )
{
i = wieoft;
rekursiv( wieoft-1 );
printf( "i ist %d, wieoft ist %d\n", i, wieoft );
}
}
int main()
{
rekursiv( 10 );
}
Der einzige Unterschied zum vorhergehenden Beispiel ist das Schlüsselwort
static bei der Definition von i.
Durch den gemeinsamen Zugriff auf eine einzige Variable i verändert sich bei einer Zuweisung an sie der Wert ,,aller`` Variablen i; die Ausgabe sieht dann so aus:
i ist 1, wieoft ist 1 i ist 1, wieoft ist 2 i ist 1, wieoft ist 3 i ist 1, wieoft ist 4 i ist 1, wieoft ist 5 i ist 1, wieoft ist 6 i ist 1, wieoft ist 7 i ist 1, wieoft ist 8 i ist 1, wieoft ist 9 i ist 1, wieoft ist 10
Bei vielen Problemstellungen hat man die freie Auswahl zwischen rekursiven und iterativen Algorithmen. Dann lassen sich nur wenige Programmierer freiwillig auf die Rekursion ein. Oft ist aber eine rekursive Datenstruktur vorgegeben, wie etwa verkettete Listen oder Binärbäume. Dann ist die rekursive Denkweise in aller Regel weniger aufwendig als die iterative. Wenn die Daten keine Verzweigungen aufweisen (lineare Listen), dann kommt man oft noch leicht ohne Rekursion aus. Hat man beispielsweise eine einfach verkette Liste mit double-Werten definiert, dann kann man die Werte in der Liste mit einer iterativen Funktion so ausgeben:
/* relist.c 30. 7.95 kw
*/
#include <stdio.h>
#include <stdlib.h>
/* Struktur eines Listenelements:
*/
struct liste
{
double wert;
struct liste *next;
};
/* iterative Ausgabe einer ganzen Liste:
*/
void zeige( struct liste *l )
{
while( l!=NULL )
{
printf( "%f\n", l->wert );
l = l->next;
}
}
/* Das Hauptprogramm erzeugt eine Liste mit 3 Elementen und
* laesst sie anzeigen:
*/
main()
{
struct liste
*l, /* Anfang der Liste */
*lp; /* wandert die Liste entlang */
/* Speicher fuer erstes Element allokieren: */
lp = l = malloc( sizeof(struct liste) );
/* Wert und Nachfolger eintragen: */
lp->wert = 3.1415;
lp->next = malloc( sizeof(struct liste) );
lp = lp->next;
/* Wert und Nachfolger eintragen: */
lp->wert = 4.12;
lp->next = malloc( sizeof(struct liste) );
lp = lp->next;
/* Wert und Nachfolger eintragen: */
lp->wert = 7.77;
lp->next = NULL; /* Kein Nachfolger, NULL ist
* Markierung fuer das
* Listenende.
*/
zeige( l ); /* Anzeigen lassen
*/
}
Die Funktion zeige() gibt in dem obigen Beispielprogramm
eine einfach verkettete Liste mit Hilfe einer while-Schleife aus.
Diese Funktion ließe sich auch durch eine rekursive Version ersetzen:
Dies sieht in C dann so aus:
/* relistr.c 30. 7.95 kw
*/
/* rekursive Ausgabe einer ganzen Liste:
*/
void zeige( struct liste *l )
{
if( l!=NULL )
{
printf( "%f\n", l->wert );
zeige( l->next );
}
}
Iterative und rekursive Version sind im wesentlichen gleichwertig. Rekursive Algorithmen brauchen aber bei tiefen Verschachtelungen ausreichend Stack (für Aufrufparameter, eventuelle lokale Variablen und die Rücksprungadresse, siehe Speichermodell eines Prozesses), der für die iterative Lösung hier nicht nötig ist. Die Größe des zur Verfügung stehenden Stacks läßt sich bei vielen System beim Übersetzen, Binden oder Laden des Programms festlegen.
Bei rekursiven Algorithmen kann man oft verblüffende Effekte sehr
einfach erreichen. Will man beispielsweise in der iterativen
Version von zeige() die umgekehrte Ausgabereihenfolge
erzwingen, dann muß man einen ziemlichen Aufwand treiben.
Die rekursive Version dagegen kann man leicht dazu überreden:
Die Funktion muß nur
Die Änderung am Quelltext ist minimal:
/* relistrr.c 30. 7.95 kw
*/
/* umgedrehte rekursive Ausgabe einer ganzen Liste: */
void zeige( struct liste *l )
{
if( l!=NULL )
{
zeige( l->next );
printf( "%f\n", l->wert );
}
}
Soweit zu einfach verketteten Datenstrukturen, die sich auch iterativ relativ bequem behandeln lassen. Besitzt eine Datenstruktur Verzweigungen (Bäume), dann kann man die meisten Operationen rekursiv wesentlich einfacher durchführen.
Als Beispiel für Bäume dient eine einfache Verwaltung von eingelesenen Gleitkommazahlen. Im Hauptprogramm hat man ein kleines Menü, mit dessen Hilfe man neue Werte eingeben oder alle gespeicherten Werte sich anzeigen lassen kann.
Ein Binärbaum besteht aus einem Zeiger auf den Wurzelknoten (oder NULL, wenn der Baum anfangs noch leer ist). Der Wurzelknoten kann einen Wert speichern (hier die Gleitkommazahl) und auf einen linken sowie auf einen rechten Nachfolger verweisen, ebenso jeder weitere Knoten. Ein Knoten kann als linken und/oder rechten Nachfolger eine NULL eingetragen haben; dann existiert eben derjenige Nachfolger nicht. Ein Knoten, der weder einen linken noch einen rechten Nachfolger hat, heißt Blatt.
Jeder Knoten kann wieder als Wurzel eines kleineren Teilbaums betrachtet werden.
Die Daten in einem solchen Baum werden nun so eingetragen, daß der Wert eines jeden Knotens größer ist als der eines eventuellen linken Nachfolgers, aber kleiner als der Wert eines eventuellen rechten Nachfolgers.
Beim Einfügen in den Baum muß man den Wert der Wurzel betrachten und entsprechend links oder rechts davon eintragen. Angenommen, man muß links eintragen, weil der neue Wert kleiner ist als der Wert der Wurzel, dann muß man den linken Nachfolger der Wurzel betrachten und links oder rechts davon eintragen, und so weiter. Hat ein Knoten auf der Seite, auf der man eintragen muß, keinen Nachfolger, dann hängt man dort als neuen Nachfolger das einzutragende Element ein.
Um einen Wert im Baum zu suchen, kann man ebenfalls bei der Wurzel beginnen, und mit links/rechts-Entscheidungen bis zur gesuchten Stelle vordringen. Trifft man unterwegs auf NULL, dann existiert das gesuchte Element nicht.
Ein Binärbaum läßt sich leicht sortiert ausgeben, wenn die Funktion zur Ausgabe des Baums einfach sich selbst mit dem linken Teilbaum aufruft (der nur kleinere Werte als die Wurzel enthält), dann den Wert der Wurzel ausgibt, und sich dann mit dem rechten Teilbaum selbst aufruft. Dieses Vorgehen heißt in order-Durchlauf.
Sowohl die Funktion einfuege_baum() zum Einfügen eines
neuen Elements in den Baum als auch zeige_baum() zur
sortierten Anzeige des Baums sind rekursiv gelöst:
/* rebaum.c 30. 7.95 kw
*
* Testprogramm fuer einfache Binaerbaeume.
*
* Das Programm bietet ein kleines Menue an, mit dessen
* Hilfe man Zahlen eingeben kann, alle eingegebenen Zahlen
* sortiert wieder ausgeben, oder das Programm beenden kann.
*
* Ein Knoten in einem Baum besteht aus den zu speichernden
* Daten (hier als Beispiel eine Gleitkommazahl), sowie
* zwei Zeigern auf weitere Knoten (links, rechts
* Der Baum wird nun so sortiert aufgebaut, dass alle Werte
* in einem linken Nachfolger und dessen Nachfolgern klei
* ner sind als der Wert jeden Knotens und alle Nachfolger
* auf der rechten Seite groesser
* Hat ein Knoten keinen linken oder rechten Nachfolger
* dann hat (links) bzw. (rechts) den Wert NULL
*/
#include <stdlib.h>
#include <stdio.h>
#include <ctype.h>
/* Datenstruktur fuer einen Knoten:
*/
struct baum
{
double wert;
struct baum *links, *rechts;
};
/* Der eigentliche Baum besteht aus einem Zeiger auf das
* erste Element (die "Wurzel") und den Nachfolgern.
* Solange kein Element gespeichert ist, hat die Wurzel den
* Inhalt NULL.
*/
struct baum *wurzel = NULL;
void einfuege_baum( double zahl, struct baum **baum_p )
{
/* an der aktuellen Stelle einfuegen, wenn dort
* noch nichts steht:
*/
if( NULL==(*baum_p) )
{
/* Platz fuer einen Knoten holen ...
*/
*baum_p = malloc( sizeof(struct baum) );
if( NULL==(*baum_p) )
{
fprintf( stderr,
"nicht genug Speicher!\n"
);
exit(3);
}
/* ... den Wert eintragen und die Nachfolger
* zu NULL setzen:
*/
(*baum_p)->wert = zahl;
(*baum_p)->links = NULL;
(*baum_p)->rechts = NULL;
}
else
{
/* an der aktuellen Stelle steht schon etwas!
* Also links oder rechts im Baum eintragen, je nach
* Groesse der einzutragenden Zahl:
*/
if( zahl < (*baum_p)->wert )
einfuege_baum( zahl, &((*baum_p)->links) );
if( zahl > (*baum_p)->wert )
einfuege_baum( zahl, &((*baum_p)->rechts) );
else
; /* gleiche Zahl nicht nochmal eintragen! */
}
}
/* gibt einen Baum mit einem inorder-Durchlauf aus, also
* sortiert:
*/
void zeige_baum( struct baum *baum )
{
/* zeigt baum ueberhaupt auf ein Element?
*/
if( baum!=NULL )
{
/* erst den linken Teilbaum ausgeben, ... */
zeige_baum( baum->links );
/* ... dann den aktuellen Wert, ... */
printf( "Knoten hat den Wert %f\n", baum->wert );
/* ... zuletzt den rechten Teilbaum: */
zeige_baum( baum->rechts );
}
}
/* Bietet ein einfaches Menue an und liefert das
* entsprechende Zeichen zurueck:
*/
int get_menue( void )
{
char c;
printf( " Bitte Auswahl eingeben:\n" );
printf( " (E)infuegen, (Z)eigen, (A)bbruch\n" );
do
{
c = toupper( getchar() );
}
while( c!='E' && c!='Z' && c!='A' );
return c;
}
/* Kleines Testprogramm.
*/
int main()
{
double wert;
int auswahl;
/* Scheife, bis 'A' eingegeben wird:
*/
while( ( auswahl=get_menue() )!='A' )
{
switch( auswahl )
{
case 'E' :
/* Einfuegen gewuenscht.
* Wert von Tastatur lesen:
*/
printf( "Bitte Wert eingeben: " );
scanf( "%lf", &wert );
/* und einfuegen:
*/
einfuege_baum( wert, &wurzel );
break;
case 'Z' :
/* Zeigen gewuenscht
*/
zeige_baum( wurzel );
break;
default :
break;
}
}
}
Theoretisch läßt sich jede Rekursion durch eine mehr oder wenige aufwendige Iteration ersetzen. Ob dies allerdings sinnvoll ist, läßt sich pauschal nicht sagen. Die Umwandlung einer rekursiven Lösung in eine iterative kann sehr einfach sein, wenn nur wenige Daten beteiligt sind und die Daten insbesondere keine Verzweigungen aufweisen (wie beispielsweise lineare Listen, siehe das Beispiel oben). Hat die zugrundeliegende Datenstruktur dagegen Verzweigungen (Bäume), dann kann die Umwandlung eines rekursiven Algorithmus in einen iterativen schnell sehr aufwendig und unsinnig werden.
Viele rekursive Algorithmen sind bestechend einfach und effektiv. Die iterative Version eines Algorithmus ist in der Regel etwas schneller, da bei Rekursion für jede Aufrufebene Parameter und Rücksprungadresse gespeichert werden müssen und jeder Rücksprung ebenfalls etwas Zeit kostet. Insbesondere sehr kurze Funktionen werden dadurch relativ stark gebremst; bei länger rechnenden Funktionen ist der Anteil des Aufrufs an der Rechenzeit geringer. In vielen Fälle ist die rekursive Lösung leichter verständlich und leichter zu programmieren; dann sollte sie man auch nicht mutwillig durch eine iterative ersetzen.
Wenn man rekursive Datenstrukturen (Bäume, Listen) verwendet, dann sind entsprechend gebaute rekursive Funktion die natürliche Lösung. Viele klassische Algorithmen (quick sort) sind ebenfalls in der rekursiven Form einfacher und direkter.
Wem die Rekursion dagegen einfach suspekt und unsympathisch ist, den wird man ohnehin nie dazu überreden können27.
AnyWare@Wachtler.de