Frage von Pokecrafter567, 99

Rekursion in Java wofür und wer kann es mir erklären?

Wer kann mir das erklären und überhaupt mal sagen, was das bringt, weil wenn es nichts bringt, muss ich den Stuff ja nicht lernen...

https://www.youtube.com/watch?v=9SC2hOSTkhA&list=PL71C6DFDDF73835C2&inde...

kann mir vllt jemand dieses Tuto erklären??? evntl auch skype :c

Antwort
von PWolff, 38

Rekursion bedeutet in der Programmierung, dass eine Prozedur sich selbst aufruft.

Ein Beispiel, wo man Rekursion verwendet:

Schau dir mal den Quelltext einer beliebigen Internet-Seite an.

Da wirst du viele "ineinander geschachtelte" "Tags" finden, also die Dinger, die mit so was wie <tagname attribut1="wert1" attribut2="Wert2"...> eingeleitet und (meistens) mit </tagname> beendet werden.

Dabei werden Dutzende von Tags geöffnet, bevor einer wieder geschlossen wird.

Da der Quelltext für uns Menschen aber schwer lesbar ist und natürlich auch nicht so schön aussieht, hätten wir ihn gern anders dargestellt. Dafür hat so ein Webbrowser einen "HTML-Renderer".

So ein HTML-Renderer geht typischerweise so vor:

Er bekommt vom Webbrowser gesagt: "Stelle die und die Webseite in dem und dem Fenster dar!"

Daraufhin nimmt der Renderer sich das äußerste Tag der Webseite (normalerweise <html> ... </html>) vor und schaut sich die Tags darin an.

Für jedes Tag innerhalb des äußersten ruft er seinerseits einen Renderer (praktisch immer eine Kopie von sich selbst) auf und sagt dem z. B.: "Stell dieses Tag dar und sag mir, wie viel Platz du dafür in der Höhe brauchst - in der Breite stehen dir 483 Pixel zur Verfügung!"

Was diese Kopie des Renderers tut, ist dem Renderer auf der oberen Ebene ziemlich egal. Alles, was er wissen will, ist, wie viel Platz er zur Verfügung stellen sollte, um das Element darzustellen. Wenn es möglich ist, markiert er ein Rechteck aus seinem eigenen Darstellungsbereich mit den nötigen Dimensionen, worin der untergeordnete Renderer tun und lassen kann, was er will.

Dieser untergeordnete Renderer findet in seinem Bereich seinerseits jede Menge Untertags, für die er unter-untergeordnete Renderer aufruft.

Und so weiter.

Bis irgendwann ein Renderer auf ein Bild oder ein Stück Text trifft, das er unmittelbar auf den Bildschirm malen kann.

Das ist mit Rekursion vergleichsweise einfach zu realisieren - die Theorie sagt, dass es immer auch ohne Rekursion geht, aber das ist sehr, sehr viel aufwendiger und damit fehleranfälliger als die Lösung mit Rekursion.

Antwort
von triopasi, 36

Viele Formeln lassen sich rekursiv sehr einfach darstellen, explizit hingegen nur sehr schwer. Daher ist rekursion manchmal einfach leichter. Bin selbst eher n Fan von der expliziten Darstellung, aber zB der ggT ist rekursiv einfach extrem einfach berechenbar, dann nimmt man halt das.

Expertenantwort
von Marbuel, Community-Experte für Computer & PC, 32

Ein schönes Beispiel wäre, wenn du ein File-System auslesen möchtest. Du rufst beispielsweise auf Platte C eine angenommene GetSubFolders auf und diese ruft sich dann für alle Subfolders, die wiederum Subfolders haben, selbst auf.

Versuch doch mal dieses Problem mit Rekursion zu lösen. Mach eine kleine GUI in der dir 1:1 deine Verzeichnisse und Files angezeigt werden. Wie wäre das? Du könntest einen Treeview verwenden.

Antwort
von MrNorux, 58

Durch eine Rekursion wird eine Methode durch sich selbst aufgerufen. Nimm mal als Beispiel die Fibonacci-Zahlen: 0, 1, 1, 2, 3, 5, 8, ...

Alle davon zu speichern ist unmöglich, weil es unendlich viele gibt. Also definierst du eine Methode, die folgendermaßen aussieht:

public int fibonacci(int stelle){
    if(stelle == 0) return 0;
    else if(stelle == 1) return 1;
    else return fibonacci(stelle - 1) + fibonacci(stelle - 2);
}
Kommentar von MrNorux ,

Schick mir deine Skypeadresse, dann kann ichs dir erklären

Kommentar von Mikkey ,

