Rekursion?

[xXx]

Was versteht man unter Rekursion im Bezug auf Java und wie wende ich es an?

Rekursion sagt mir nur aus dem Mathe Unterricht etwas (Folgen usw...).

[zeckensack]

Rekursion hat man immer dann, wenn eine Funktion sich selbst aufruft.

Informatik-Lehrpersonal tendiert dazu, dieses Konstrukt extrem überzubewerten ;)

[Demirug]

Original geschrieben von zeckensack
Informatik-Lehrpersonal tendiert dazu, dieses Konstrukt extrem überzubewerten ;)

Und wenn man eine Rekursion für etwas verwendet was nicht in den Lehrbüchern steht es oft selbst nicht mehr zu verstehen.

[xXx]

ok eine funktion ruft sich selbst auf
und was passiert dann?

wenn ich jetzt logisch überlege ensteht entweder eine endlosschleife oder es gibt eine fehlermeldung

wie funktioniert das? und wo wird soetwas verwendet?

[EgonOlsen]

Original geschrieben von KR
wenn ich jetzt logisch überlege ensteht entweder eine endlosschleife oder es gibt eine fehlermeldung
Naja, irgendwann sollte die Rekursion schon enden :D ,d.h. irgendwann hört die Methode auf, sich selber zu rufen.
Nützlich ist das z.B. um baumartige Strukturen aufzubauen/durchzuhecheln. Ein Beispiel ist ein XML-Parser...z.B. so:

private Vector parseXML(String xml, int level) {
int pos=0;
Vector subNodes=null;
String tag=null;

do {
pos=getNextTag(pos, xml);
if (pos!=-1) {
pos++;
tag=extractTag(pos, xml);

if (tag.length()>0) {

int nodeEnd=getEndTag(pos, -1, tag, xml);

if (nodeEnd!=-1) {

XMLNode subNode=new XMLNode();

subNode.setName(tag);
subNode.setLevel(level);
subNode.setAttributes(getAttributes(pos, xml));

Vector subSubNodes=parseXML(xml.substring(pos+tag.length(), nodeEnd), level+1); // Hier ist die Rekursion
if (subSubNodes!=null) {
subNode.setSubNodes(subSubNodes);
}

if (subSubNodes==null||subSubNodes.size()==0) {
subNode.setData(grabData(pos, nodeEnd, xml));
}

if (subNodes==null) {
subNodes=new Vector(5);
}
subNodes.addElement(subNode);

}
pos=nodeEnd;
}
}
} while (pos!=-1);

return subNodes;
}

[Crushinator]

Der Stack gibt es irgendwann nicht mehr her und dann gibt es natürlich auch die entsprechende Fehlermeldung. Man kann aber rekursive Funktionen schreiben, die selbst wissen wann sie aufhören müssen, sich selbst aufzurufen. ;)

[zeckensack]

Klassisches Beispiel: die Fakultät ( n! )


unsigned int
fak(unsigned int n)
{
if (n==1) return(1);
else return(n*fak(n-1));
}
Oder so ähnlich :)

Und das läuft dann so ab:
fak(5)=5*fak(4)=5*4*fak(3)=5*4*3*fak(2)=5*4*3*2*fak(1)=5*4*3*2*1

[Gast]

Original geschrieben von KR
wie funktioniert das? und wo wird soetwas verwendet?

Man setzt sich bei der Rekursion irgendeine Bedingung, bei der das ganze abbricht.
Als klassische Beispiele fallen mir alle mögliche Such- und Sortieralgorithmen ein.

Man teilt sich halt oft ein grosses Problem in Teilprobleme auf und versucht die unabhängig voneinander zu lösen. Nennt sich auch "Divide and Conquer".

[thop]

rekursion - die, siehe rekursion

[xXx]

Original geschrieben von thop
rekursion - die, siehe rekursion

aha, und...?

für alle anderen beiträge: danke!

[KiBa]

Original geschrieben von KR
aha, und...?

