Rekursion

[pe81]

Halloan alle,

ich habe mal hier eine Frage zur Rekursion........

private int methode(int i, int j, char newC, char oldC) {

// hier wird dieMethode durchgearbeitet
		
return methode(i+1,j,newC,oldC)+ methode(i,j+1,newC,oldC)+ methode(i-1,j,newC,oldC)+ methode(i,j-1,newC,oldC)+ 1;
}

wie kann ich diese schreibweise interpretieren.....mit + bei den methoden....
wie wirkt sich das bei der ausführung.....habe das zum ersten mal gesehen..
kann mir da jemand erklären wie das zu verstehen ist oder kennt gute seiten zum thema
rekursion

vielen dank

lg
pe

 

[Gast2]

da steht

return methode(...)+methode(...)+methode(...)+methode(...)+1;

methode gibt dir einen int zurück, d.h. du rechnest hier einfach die 4 rückgabewerte der methoden zusammen und addierst eins drauf. die methoden werden von links nach rechs abgearbeitet.

 

[pe81]

danke eikeB für die antwort,

so ungefähr habe ich mir das vorgestellt.....nur meine frage ist es
in der methode eine abbruch bediengung habe zb i<5.....
wird dann die erste methode rekursiv aufgerufen bis die abbruch bediengung erfüllt ist oder werden die anderen methoden durch dieses + auch gleich zur geltung kommen......
danke
lg
pe

 

[Gast2]

alles wird nacheinander abgearbeitet.
du hast 4 Methdodenaufrufe im return statement. zuerst wird die erste Methode aufgerufen bis die rekursion abbricht und das ergebnis kommt, dann kommt der zweite methodenaufruf, usw. bis alle 4 durch sind.

 

[Landei]

Das Beispiel ist viel zu kompliziert. Das "klassische" Beispiel, das du am besten mit Bleistift und Papier nachvollziehen solltest, ist die naive Implementierung der Fibonacci-Folge (0,1,1,2,3,5,8,13...):

public int fibo(int n) {
   if (n == 0 || n == 1) {
      return n;
   } else {
      return fibo(n-1) + fibo(n-2);
   }
}

Bei fibo(0) und fibo(1) wird direkt 0 oder 1 zurückgeliefert (das sind die sogenannten "Basisfälle", in denen keine Rekursion stattfindet).

Was passiert beim Aufruf von fibo(2)? Nun, fibo(2-1) ist fibo(1) und liefert 1 zurück. fibo(2-2) ist fibo(0) und liefert 0 zurück. Beides wird zusammenaddiert, was 1 ergibt, und das wird als Ergebnis von fibo(2) zurückgeliefert.

Was passiert beim Aufruf von fibo(3)? fibo(3-1) ist fibo(2) - was wir gerade besprochen haben, und das 1 zurückliefert. fibo(3-2) ist fibo(1) und liefert 1 zurück. Beides wird zusammenaddiert, was 2 ergibt, und das wird als Ergebnis von fibo(3) zurückgeliefert.

Was passiert beim Aufruf von fibo(4)? Das kannst du jetzt sicher selbst herausfinden...

Genauso funktioniert deine Methode, nur mit mehr Parametern und Unteraufrufen.

An Rekursion ist nichts magisches, eine Methode ruft andere Methoden auf, die "zufällig" den gleichen Namen haben. Aber die Argumente unterscheiden sich, und an dieser Stelle muss man sorgfältig schauen, womit denn n oder i oder sonstwas bei einem Unteraufruf belegt ist. Natürlich muss die Aufrufkette irgendwann einmal stoppen und ein Ergebnis "nach oben" zurückliefern, und das geschieht in den Basisfällen.

 

[hoangvm]

Halloan alle,

ich habe mal hier eine Frage zur Rekursion........

private int methode(int i, int j, char newC, char oldC) {

// hier wird dieMethode durchgearbeitet
		
return methode(i+1,j,newC,oldC)+ methode(i,j+1,newC,oldC)+ methode(i-1,j,newC,oldC)+ methode(i,j-1,newC,oldC)+ 1;
}

wie kann ich diese schreibweise interpretieren.....mit + bei den methoden....
wie wirkt sich das bei der ausführung.....habe das zum ersten mal gesehen..
kann mir da jemand erklären wie das zu verstehen ist oder kennt gute seiten zum thema
rekursion

vielen dank

lg
pe

deiner fehlt noch das Abbruchkriterium

z.b was ist der ruckgabewert wenn i = 0 , j = 0 ..

 

[pe81]

z.b was ist der ruckgabewert wenn i = 0 , j = 0

@hoangvm das habe ich mit hier wird die methode durchgearbeitet

aber der landei hat es mit der fibo super erklärt......nun ist es verständlicher

lg
pe

 

[netzBone]

Hallo,

wenn du das Thema Rekursion einfach nur verstehen möchtest ist die Fib Methode ein
gutes Beispiel.
Bist du aber an einem Projekt, würde ich dir empfehlen Rekursion nur bei komplexeren
Anwendungen einzusetzen. Eine iterative Methode ist viel schneller, denn
bei der Rekursion landen die Zwischenergebnisse auf dem Stack. Setzt man ein paar
Methoden mit Rekursion ein, wird die Ausführung bedeuten langsamer sein !

 

[Dekker]

Hallo,

wenn du das Thema Rekursion einfach nur verstehen möchtest ist die Fib Methode ein
gutes Beispiel.
Bist du aber an einem Projekt, würde ich dir empfehlen Rekursion nur bei komplexeren
Anwendungen einzusetzen. Eine iterative Methode ist viel schneller, denn
bei der Rekursion landen die Zwischenergebnisse auf dem Stack. Setzt man ein paar
Methoden mit Rekursion ein, wird die Ausführung bedeuten langsamer sein !

Oder je nach Anwendung kann es zum Stackoverflow kommen, wenn eine zu hohe Rekursionstiefe erreicht wird. Java ist nunmal keine Sprache die für Rekursion optimiert ist wie Lisp, Prolog / Datalog und Dialekten selbiger z.B.

Im allgemeinen lässt sich aber nicht immer so leicht sagen welcher Ansatz besser ist. Das hingt im Einzelfall von der Aufgabe und den Gegebenheiten ab. Aber genug davon, das schweift etwas vom Thema ab.

 

[Landei]

Das ist so nicht ganz richtig. Eine bestimmte Teilklasse von Rekursionen, ("Tail calls" oder "Endrekursion") läßt sich relativ leicht in der JVM optimieren, und auch wenn das Oracles Version unverständlicherweise nicht tut, gibt es JVMs (etwa von IBM), die das so implementiert haben. In diesen JVMs würde etwa der Aufruf von [c]public void f(){ f(); }[/c] ewig laufen, ohne einen Stacküberlauf zu verursachen.