Startseite   |  Site map   |  A-Z artikel   |  Artikel einreichen   |   Kontakt   |  
  


informatik artikel (Interpretation und charakterisierung)

Rekursion -


1. Java
2. Viren



1.1 Allgemeines zu Rekursionen Die Rekursion ist ein fundamentales Konzept, das in der Mathematik und in der Informatik im Einsatz ist. Zerlegt man ein Problem in Teilprobleme und erhält dann wieder das Problem von dem ausgegangen wurde, so handelt es sich hierbei um eine Rekursion.
Dies funktioniert so, das sich eine Funktion immer wieder selbst aufruft, und das Problem wieder in Teilprobleme zerlegt wird. Es wird so lange zerlegt, bis das Teilproblem so einfach ist, daß es ausprogrammiert werden kann. Der Funktion muß immer das Problem übergeben werden, welches in Teilprobleme zerlegt wird und dann wieder übergeben wird. Tritt das Problem nicht mehr auf, d.h. ist Abbruchbedingung ist bereits erfüllt wird mit Hilfe eines Rückgabewertes die Rekursion beendet. Ansonsten wird das Ergebnis des Aufrufs für die Berechnung des Rückgabewertes verwendet.









1.2 Beispiele
1.2.1 Ausgabe eines Binärbaumes (sog. Traversierung)
Eine Anwendung auf die Rekursionen regelrecht zugeschnitten sind, sind Binärbäume, deren iterative Programmierung ziemlich aufwendig wäre.



C-Funktion traverse: Es wird solange in den linken Ast des Knotens verzweigt, bis es keinen linken Ast mehr gibt. Dann wird der aktuelle Knoten ausgegeben und in den ev. Vorhandenen rechten Ast verzweigt. Gibt es auch keinen rechten Ast mehr, dann wird in den Knoten der übergeordneten Ebene zurückgegangen. Solange bis der ganze Baum ausgegeben wurde. Die Ausgabe der Knoten erfolgt nach der Numerierung. Der erste Knoten ist logischerweise links unten, dann zu seinem übergeordneten und dann zum untergeordneten rechten Knoten.

void traverse(KNOTEN *pknoten)
{

if(pknoten-left) traverse(pknoten-left);

knoten_ausgeben(pknoten);

if(pknoten-right) traverse(pknot-right);
}


1.2.2 Fakultät einer Zahl
Die Fakultät einer Zahl x ist folgendermaßen definiert: x! = x * (x-1)!. Das wird solange fortgeführt, bis x-n den Wert 1 erreicht hat.
z.B: 5! = 5 * 4 * 3 * 2 *1
C-Funktion factorial: Berechnet die Fakultät einer Zahl.
Lösung mit Rekursion:

int factorial(int x)
{

if(x==1) return 1;

return x * factorial(x-1);
}
Lösung mit Iteration(mit Schleifen):

int factorial( int x)
{

for(int factor=1; x 1; x--) factor = factor * x;

return factor;
}




1.3 Arten von Rekursionen

1.3.1 Lineare Rekursion
Die Tiefe der möglichen Rekursion ist 1. Eine linear - rekursive Funktion ruft sich maximal einmal selbst auf. Diese Funktionen können leicht auch iterativ programmiert werden.


1.3.2 Kaskadenförmige Rekursion
Es kann vorkommen, daß sich die Funktion mehrmals selbst aufruft. Die Bearbeitung von Bäumen ist typischerweise kaskadenförmig und die Adaptierung in iterative Programmierung ist nicht so ohne weiteres möglich.


1.4 Gegenüberstellung Rekursion und Iteration
Grundsätzlich wird bei einer Rekursion die Funktion immer wieder aufgerufen bis die Abbruchbedingung erfüllt ist. Bei der Iteration wird das Problem mit Hilfe von Schleifen gelöst. Theoretisch kann jede(!) rekursive Funktion auch als iterative Funktion ausprogrammiert werden, jedoch gibt es Probleme für die sich die Rekursion besonders gut eignet, zum Beispiel Binärbäume.

Es gibt drei Kriterien:







Kriterium Rekursion Iteration
Laufzeit langsam schneller

Speicher viel wenig
Aufwand gering höher


Ob man nun Rekursionen oder Iterationen verwendet, hängt vom jeweiligen Problem ab und von der Wichtigkeit der jeweiligen Kriterium ab. Wenn es möglich ist, sollte man lineare Rekursionen in Iterationen umwandeln und kaskadenförmige Rekursionen belassen.

 
 



Datenschutz
Top Themen / Analyse
indicator CMOS
indicator Monitoring
indicator Löschen einzelner Seiten im Cache
indicator AMD, Intels Konkurrenz kann nicht mehr mithalten8
indicator Einzugsscanner
indicator Synchrone und asynchrone Busse
indicator Verbindung zwischen Netzen/Netzteilen
indicator Entfernung aus dem Speicher
indicator Was hat ein Computervirus für genau definierte Aufgaben?
indicator Die Architektur von PHP




Datenschutz
Zum selben thema
icon Netzwerk
icon Software
icon Entwicklung
icon Windows
icon Programm
icon Unix
icon Games
icon Sicherheit
icon Disk
icon Technologie
icon Bildung
icon Mp3
icon Cd
icon Suche
icon Grafik
icon Zahlung
icon Html
icon Internet
icon Hardware
icon Cpu
icon Firewall
icon Speicher
icon Mail
icon Banking
icon Video
icon Hacker
icon Design
icon Sprache
icon Dvd
icon Drucker
icon Elektronisches
icon Geschichte
icon Fehler
icon Website
icon Linux
icon Computer
A-Z informatik artikel:
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z #

Copyright © 2008 - : ARTIKEL32 | Alle rechte vorbehalten.
Vervielfältigung im Ganzen oder teilweise das Material auf dieser Website gegen das Urheberrecht und wird bestraft, nach dem Gesetz.
dsolution