Rekusiv und iterativ bezüglich Sortieralgorithmen..

[fizzle]

Hallo,

in meiner bald anstehenden Abiturpräsentation werde ich den Quicksort und im Kontrast dazu den Bubblesort vorstellen.

Der Quicksort arbeitet rekusiv, der Bubblesort iterativ.

Trotz einiger Recherche ist mir der Unterschied immer nocht nicht einleuchtend. Bisher bin ich auf diesem Stand :

Rekusiv : eine Funktion definiert sich durch sich selbst ?!
Iterativ : schrittweise Wiederholung eines bestimmten Schrittes zur Lösung des Problems

Kann jemand die Begriffe etwas weiter ausführen? Wie kann man die Begriffe auf die Funktionsweise der aufgeführten Sortieralgorithmen beziehen ?

 

[asdfman]

Rekursiv und Iterativ sind Bezeichnungen für die Funktionsweise eines Prozesses. Eine rekursive Funktion
kann einen iterativen Prozess implementieren. Ich empfehle, dazu ein Buch zu lesen. Am Anfang von SICP
gibt es eine gute Erklärung dazu.

http://mitpress.mit.edu/sicp/full-text/book/book.html

€: Der spezielle Abschnitt, um den es geht ist hier:
http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2
Aber es lohnt sich, den kurzen Teil vorher zu lesen, um ein Verständnis von der Sache zu haben. Der Link
zeigt auf Abschnitt 1.2, also kommt vorher nur 1.1; das ist nicht viel.

Wenn du den Abschnitt einmal kurz überfliegst, solltest du merken, dass das kein Thema ist, das man mal
eben in einem Forenpost abhandeln kann. Also lies ein Buch dazu (beispielsweise SICP).

€2: Das Buch gibts auch als Videovorlesung:
http://groups.csail.mit.edu/mac/classes/6.001/abelson-sussman-lectures/
Die entsprenden Vorlesungen sind 1a und 1b. Zusammen etwa 2 Stunden Videomaterial. Das wird man sich
doch mal an einem Nachmittag angucken können und dann hat man einen ordentlichen Haufen Wissen dazu.

Bei Detailfragen kannst du dich dann ja nochmal melden.

 

[fizzle]

Danke dir für deine Bemühungen, aber ich bräuchte eine kurze, knackige Definition. Vielleicht eine einfache Erklärung mit einem allgemeinen Beispiel oder so, wäre euch sehr dankbar.


Edit : Konkretere Frage: Wieso ist der Quicksort rekusiv ? Wo ist die, durch sich selbst Definierte, rücklaufende Rekusion ?

 

[refri89]

Sieh dir mal die Ausgabe dieses Beispiels an:

#include <stdio.h>

void function_recursiv(int zahl)
{
if(zahl > 0)function_recursiv(zahl-1);
fprintf(stderr,"\nZahl ist: %i",zahl);
}


int main(int argc, char *argv[])
{
function_recursiv(7);
}


Zahl ist: 0
Zahl ist: 1
Zahl ist: 2
Zahl ist: 3
Zahl ist: 4
Zahl ist: 5
Zahl ist: 6
Zahl ist: 7

Rekursiv heißt: "eine funktion ruft sich selbst auf"
Man übergibt als Anfangsargument die Zahl 7 und erwartet ein Herunterzählen der Zahl bis auf 0 aber es passiert genau das Gegenteil, warum ?
Die rekursiven Funtionsaufrufe "speichern sich" auf dem Stack und erst bei erreichen des Abbruchkriteriums wird der Stack wieder rückwärts abgearbeitet:

Es gibt in der Computerlehre den abstrakten Datentyp Stapel (=Stack), der funktioniert wie ein Stapel von Notizblättern, die du in einer bestimmten Reihenfolge aufeinander legst und in der geanu umgekehrten Reihenfolge wieder abhebst, die zwei Grundoberation sind also put() und get():

Zahl am Anfang ist 7:
put(7)
put(6)
put(5)
put(4)
put(3)
put(2)
put(1)
put(0)

unterstes Blatt steht jetzt sieben drauf, oberstes Blatt steht 0 drauf...