für alle anderen beiträge: danke!
er meinte damit sicherlich: um die rekursion zu verstehen, muss man zuerst die rekursion verstehen.
scnr

[huha]

Rekursionen sind, öhem, cool.
Mit der winzigen Ausnahme, daß mir bis heute kein sinnvolles Anwendungsgebiet außerhalb der Mathematik oder Verzeichnisdruchsuchung einfällt, bei dem man Rekursionen benutzen kann.

-huha

[thop]

nein, sieh das als DUDEN eintrag. unter rekursion steht dann: siehe rekursion. so dreht sich das dann immer weiter. das ist rekursion.

[xXx]

Original geschrieben von thop
nein, sieh das als DUDEN eintrag. unter rekursion steht dann: siehe rekursion. so dreht sich das dann immer weiter. das ist rekursion.

ahhh, jetzt leuchtet es mir ein

;)

[GloomY]

Original geschrieben von huha
Rekursionen sind, öhem, cool.
Mit der winzigen Ausnahme, daß mir bis heute kein sinnvolles Anwendungsgebiet außerhalb der Mathematik oder Verzeichnisdruchsuchung einfällt, bei dem man Rekursionen benutzen kann.

-huha Das muss ja nicht umbedingt auf Verzeichnisse beschränkt sein. Bei jeder baumartigen Datenstruktur muss man rekursiv von der Wurzel ausgehend nach Elementen suchen (gerade beim Suchen liegt ja der Vorteil von Bäumen gegenüber linearen Listen).

Und von Bäumen gibt's wirklich jede Menge (AVL-, B-, Rot-Schwarz- usw.). Man kann auch innerhalb von Programmen baumartige Datenstrukturen verwenden und kommt somit zwangsläufig mit Rekursion in Berührung.

[Crushinator]

Original geschrieben von huha
Rekursionen sind, öhem, cool.
Mit der winzigen Ausnahme, daß mir bis heute kein sinnvolles Anwendungsgebiet außerhalb der Mathematik oder Verzeichnisdruchsuchung einfällt, bei dem man Rekursionen benutzen kann. Ein Beispiel aus der Wirtschaftsinformatik: Wenn Du den Bestand eines logischen Materials buchen möchtest, welches aus mehreren Physischen (Materialien) besteht - deren Bestände auch korrekt gebucht werden müssen - erzeugst Du automatisch eine Rekursion. Alles halb so schlimm wenn man eine Grenze deffiniert, wie klein die zu buchende Mindestmenge sein darf. =)

[ethrandil]

Okay, hier ein Anwendugnsgebiet außerhalb von Mathe und Verzeichnissen:

Firmenstrukturen, oder Baumstrukturen überhaupt.
Auch Verzeichnisse.

Und das ist doch unbestritten kein 'kleines' gebiet, oder?

[Stone2001]

Original geschrieben von zeckensack
Rekursion hat man immer dann, wenn eine Funktion sich selbst aufruft.

Informatik-Lehrpersonal tendiert dazu, dieses Konstrukt extrem überzubewerten ;)
Tja, die Studenten werden am Anfang recht oft mit Rekursivität 'belästigt', nur um dann in der Theoretischen Informatik zu erfahren, das man gleich alles mit einer 'While'-Schleife berechnen kann! ;)

[Xmas]

Original geschrieben von Stone2001
Tja, die Studenten werden am Anfang recht oft mit Rekursivität 'belästigt', nur um dann in der Theoretischen Informatik zu erfahren, das man gleich alles mit einer 'While'-Schleife berechnen kann! ;)
Wobei Rekursion bei Bäumen fast immer deutlich einfacher ist.

[Stone2001]

Original geschrieben von Xmas
Wobei Rekursion bei Bäumen fast immer deutlich einfacher ist.
Sicher hat die Rekursion in diesem Bereich Vorteile, die Fakultät (z.B.) würde aber nicht rekursiv berechnen. ;)

[ethrandil]

