SUCHE MIT Google
Web virtualuniversity.ch
HOME DIDAKTIK ECDL ELEKTRONIK GUIDES HR MANAGEMENT MATHEMATIK SOFTWARE TELEKOM
DIENSTE
Anmeldung
Newsletter abonnieren
Sag's einem Freund!
VirtualUniversity als Startseite
Zu den Favoriten hinzufügen
Feedback Formular
e-Learning für Lehrer
Spenden
Autoren login
KURSE SUCHEN
Kurse veröffentlichen

Suche nach Datum:

Suche mit Schlüsselwort:

Suche nach Land:

Suche nach Kategorie:
PARTNER
ausbildung24.ch - Ausbildungsportal, Seminare, Kursen... 

 
HTMLopen.de - Alles was ein Webmaster braucht

 
PCopen.de - PC LAN Netze und Netzwerke - alles was ein IT Profi und Systemtechnicker braucht

SOFTWARE
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
                                       

DIPLOMARBEITEN UND BÜCHER

Diplomarbeiten zum Runterladen:

Suche im Katalog:
Architektur / Raumplanung
Betriebswirtschaft - Funktional
Erziehungswissenschaften
Geowissenschaften
Geschichtswissenschaften
Informatik
Kulturwissenschaften
Medien- und Kommunikationswissenschaften
Medizin
Psychologie
Physik
Rechtswissenschaft
Soziale Arbeit
Sozialwissenschaften


JOBS
HOME | E-LEARNING | SITEMAP | LOGIN AUTOREN | SUPPORT | FAQ | KONTAKT | IMPRESSUM
Virtual University in: Italiano - Français - English - Español
VirtualUniversity, WEB-SET Interactive GmbH, www.web-set.com, 6301 Zug

Partner:   Seminare7.de - PCopen.de - HTMLopen.de - WEB-SET.com - YesMMS.com - Ausbildung24.ch - Manager24.ch - Job und Karriere