[Inhalt][0][1][2][3][4][5][6][7][8][9][10][11][12][13][14][15][16][17]
| Der 8. Teil der unendlichen Geschichte |
Diesmal werden wir uns mit dem Thema Rekursion beschäftigen und
einem besonderen Speicher, dem Stack, beschäftigen. Der Vorteil von
Rekursionen ist, das sie sehr klein und effizient sind. Der Nachteil ist,
das in der Regel die Stackgröße sehr groß wird und rekursive
Funktionen schwer nachzuvollziehen sind.
| Rekursion |
Rekursionen sind Zahlenfolgen, bei denen ein Zahlenelement durch einen
Vorgänger oder Nachfolger bestimmt wird. Wenn man eine Vorschrift
zu der Bildung einer Zahlenfolge hat, die wie folgt aussieht
| A 1 = 1
A n+1 = A n + 1 |
erhält man die Zahlenfolge
| 1 , 2 , 3 , ... |
Das Ganze kann man nun auch anders herum durchführen:
| A n = A n+1 - 1 |
Abbruchbedingung:
| A 1 = 1 |
Die Zahlenfolge bleibt die selbe, nur fangen wir bei einer Anfangszahl,
z.B. 3 , an und bilden die Vorgänger. Damit das nicht ewig weitergeht,
müssen wir eine Abbruchbedingung angeben, wo wir aufhören können.
Die ist in unserem Fall A 1 , da dies unser Startwert
in der zu bildenden Zahlenfolge ist. Rekursionen haben den Vorteil, das
sie durch ihre einfachen Zuweisungsvorschrift, jedem folgendem Element
einen Wert zuweisen können und relativ klein sind. Statt der Variablen
Axkann
jede beliebige mathematische Abbildunsvorschrift stehen. Das wird am Besten
an ein paar kleinen Beispielen klar.
| Fakultätsberechnung |
In der Mathematik bedeutet die Fakultät folgendes:
| n! = 1 * 2 * 3 * .. * n |
n! spricht man n-Fakultät.Es werden also alle ganzen
Zahlen bis n miteinander multipliziert. Wenn wir nun ein rekursives
Programm in C schreiben, könnte es z.B. so aussehen
int fakultaet ( int ); int fakultaet ( int n )
return n * fakultaet ( n - 1 ); void main ( void )
printf("\nBitte geben sie eine Zahl ein : "); scanf ("%d",&zahl); printf ("\n\n%d Fakultät = %d",zahl,fakultaet(zahl)); |
Um zu verdeutlichen, wie das Programm arbeitet, wieder einen mathematischen
Abstecher.
4!
= 4 * 3 * !2 = 4 * 3 * 2 * !1 = 4 * 3 * 2 * 1 |
Bei 1 setzen wir unsere Abbruchbedingung. Es ist mathematisch
definiert: 0! = 1, aber da 1 * 1 = 1 gilt, können wir
die Abbruchbedingung bei n = 1 festlegen. Und genau nach dem oberen
Arbeitsschema arbeitet auch unser Programm. Es bekommt als Übergabewert
die Zahl n, deren Fakultät berechnet werden soll und multipliziert
diese mit dem Wert der Fakultät von
n-1 . Das geschieht solange,
bis n=1 ist. Schematisch sieht das etwa so aus:
fakultaet(4)
= 4 * 3 * fakultaet (2) = 4 * 3 * 2 * fakultaet (1) = 4 * 3 * 2 * 1
= 24 |
| Der Stack |
Um etwas genauer auf die Funktionsweise des Programmes eingehen zu können, lernen wir den Stack , oder auch Kellerspeicher genannt, kennen. Allgemein kann man sagen, das der Stack ein Speicher ist, der nur 2 Befehlsarten kennt, Daten einfügen und Daten entfernen, auch als push und pop bezeichnet. Wird nun wie in unserem Beispiel zur Fakultätsberechnung das Modul von sich selbst aufgerufen, so stellt dies die Verwaltung der Variablen vor ein großes Problem. Man will auf den aktullen Variablenwert zugreifen und außerdem die Variablen aus dem aufrufenden Modul behalten. Erschwerend kommt hinzu, das die Bezeichner sogar identisch sind. Zur Verwaltung dieser und ähnlicher Probleme gibt es den Stack. Ihn kann man sich wie einen Speicher vorstellen, bei dem man nur auf das oberste Element zugreifen kann. Wird etwas hinterlegt, so wird das aktuelle Element oben auf die anderen aufgelegt, wird etwas entnommen, so wird das oberste Element entfernt und das darunterliengende Element kommt zum vorschein.
Wird nun ein Unterprogramm aufgerufen, passiert genau das vorher Beschriebene. Die Variablen des aufrufenden Moduls werden auf einen Stack gelegt und die neuen Variablen praktisch oben aufgesetzt. da man nur auf das oberste Element zugreifen kann, gelten nur die Variablen des obersten Elements/Moduls. Wird das aufgerufene Modul verlassen, so wird das oberste Element entfernt und die vorherigen Variablen kommen zum Vorschein. Bei unserem Beispielprogramm ruft sich das Modul solange selber auf, bis eine Abbrucbedingung erfüllt ist und es sich nicht mehr selber aufruft. Obere Skizze verdeutlicht nochmal was mit dem Stack passiert, wenn das Modul mit dem Wert 4 aufgerufen wurde. Bei n = 1 enthält der Stack die Werte und gibt sie sozusagen in umgekehrter Reihenfolge wieder zurück vom zuletzt aufgerufenen Modul bis zum zuerst aufrufenden. Würden wir alle Elemente einzeln ausgeben lassen, so könnte man sehen, das zuerst die 1, dann die 2, die 3 und zuletzt die 4 zurückgegeben wird, welche dann miteinander multipliziert werden, also 1 * 2 * 3 * 4 = 24 .
Wir modifizieren unser Fakultätsprogramm etwas und lassen bei jedem
Aufruf des Moduls den Wert für n ausgeben.Nach den Vorüberlegungen
sollten nun die Zahlen in umgekehrter Reihenfolge aufgerufen werden. Wie
man sieht wurde das Programm wegen des vorherign Aufbaus leicht modifiziert,
da wir ja nun die aktuellen Werte der Variablen n im Modul korrekt
ausgeben wollen.
int fakultaet ( int ); int fakultaet ( int n )
if (n == 0) return 1; rueck = n * fakultaet ( n - 1 ); printf (" %d",n); return rueck; void main ( void )
printf("\nBitte geben sie eine Zahl ein : "); scanf ("%d",&zahl); printf ("\n\n%d Fakultaet = %d",zahl,fakultaet(zahl)); |
| Rückwärtsausgabe über den Stack |
Um ein weiteres Beispiel zu bringen, schreiben wir ein weiteres Programm,
welches ein eingegebenes Wort rückwärts wieder ausgibt. Dazu
benutzen wir wie vorher den Stack und legen Buchstabe für Buchstabe
auf ihm ab. Jeder der abgelegten Buchstaben wird ausgegeben. Den Skizzen
zufolge werden dann, ausgehen vom letzten Aufruf alle in rückwärtiger
Reihenfolge wieder ausgegeben. Zur Übung sollte man versuchen das
folgende Beispiel zu verstehen. Eventuell ist es dabei hilfreich einmal
eine Skizze des Stacks von Hand mit den darauf hinterlegten Werten anzufertigen.
Hier wenden wir auch das Wissen an, was wir uns im Kapitel
über Zeiger und Felder schon über Strings aneigneten.
void Zeige(char*); void Zeige ( char *c )
if (*c != '\0')
printf ("%c",*c); void main ( void )
printf ("\nBitte geben sie ein Wort ein : ");
|
| ...das Obligatorische |
Autor: Sebastian Cyris PCDBascht@aol.com
Dieser C-Kurs dient nur zu Lehrzwecken! Eine Vervielfältigung ist ohne vorherige Absprache mit dem Autor verboten! Die verwendete Software unterliegt der GPL und unterliegt der Software beiliegenden Bestimmungen zu deren Nutzung! Jede weitere Lizenzbestimmung die der benutzten Software beiliegt, ist zu beachten!