ja, klar ;)
Um alle zahlen von 1 bin n herauszufinden macht man ja auch nicht:

from1ton(int n, int act=1){
if(act == n)
return act;
else
return n + from1ton(act+1);
}

und auch nicht:

int result = 0;
for(int i=1; i <= n; ++i)
result += i;
return result;

sondern

return (n*(n+1))/2;


Das sollte die effizienz deutlich genug darstellen ;)

Wenn eine Möglichkeit mit while-schleife vorhanden ist, dann ist sie meistens von der Ausführungszeit effizienter, aber der Aufwand evtl. höher.

btw: Wie benutzt man bei baumstrukturen ein schleife??
EDIT: Ich hab mal nen Test gemacht :)
Der komplette Code ist:
import java.util.Date;

class Test{
public static void main(String[] args){
long n = Integer.parseInt(args[0]);
long date = 0;

date = new Date().getTime();
try{
System.out.println("Rekursion: "+gaussRec(n, 1));
System.out.println("took: "+(new Date().getTime()-date));
}catch(Throwable t){
System.out.println("Rekursion ist nach "+(new Date().getTime()-date)+" milisekungen gecrasht");
}

date = new Date().getTime();
System.out.println("While: "+gaussWhile(n));
System.out.println("took: "+(new Date().getTime()-date));

date = new Date().getTime();
System.out.println("Gauss: "+gaussGauss(n));
System.out.println("took: "+(new Date().getTime()-date));
}

public static long gaussRec(long n, long act){
if(n <= act)
return act;
else
return act+gaussRec(n, act+1);
}

public static long gaussWhile(long n){
long result = 0;
for(long c = 1; c <= n; ++c)
result += c;
return result;
}

public static long gaussGauss(long n){
return (n*(n+1))/2;
}
}

Die Ausgabe:
java Test 100000000
Rekursion ist nach 10 milisekungen gecrasht
While: 5000000050000000
took: 4206
Gauss: 5000000050000000
took: 0

:)

[Stone2001]

hmm, sehr schön! =) Klar ist ein Algorithmus mit O(1) einem Algorithmus mit O(n) vorzuziehen, aber kannst du das auch mit weniger trivialen Fällen? Z.B. mit der Fakultät? ;)
Das eine While-Schleife bei normalen Berechnungen schneller als Rekursion ist, dürfte wohl klar sein, oder?

P.S.: Wie man eine While-Schleife in einer Baumstruktur benutzt. K.A. Ich kann dir nur sagen, das es geht. ;)

[ethrandil]

Original geschrieben von Stone2001
kannst du das auch mit weniger trivialen Fällen? Z.B. mit der Fakultät?
Nur näherungsweise ;)

Math.sqrt(2*Math.PI*n)*Math.pow(n, n)*Math.pow(Math.E, -n)

bzw

Math.pow((n/Math.E), n)*Math.sqrt((Math.pow(Math.E, 4)/8)*n)


;);)

[Stone2001]

Original geschrieben von ethrandil
Nur näherungsweise ;)
;);)
Tja, näherungsweise reicht aber nicht immer! ;)

[Xmas]

Original geschrieben von Stone2001
Tja, näherungsweise reicht aber nicht immer! ;)
Joa, aber bei den "üblichen" Datentypen schon. Int32 geht eh nur bis 12!, Int64 bis 20!, Und bei double reicht die Stirlingformel auch aus.

Original geschrieben von ethrandil
btw: Wie benutzt man bei baumstrukturen ein schleife??
Eventuell braucht man mehrere Schleifen (und einen Stack o.ä.) , je nachdem ob man top-down oder bottom-up durchlaufen will.


node = top
while node != None:
print node.text # einfaches Beispiel
if node.hasChildren:
node = node.child[0]
else:
while node.nextSibling == None and node.parent != None:
node = node.parent
node = node.nextSibling


Zum Vergleich:

def printNode_rec(node):
print node.text
for c in node.child:
printNode_rec(c)

printNode_rec(top)