bis hierher hat sich die rekursive Funktion immer nur selbst aufgerufen, der fprintf-code wurde nie erreicht. Jetzt ist die Abbruchbedingung erfüllt (ABBRUCHBEDINGUNG EIN MUSSSS bei rekursiven Funktionen)

print(get(last)) druckt 0
(das oberste Blatt hat eine 0 draufgeschrieben, weil das der letzte Wert war, der auf den Stack gelegt wurde, zuunterst wurde ein Blatt gelegt wo 7 draufsteht)
print(get()) druckt 1
print(get()) druckt 2
print(get()) druckt 3
print(get()) druckt 4
print(get()) druckt 5
print(get()) druckt 6
print(get()) druckt 7 (ist das unterste Blatt)

Funktionenstack ist abgebaut und erst jetzt kehrt die Funktion zurück.
So schön rekursive Funktionen auch sind, wenns um die Laufzeiteigenschaften geht sind sie nicht so toll (Funktionsstackverwaltung) kann auch mal den Speicher sprengen bei vielen lokalen Variablen, da die ja bei jedem Funktionsaufruf auf den Stack gelegt werden müssen.

Vermeindung von rekursiven Funktionen mithilfe einer Stack Implementierung.

 

[fizzle]

Dir auch danke aber leider muss ich passen. Soweit bin ich ned in der Materie drin und habe eher auf die Beantwortung meiner konkreten Frage gehofft

 

[refri89]

is nich einfach, hier hätt ich ein paar schöne Demos (falls nicht selbst schon vorhanden)
http://java.sun.com/applets/jdk/1.4/demo/applets/SortDemo/example1.html

auf die Grafikdarstellung klicken, dan läuft der jeweilige Algo los.
Seite neu laden im Browser wenn man nochmal durchlaufen will

 

[fizzle]

Jo, bleibt die Frage was am Quicksort so selbstaufrufend ist

 

[cx01]

Quicksort ist ja in etwa so definiert: Man teilt eine Liste in 2 Teilleisten anhand des Pivot-Elements und wendet dann auf beide Listen wieder den Algorithmus an, der diese dann wiederum in 2 Teillisten zerteilt usw.
Deine Definition vom Anfang kommt also ungefähr hin. Ein Algorithmus ist rekursiv, wenn er in seiner Definition auf sich selbst verweist.
Es ist jedoch möglich, den Quicksort auch iterativ zu implementieren, also mit Hilfe einer Schleife.
Die ganze Sache ist also nicht ganz so simpel. Es gibt auch einige Compiler, die in der Lage sind, manch rekursive Funktion in eine iterative zu konvertieren.

Aber ich glaube, das ist für dich alles nicht so relevant. In einer Abiprüfung wird es keinen interessieren, ob das jetzt 100% mathematisch korrekt ist. Sag denen einfach, Quicksort ist rekursiv, weil es sich zum Sortieren einer Liste selbst aufruft. Und Bubblesort ist iterativ, weil es einfach nur mit Schleifen arbeitet.

 

[fizzle]

Denkst du das reicht ?

 

[kuddlmuddl]

Das einfache Standardbeispiel zur Rekursion ist die Berechnung der Fakultät.
Kennst du?
faku(5) = 5*4*3*2*1 = 120

Versuch mal selbst auf beide weisen zu implementieren - oder google dir was zusammen

Die Funktion kann man sehr schön rekursiv implementieren aber eben auch iterativ!
Ich würde sagen, dass man das auf jeden Fall einmal erwählen sollte - wie mans implementiert ist nicht zwangsläufig vorgegeben.

Rekursive Algorithmen rufen sich selbst auf - das wurde ja schon oft genug gesagt.

Die "Form" ist meist die gleiche. Es werden nur 2 Fälle unterschieden: Das Ende und die rekursion. Das Ende wird meist auch "Abbruchbedingung" gekannt. Dh:

Man kann eben zwei Anweisung formulieren:

meine_fakultaet(int n)
if (Problem ist so klein, dass es direkt gelöst werden kann) // Dies ist die Abbruchbedingung
{
    Löse es direkt
    // (In meinem Beispiel der Fakultät wäre das der Fall: "if (n == 1) return 1;"
}

