[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
 

#include <stdio.h> 
int fakultaet ( int );

int fakultaet ( int n ) 

if (n == 1) return 1;

return n * fakultaet ( n - 1 ); 

}

void main ( void

int zahl; 
printf("\nBitte geben sie eine Zahl ein : "); 
scanf ("%d",&zahl); 
printf ("\n\n%d Fakultät = %d",zahl,fakultaet(zahl)); 
}

Screenshot des ausgeführten Programms

Um zu verdeutlichen, wie das Programm arbeitet, wieder einen mathematischen Abstecher.
 

4! 
    =  4 * !3

    =  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 * fakultaet(3)

    =  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.

Skizze: Stack der Variablen n des Fakultaetmoduls (push)

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 .

Skizze: Stack der Variablen n des Fakultaetmoduls (pop)

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.
 

#include <stdio.h> 
int fakultaet ( int );

int fakultaet ( int n ) 

int rueck;
if (n == 0) return 1;
rueck = n * fakultaet ( n - 1 ); 
printf (" %d",n);
return rueck;
}

void main ( void

int zahl; 
printf("\nBitte geben sie eine Zahl ein : "); 
scanf ("%d",&zahl); 
printf ("\n\n%d Fakultaet = %d",zahl,fakultaet(zahl)); 
}

Screenshot des ausgeführten Programms


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.
 

#include <stdio.h> 
void Zeige(char*);

void Zeige ( char *c ) 

char *d = c;

if (*c != '\0')
{

Zeige (++d);
printf ("%c",*c);
}
}

void main ( void

char Wort[20]; 

printf ("\nBitte geben sie ein Wort ein : "); 
scanf ("%s",Wort); 
Zeige(&Wort[0]);

}

Screenshot des ausgeführten Programms



[Inhalt][0][1][2][3][4][5][6][7][8][9][10][11][12][13][14][15][16][17]