Damit hast Du gleich DAS Beispiel gegeben, wann man rekursive Programmierung vermeiden sollte.

Kommentar von MrNorux ,

Ich weiß. Es geht aber um das Prinzip der Rekursion, nicht die Effizienz. Und mit diesem Beispiel lässt sich Rekursion gut nachvollziehen.

Antwort
von Willibergi, 12

Es gibt in der Programmierung zwei Arten von Methoden: Die iterativen und die rekursiven.

Iterative (lat. iteratio = Wiederholung) Methoden laufen einmal von oben nach unten durch und enden entweder beim Return-Befehl oder bei der schließenden, geschweiften Klammer.

Rekursive (lat. recurrere = Zurücklaufen) Methoden rufen sich in sich selbst immer wieder auf, bis eine Abbruchbedingung erfüllt wurde.

Das ganze werde ich dir nun - wie in deinem Video - an der Fakultät einer Zahl verdeutlichen:

Iterative Methode:

static int fac(int x){
    if(x < 0) return null;
    if(x == 0 || x == 1) return 1;
    int res = 1;
    for(int i=2; i<=x; i++){
        res *= i;
    }
    return res;
}

In dieser Methode wird ausgehend von der Zahl zwei jede Zahl bis zur übergebenen Zahl miteinander multipliziert.
(mit 1 zu multiplizieren ist unnütz - es verändert das Ergebnis nicht)

Würdest du also folgenden Funktionsaufruf tätigen:

fac(8);

würde die Funktion folgendes berechnen:

2*3*4*5*6*7*8

Die Fakultät einer negativen Zahl ist nicht definiert, daher wird null zurückgegeben. (theoretisch müsste man hier eine Exception werfen, das würde aber hier zur Verwirrung führen)

Nun die rekursive Methode:

static int fac(int x){
    if(x < 0) return null;
    if(x == 1 || x == 0) return 1;
    return fac(x - 1)*x;
}

Diese Methode ruft sich im return-Befehl selbst wieder auf, da man für die Fakultät einer Zahl auch die Fakultät des Vorgängers mit der Zahl multiplizieren kann.
(8! = 7! * 8)

Diese Methode ruft sich also immer wieder auf, bis sie mit dem Wert 1 aufgerufen wird, denn dabei wird ein konkreter Wert zurückgegeben.

Dann werden noch alle nicht abgeschlossenen Methoden abgeschlossen, die durch den Funktionsaufruf "pausiert" wurden.

Damit wird folgendes gerechnet:

8! = (8-1)! * 8
7! = (7-1)! * 7
6! = (6-1)! * 6
5! = (5-1)! * 5
4! = (4-1)! * 4
3! = (3-1)! * 3
2! = (2-1)! * 2
    = 1! * 2
1! = 1 (Abbruchbedingung)
2! = 1 * 2
3! = 1 * 2 * 3
4! = 1 * 2 * 3 * 4
5! = 1 * 2 * 3 * 4 * 5
6! = 1 * 2 * 3 * 4 * 5 * 6
7! = 1 * 2 * 3 * 4 * 5 * 6 * 7
8! = 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8
    = 40.320

40.320 wird zurückgegeben.

Rekursive Methoden haben Vorteile aber eben auch Nachteile:

Ein Vorteil ist, dass sie kurz und knapp sind.
Ein Nachteil ist allerdings, dass sie sehr rechen- und somit zeitintensiv sein können (rekursiv: O(n), iterativ: O(n) - probiere doch einfach mal fac(50) aus).
Ein weiterer Nachteil ist, dass sie speicherplatzintensiv sind (rekursiv: O(n), iterativ: O(1)).

Die Laufzeit O(1) ist immer da, was erreicht werden will - die optimale, konstante Laufzeit.

Rekursive Methoden sind somit selten sinnvoll, aber manchmal geht es eben nicht anders.

Ich hoffe, ich konnte dir helfen; wenn du noch Fragen hast, kommentiere einfach.

LG Willibergi

Expertenantwort
von TeeTier, Community-Experte für programmieren, 26

Diese Frage wird dir hier beantwortet:

https://www.gutefrage.net/frage/rekursion-in-java-wofuer-und-wer-kann-es-mir-erk...

Genau DAS ist hier ist eine rekursive Antwort. Die Abbruchbedingung bist du selbst, und das Ergebnis ist "false". :)

Kommentar von MrNorux ,

:D google mal rekursion 

Kommentar von TeeTier ,

Na toll ... da hab ich mir mal einen ganz tollen Witz ausgedacht, und plötzlich zeigen mir alle, dass das Netz bereits voll davon ist. ><

Keine passende Antwort gefunden?

Fragen Sie die Community