else // Da das Problem nicht direkt gelöst werden kann, wird rekursiv die Funktion für kleinere Probleme gelöst
{
    // Zerteile das Problem in einen winzigen, lösbaren Teil und einen Rest R
    return meine_fakultaet(n-1) * n;
}

Ich würd sagen, so sehen rekursive Problemlösungen meistens aus. Man prüft, ob ein einfacher / elementarer Fall vorliegt der direkt gelöst werden kann und ansonsten wird das Problem verkleinert erneut an die Funktion gegeben.
Wenn man das Problem in 2 halbwegs gleich große Hälften teilt nennt man das http://de.wikipedia.org/wiki/Teile_und_herrsche_%28Informatik%29

(Sorry falls es Fehler gibt - is noch früh :X)

 

[NullPointer]

Hier ist das Quicksort-Beispiel aus Wikipedia in Pseudocode, da sollte klar werden, warum er rekursiv ist:

 funktion quicksort(links, rechts)
     falls links < rechts dann
         teiler := teile(links, rechts)
         quicksort(links, teiler-1)
         quicksort(teiler+1, rechts)
     ende
 ende

 

[kuddlmuddl]

Ja das is doch wunderbar ums vorzuführen
Am besten machst du ein Beispiel mit einer 8 elementigen Liste und malst dazu einen Baum (!)
(Oben gehts los mit dem Aufruf der Funktion mit den 8 Elementen - darunter dann 2 Aufrufe mit je 4 Elementen - darunter dann 4 Aufrufe mit je 2 Elementen)

Dann sieht man auch, wie oft (7 mal! hättest du das vorher gewusst?) und von wo aus die Funktion aufgerufen wird

Das "elegante" an so einer rekursiven Lösung ist halt, dass man nicht vorher überlegen muss, wie oft die Funkion eigentlich aufgerufen wird.

Die Gefahr bei Rekursion sind Endlosschleifen. Macht man einen Fehler, oder erfasst bei seiner Abbruchbedingung nicht alle Fälle, die tatächlich das Ende bedeuten, kann es sein, das Programm "hängt" (= die Funktion ruft sich ohne Ende immer wieder und wieder auf)
Bei einer iterativen Lösung ist sowas unwahrscheinlicher, durch die Schleife fest vorgegeben sein sollte, wie oft die Funktion aufgerufen wird. Dort würde dann am Ende eher das Ergebnis falsch sein bei einem Fehler.
Was man nun besser findet kommt halt drauf an...

 

[fizzle]

Danke euch, nehme gleich meine Prüfung in Anspruch, werde euch dann berichten wie es war !

Ergänzung (19. Mai 2010)

Edit: Auch wenns keinen interessiert, hab heute eine gute Präsi hingelegt, müsste im 1er Bereich sein. Danke an Alle

 

[refri89]

Mir hauts hier eh die Formatierungen raus, habs wieder gelöscht.
Fileicht nicht erst am vorletzten Tag...?

 

[fizzle]

Danke dir aber die Prüfung habe ich hinter mir

 

[asdfman]

Eine Funktion die durch sich selbst definiert ist, ist nicht zwangsläufig rekursiv. Beispiel:

(define (factorial n)
  (fact-iter 1 1 n))

(define (fact-iter product counter max-count)
  (if (> counter max-count)
      product
      (fact-iter (* counter product)
                 (+ counter 1)
                 max-count)))

Die Funktion fact-iter ist hier über sich selbst definiert. Trotzdem ist der Prozess, der durch diese Funktion
generiert wird, iterativ. Ruft man beispielsweise (factorial 6) auf, läuft folgender Prozess ab:

(factorial 6)
(fact-iter 1 1 6)
(fact-iter 1 2 6)
(fact-iter 2 3 6)
(fact-iter 6 4 6)
(fact-iter 24 5 6)
(fact-iter 120 6 6)
(fact-iter 720 7 6)
720

Die Funktion ruft sich zwar selbst auf, nachdem die nächste Funktion in der Reihe abgelaufen ist, kehrt der
Prozess aber nicht wieder zur Alten zurück. Man vergleiche im Gegensatz dazu die rekursive Variante:

(define (factorial n)
  (if (= n 1)
      1
      (* n (factorial (- n 1)))))

Ruft man jetzt (factorial 6) auf, läuft folgender Prozess ab:

