Rekursion

vogtländer

Erfahrenes Mitglied
Hallo,

inspiriert von dem Mathematik-Threat und der daraus entnommenen Intention, allgemeine Probleme der Informatik zu besprechen, wollte ich mal das Thema Rekursion zur Diskussion stellen.

Gibt es klassische Anwendungsgebiete?
Was sind die Vorteile und kann man die überhaupt klar definieren?
Und kann mir vielleicht jemand sagen, wieso der Quicksort-Algorithmus so schnell ist?
Welche gängigen Beispiele gibt es für Rekursion?

Vielleicht kann hier auch eine kleine Bibliothek für diverse Probleme entstehen, die sehr schön durch rekursive Algorithmen gelöst werden können, wie die Türme von Hanoi oder die Fakultät.

Gruß
Falk
 
Also nur ganz kurz ein Beispiel für eine Rekursion :

Ich habe folgende Logik für meine Dateisucherklasse
(http://www.tutorials.de/tutorials122049.html) verwendet
und bin eigentlich recht zufrieden mit dem Ergebniss.

Ich glaube nicht das es anders möglich gewesen wäre
und ich möchte es auch garnicht wissen.

Also kurz zur Logik :
(mehr Information bitte dem Link entnehmen)

Code:
 öffne Verzeichniss (aus Parametern)
 durchlaufe Verzeichnissinhalt (Eintrag für Eintrag)
 wenn Eintrag eine Datei ist, speichere den Eintrag
 wenn Eintrag ein Verzeichniss ist, rufe dich selbst auf

Soviel zur groben Logik hinter meiner Rekursion.
Ich habe das Ganze noch mit ein paar zusätzlichen
Filtern versehen um bestimmte Dateien oder Endungen
herauszufiltern, wer mehr wissen möchte poste bitte
hier.

Jona
 
Hallo zusammen,
zum QuickSort: Der Algorithmus ist so schnell, weil er nach dem Prinzip "Divide and Conquer" arbeitet, das heißt, das Ausgangsproblem (=Zahlenmenge sortieren) wird nach und nach in Teilprobleme (=Teilmengen) unterteilt, die dann zunächst einzeln gelöst (=sortiert) werden und dann wird das Ganze noch zu einem Endergebnis zusammengeführt.
Dabei ist der QS ein rekursiver Sortieralgorithmus.

Das macht ihn schneller als beispielsweise den BubbleSort, der jedes Element mit jedem anderen Element vergleicht, was die Laufzeit erheblich in die Höhe treibt.

Wer Interesse hat, hier gibt's ein Zahlenbeispiel zum QuickSort.
 
Dass der Quicksort rekursiv arbeitet erklärt aber noch nicht, dass er so schnell ist, denn nachdem die Mitte des Feldes festgelegt ist, müssen alle Elemente des Feldes mit der Mitte verglichen werden. In einem Feld mit 1000 Elementen bedeutet das 999 Vergleiche. In der ersten Rekursionsstufe sind es 998, denn es gibt dann zwei "Mitten" in zwei Feldern. Die Anzahl der "Mitten" nimmt dann allerdings exponentiell zu, vielleicht kommt daher die hohe Geschwindigkeit.

Vielleicht kommt die hohe Geschwindigkeit auch daher, dass Elemente getauscht werden, also gleich zwei Elemente in einem Schritt in das richtige Teilfeld gebracht werden.

An der Rekursion allein liegt es jedoch meiner Meinung nach nicht, denn es gibt auch gute Beispiele für Rekursion, die keinen Vorteil bringt. Zum Beispiel lässt sich die Fakultät in einer einfachen FOR-Schleife berechnen oder so: n! = n * (n-1)! Ich wüsste nicht, dass dabei die Rekursion Vorteile hätte.

Gruß
Falk
 
Hallo,

Quicksort teil eine Liste in zwei Teillisten auf und wiederholt das rekursiv. Dadurch entsteht eine Art baum.

Die Anzahl der "Mitten" nimmt dann allerdings exponentiell zu, vielleicht kommt daher die hohe Geschwindigkeit.
Die Anzahl der Listen nimmt expotentiell zu, dadurch wächst die Anzahl der benötigten Rekursionsschritte logarithmisch(=Dauer bis die Listen die Größe 1 haben). Da eine Liste in zwei Listen aufgeteilt wird(zumindest meistens), wächst die Anzahl der Rekursionsschritte mit dem 2-er Logarithmus.

D.h. Wenn du die Listengröße von 1000 auf 2000 Elemente verdoppest, dann brauchst du nur ein rekursionsschritt mehr:
(log2 2000)-(log2 1000) = (log2 2) = 1

Ich hoffe das ist einigermaßen verständlich.

Gruß Frank
 
D.h. Wenn du die Listengröße von 1000 auf 2000 Elemente verdoppest, dann brauchst du nur ein rekursionsschritt mehr:

Stimmt leider nicht, denn wenn du 2000 Elemente hast, dann sind das quasi 2x1000, das heißt du hast die 2000 Elemente in zwei Listen zu je 1000 Elementen zerlegt. Jetzt muss du aber für beide Listen die Rekursionen durchführen, so dass bei der Erhöhung der anzahl der Elemente von 1000 auf 2000, die Anzahl n der Rekursionsschritte auf 2n+1 steigt und nicht, wie du schreibst um 1.

Gruß
Falk
 
@vogtländer: Ich meinte die Rekursionstiefe(nicht die Anzahl der Aufrufe).

Wenn man das in einem Baum aufzeichnet sieht das so aus(Ich hoffe man kann erkennen, dass das ein Baum sein soll):
Code:
             n     
          /     \
         /       \
       n/2       n/2
       /\         /\
      /  \       /  \
    n/4  n/4    n/4  n/4
Die Tiefe des oben gezeichneten Baums ist log2 n. In jeder Ebene sind n Vergleiche notwendig (z.B. n/2+n/2 oder n/4+n/4+n/4+n/4).

Verdoppelt sich nun n, dann kommt eine Ebene hinzu. Trotzdem sind in dieser neuen Ebene nur n Vergleiche notwendig. D.h. Anzahl der gesamten Vergleichsoperationen = n* (Anzahl Ebenen) = x* log2 n

Gruß Frank
 
Zurück