Rekursion:
Ein rekursiver Algorithmus enthält zunächst noch ungelösteProbleme, zu deren Lösung man denselben Algorithmus nochmalsanwenden muß. |
Eine Beschreibung eines rekursiven Algorithmus liegt also dann vor,wenn in einer elementaren Anweisung ein Verweis auf den eigenen Algorithmus erfolgt. (Man sagt auch: "Der Algorithmus ruft sich selbst auf.") Dabei wird der Code der Funktion mehrfach rekursiv durchlaufen, d. h. der Code ist nach wie vor nur einmal vorhanden, aber er wird mehrfach mit unterschiedlichen Werten durchlaufen. Möglich ist das nur durch eine besondere Eigenschaft der Funktions-Codes, die als
"Wiedereintrittsfähigkeit" bezeichnet wird.
Um das zu erreichen, dürfen die lokalen Variablen und Parameter
nicht unter einer festen Speicheradresse gespeichert werden,
sondern es muß ihnen bei jedem Aufruf der Funktion ein neuer Speicherplatz
zugewiesen werden ("dynamische" Speicherverwaltung). Dazu
wird in der Regel ein Stack verwendet, der meist per Software
realisiert wird. Beim Funktions-Aufruf werden - soweit vorhanden - die
Parameter auf den Stack gerettet und für die lokalen Variablen
Platz auf den Stack reserviert (die Rücksprungadresse befindet
sich, ebenfalls auf dem Stack). Bei Werteparametern
wird der Wert selbst gespeichert, bei Variablenparametern
die Adresse der Variablen.
Mit jedem rekursiven Aufruf wächst also der Speicherbedarf des
Stack. Da irgendwann jeder Speicher aufgebraucht ist, muß die
rekursive Aufruffolge irgendwann durch ein sogenanntes Abbruch-Kriterium
unterbrochen werden. Das führt uns zu einer generellen
Analyse eines rekursiven Funktion. Der Anweisungsteil eines rekursiven
Funktion besteht aus:
- Test eines oder mehrerer Parameter oder globaler Variablen auf
Erfülltsein des Abbruchkriteriums.
- Falls das Abbruchkriterium nicht erfüllt ist, erfolgt der
Aufruf der Funktion mit mindestens einem modifizierten Parameter
(damit das Abbruchkriterium erreicht wird).
Ein ähnliches Verfahren ist übrigens aus der Mathematik bekannt,
der Beweis eines Lehrsatzes durch vollständige Induktion. Rekursion
ist nicht an eine bestimmte Programmiersprache gebunden, sie
ist auch auf Ebene des Maschinencodes möglich (der Stack muß dann
gegebenenfalls zusätzlich realisiert werden).
Anmerkung: Bei der Formulierung von
rekursiven Algorithmen besteht leicht die Gefahr, die Bedingung der
Finitheit zu verletzen.
Rekursive Algorithmen ermöglichen zum Teil sehr elegante
Programmierung. Die Stackoperationen beim wiederholten Aufruf des
Funktion machen die Ausführung aber langsamer. Grundsätzlich ist jeder
rekursive Algorithmus auch durch Wiederholungsanweisungen zu
realisieren. Problem: Nachweis, daß Rekursion vor einem Stack-Überlauf
abbricht.
Beispiel: Zahlenumwandlung Dezimal-Binär
Zunächst die nicht-rekursive Variante.
Programm in C-Notation:
#include <stdio.h>
/* Programm zur Umwandlung von Dezimalzahlen in Binärzahlen */
void main(void)
{
int dez, i;
int dual[8];
for(i = 0; i < 8; i++)
dual[i] = 0; /* Dualzahl löschen */
scanf("%d", &dez);
i = 0;
if ((dez >= 0) && (dez <= 255)) /* Wert zulässig? */
do
{ /* sukzessive Division */
dual[i] = dez % 2; /* aktuelle Dualstelle speichern */
dez = dez/2; /* abdividieren */
i++;
} while(dez > 0);
for(i = 7; i > -1; i--)
printf("%1d", dual[i]); /* Ausgabe Dualstellen */
printf("\n"); /* neue Zeile */
}
Zahlenumwandlung Dezimal-Binär rekursiv
Formalisierung des Problems:
d sei die zu konvertierende Dezimalzahl.
- Falls d > 1 ist, wende den Algorithmus auf den Wert (d div 2) an.
- Gib die letzte Stelle der Dualzahl (d mod 2) aus.
Damit ist die Berechnung auf einen Induktionsschluß von n dualen Stellen
auf n-1 duale Stellen zurückgeführt. Die Umkehrung der Ausgabereihenfolge
erfolgt implizit durch die Rekursion.
Beispiel: Aufrufstruktur der Binärumwandlung der Dezimalzahl 13.
Senkrecht untereinander stehende Kästchen (durch gestrichelte Linien
verbunden) bezeichnen dieselbe "Inkarnation" der Funktion.
Vorteil: Es muß keine Array-Variable für die Speicherung der
Dualstellen vereinbart werden. Der Wertebereich ist lediglich durch die
Größe des Aufruf- und Parameter-Stacks begrenzt.
Nachteil: Durch die rekursiven Aufrufe erhöhen sich Speicherbedarf
und Rechenzeit.
Programm in C-Notation:
#include <stdio.h>
/* dezimal-dual Wandlung */
void bin(int dezimal)
{
if (dezimal > 1) /* Abbruchbedingung */
bin(dezimal / 2); /* rekursiver Aufruf */
printf("%1d", dezimal % 2); /* Ausgabe i-te Stelle */
}
void main(void)
{
int dez;
scanf("%d ", &dez); /* Eingabe */
bin(dez); /* Funktionsaufruf */
printf("\n"); /* neue Zeile */
}
Zum Testen wurde die FUnktion bin um zwei AUsgaben erweitert:
void bin(int dezimal)
{
printf("Aufruf von bin(%d)\n",dezimal);
if (dezimal > 1) /* Abbruchbedingung */
bin(dezimal / 2); /* rekursiver Aufruf */
printf("Ruecksprung von bin: %1d\n", dezimal % 2); /* Ausgabe i-te Stelle */
}
Für die Eingabe 179 liefert bin() dann folgende Ausgabe (zur besseren
Erkennbarkeit sind die Zeilen entsprechend der Aufrufverschachtelung eingerückt):
Aufruf von bin(179)
Aufruf von bin(89)
Aufruf von bin(44)
Aufruf von bin(22)
Aufruf von bin(11)
Aufruf von bin(5)
Aufruf von bin(2)
Aufruf von bin(1)
Ruecksprung von bin: 1
Ruecksprung von bin: 0
Ruecksprung von bin: 1
Ruecksprung von bin: 1
Ruecksprung von bin: 0
Ruecksprung von bin: 0
Ruecksprung von bin: 1
Ruecksprung von bin: 1
Weiteres Beispiel:
Beim Spiel Türme von Hanoi hat man n unterschiedlich große
Lochscheiben, die sich auf drei möglichen Ablageplätzen befinden
können. In der Ausgangssituation befinden sich alle Scheiben als Turm der
Größe nach geordnet auf einem Platz (die größte Scheibe unten,
die kleinste Scheibe oben).
Das Problem besteht darin, den Turm auf einen bestimmten anderen Platz
zu bringen, wobei
- immer nur eine Scheibe bewegt werden und
- niemals eine grössere Scheibe auf einer kleineren liegen darf.
Zur Lösung geht man wie folgt vor:
- zuerst werden n-1 Scheiben "irgendwie" auf den übrigen dritten Platz
gebracht (--> das verkleinerte Problem),
- dann bringt man die unterste Scheibe auf den Endplatz (Trivialfall),
- danach werden auch die n-1 Scheiben auf den Endplatz gebracht
(ebenfalls verkleinertes Problem).
Kaum ein anderes Beispiel demonstriert so eindrucksvoll die Eleganz
von rekursiven Algorithmen:
/* hanoi : Zugfolge fuer n Scheiben von Platz p1 nach Platz p2 */
void hanoi(int n, int p1, int p2)
{
int parkplatz;
if(n > 1)
{
/* n-1 Scheiben auf Parkplatz */
parkplatz = 6-p1-p2;
hanoi(n-1, p1, parkplatz);
}
/* unterste Scheibe auf Endplatz */
printf("Zug von %d nach %d\n", p1, p2);
if(n > 1)
/* n-1 Scheiben auf Endplatz */
hanoi(n-1, parkplatz, p2);
}
Die Rekursivität kann auch über mehrere Aufrufebenen erfolgen.
Ein Algorithmus A verweist z. B. in einer elementaren Anweisung auf den
Algorithmus B, und dieser verweist wieder auf den Algorithmus A.
Iteration
Ein iterativer Algorithmus enthält eine Wiederholung
in der, ausgehend von bekannter Information, Zwischenergebnisse
erzeugt werden, die wiederum die Basis für die Zwischenergebnisse
im nächsten Wiederholungs- (Iterations-) Schritt bilden.
Iterative Algorithmen treten in der Datenverarbeitung sehr
häufig auf. Man kann grundsätzlich 2 Arten von Iterationen
unterscheiden:
- Algorithmen mit einer vorher bekannten Anzahl von
Wiederholungsschritten. Beispiel: Berechnung von an:
an = a * a * ... *a * a
mit n Iterationsschritten.
- Algorithmen mit einer vorher unbekannten Anzahl von
Wiederholungsschritten. Beispiel: Suche nach der größten
2-er Potenz kleiner/gleich M:
Gegeben ist eine natürliche Zahl M. Gesucht ist eine natürliche
Zahl k, für die gilt: 2k+1 > M >= 2k
Beispiel für eine iterative Berechnung, die näherungsweise
Wurzel-Berechnung:
#include
#include
void main()
{
float a, eps, x, y;
printf("Näherungsweise Wurzelberechnung");
printf("\nWert a: ");scanf("%f",&a);
printf("Grenze: ");scanf("%f",&eps);
y=a/2;
do
{
x = y;
y = (x + a/x)/2;
}
while (fabs(y-x) > eps);
printf("Ergebnis:%f", y);
}
In der Mathematik werden häufig rekursive Definitionen benutzt, die
aber bei der Umsetzung in einen Berechnungsalgorithmus sowohl als
Iteration als auch als Rekursion verwirklicht werden können.
Ein Beispiel haben wir schon bei der Dezimal-Binär-Umwandlung gesehen.
Anmerkung:
Die rekursive Formulierung eines Algorithmus ist meist kürzer
und daher übersichtlicher, aber wegen der unzulänglichen
Implementierung von rekursiven Verfahren sollten für
Datenverarbeitungsanlagen wenn möglich immer iterative Verfahren
gewählt werden.
Nicht immer kann zu einer rekursiven Definition sehr leicht ein
iterativer Berechnungsalgorithmus gefunden werden. Beispiel:
Berechnung der Ackermann-Funktion A(n,m)
A(n,m) = A(n-1,A(n,m-1))
mit
A(n,0) = A(n-1,1)
und
A(0,m) = m + 1
| 
DIENSTE