(factorial 6)
(* 6 (factorial 5))
(* 6 (* 5 (factorial 4)))
(* 6 (* 5 (* 4 (factorial 3))))
(* 6 (* 5 (* 4 (* 3 (factorial 2)))))
(* 6 (* 5 (* 4 (* 3 (* 2 (factorial 1))))))
(* 6 (* 5 (* 4 (* 3 (* 2 1)))))
(* 6 (* 5 (* 4 (* 3 2))))
(* 6 (* 5 (* 4 6)))
(* 6 (* 5 24))
(* 6 120)
720

Dieser Prozess ist rekursiv, weil immer von der aufrufenden Funktion "etwas übrig bleibt", das später ab-
gearbeitet werden muss (erst die Multiplikation mit 6, dann mit 5 undsoweiter).

Zu sagen, eine Funktion ist rekursiv, wenn sie sich selbst aufruft ist also falsch.

 

[refri89]

Eine Funktion die sich NICHT selbst aufruft, kann aber niemals rekursiv sein, also ist der Aufruf einer Funktion durch sich selbst eine zwingende Anforderung an eine Funktion, will sie rekursiv sein. Allerdings ist eine sich selbst aufrufende Funktion nicht zwingenderweise auch rekursiv:

#include <stdio.h>

int zahl = 7;

void dummrekursiv()
{
fprintf(stdout,"Zahl: %i\n",zahl--);
if( !(zahl < 0) )dummrekursiv();
}

int main()
{
dummrekursiv();
return 1234;
}

 

[NullPointer]

asdfman: Der Prozeß mag iterativ sein, die Funktion ist aber dennoch rekursiv - dieser Spezialfall nennt sich "Tail-Rekursion" (der rekursive Aufruf findet ganz am Ende der Funktion statt) und wird in diesem Fall vom Compiler optimiert.

 

[asdfman]

Ja, das ist Wahr. Habe mich da mit den Begriffen etwas verheddert. Bin ja auch kein Informatiker, also da
nicht so geübt, was die strenge Anwendung solcher Bezeichnungen angeht.

Würde vielleicht noch hinzufügen, dass Quicksort einen rekursiven Prozess erzeugt, weil jeweils, wenn ein
Sortierproblem in zwei Unterprobleme geteilt wird, für beide Unterprobleme ein neuer Aufruf von Quicksort
selbst stattfindet, und der Prozess so eine Baumstruktur bekommt.

Bei Bubblesort wird das zu sortierende Array dagegen immer der Reihe nach durchgegangen, ohne dass
eine Aufspaltung des Prozesses stattfindet. Er ist also linear und damit iterativ (Selbst, wenn für ein
weiterer Durchgang durch das Array die Bubblesortfunktion erneut aufgerufen wird, was man ja völlig
legitimerweise tun kann).

 

[kuddlmuddl]

Ich hätte jetzt gedacht man kann Algorithmen wie zB Bubble- oder Quicksort nicht pauschal in rekursiv oder iterativ unterteilen sondern es kommt immer auf die Implementation an - oder nicht?

Selbst eine Schleife kann ich rekursiv hinschreiben:

Iterativ:

void counter(int max)
{
  for (int i = 1; i <= max; ++i)
  {
    cout << i << "\n";
  }
}

Rekursiv:

void counter(int max)
{
  counter_rek(max, 1);
}

void counter_rek(int max, int aktuell)
{
  if (aktuell == max) // Abbruchbedingung
    cout << aktuell << "\n";
  else
  {
    cout << aktuell << "\n";
    counter_rek(max, aktuell + 1); // Rekursiver Aufruf
  }
}

N Bubblesort müsste doch auch rekursiv gehen?
so vonwegen:

vector<int> bubblesort(vector<int>& v)
{
  if ( isSorted(v) ) // Die Implementation von isSorted (=Abbruchbedingung) spar ich mir mal
    return v;
  else
  {
    // Durchlaufe einmal von vorn bis hinten und tausche alle Paare wenn nötig
    for(int i = 0; i+1 < v.size(); ++i)
    {
      if (v[i] > v[i+1])
        swap(v[i], v[i+1]);
    }
    return bubblesort(v); // Rekursiver Aufruf
  }
}