Rekursion

Zeppi

Zeppi

Aktives Mitglied
Moin,
ich habe eine Frage bezüglich der Rekursion. Ich frage mich, was genau abläuft, wenn man ein return hat, indem nicht wirklich was zurück gegeben wird.

Minesweeper:
char benutztesFeld[][] = new char[12][16];
public void aufdeckenNull(int x, int y){
char besetzt = 'B'
if (x < 0 || x > 11 || y < 0 || y > 15) {
            return;
        }

        if (benutztesFeld[x][y] == besetzt) {
            return;
        }
        if (benutztesFeld[x][y] != besetzt) {
            benutztesFeld[x][y] = besetzt;
            aufdeckenNull(x + 1, y);
            aufdeckenNull(x - 1, y);
            aufdeckenNull(x, y - 1);
            aufdeckenNull(x, y + 1);
        }
    }

}

Vielleicht kann mir das auch jemand anhand meines Programms erklären. Hierbei handelt es sich um Minesweeper und die Aufdeckung.
Ich frage mich eigentlich, wohin man springt mit dem return und und wie weiß das Programm, welches aufdeckenNull(x,y) er als nächstes nehmen muss?

Edit* springt man dann quasi vom return zum nächsten aufdeckenNull(x-1,y) und beim nächsten return zum aufdecken(x,y-1) usw.?

Vielleicht hat jemand einen Tipp.
Danke Zeppi
 
kneitzel

kneitzel

Top Contributor
Das Return beendet die Ausführung der Methode und er Springt dann zum Aufrufer zurück.

Wenn der Aufruf in Zeile 13 war, dann geht es bei Deinem Beispiel in Zeile 14 weiter. Das ist aber dem return egal. Das ist Sache von der Stelle, an der die Methode aufgerufen wurde.
 
Zeppi

Zeppi

Aktives Mitglied
Das Return beendet die Ausführung der Methode und er Springt dann zum Aufrufer zurück.
Wenn er zum Aufrufer zurück springt, führt er die Methode dann erneut durch?

Wenn der Aufruf in Zeile 13 war, dann geht es bei Deinem Beispiel in Zeile 14 weiter. Das ist aber dem return egal. Das ist Sache von der Stelle, an der die Methode aufgerufen wurde.
Meinst du damit, wenn Zeile 13 ausgeführt wurde und dann dadurch in Zeile 5 ein Return kommt, dass er dann in Zeile 14 weitermacht?
 
kneitzel

kneitzel

Top Contributor
Also generell ist es so, dass er bei einem Methodenaufruf in die Methode springt, diese ausführt und dann zurück springt. Dabei ist es dem Computer egal, was für eine Methode das ist:

Also wenn Du hast:
Java:
f1();
f2();
f3();
Da geht es bei der Ausführung erst in die Methode f1. Wenn er da fertig ist (Also entweder zum Ende der Methode oder zu einem return gekommen ist, dann geht es nach f1 weiter. Da kommt dann f2(). Wenn er von f2() zurück kommt, dann geht es weiter zu f3().

Lass Dich nicht davon verwirren, dass das jetzt alles in einer Methode ist.

Mal Dir das evtl. zur Besseren Vorstellung auf vielen Zetteln auf. Also einfach ein Zettel mit der Methode mehrfach ausdrucken:
Du arbeitest dann die Methode ab. Wenn Du zu einem Methodenaufruf kommst, dann markierst Du Dir die Stelle, wo Du zuletzt warst und nimmst Dir einen Zettel von der aufgerufenen Methode. Den legst Du nun oben drauf. Das alte zählt nicht mehr, das ist erst einmal "weg" oder "Verborgen". Wenn Die Methode fertig ist, dann merkst Du dir ggf. die Rückgabe und schmeisst den Zettel weg. Die Rückgabe kommt dann da hin, wo der Aufruf war ...
So könnte man das evtl. einmal aktiv durchspielen....

Graphisch kann man das auch aufmalen. Dann hast Du einen Baum:
Du hast als Root den ersten Aufruf Deiner Methode. Wenn es zu den weiteren Aufrufen kommt, dann kommen da die 4 Knoten der Aufrufe, die nacheinander erfolgen. Dann bist Du in einem Knoten. Wenn es wieder zu den Stelle mit den Aufrufen kommen sollte, dann hat er auch die 4 neuen Knoten ... Wenn es bei einem Knoten nicht zu den Aufrufen kommen sollte, dann gehst Du eine Ebene zurück wo dann der nächste Knoten dran kommt.
So ein Baum zeigt dann den ganzen Ablauf, denn im Rahmen der Ausführung ist der ganze Baum durchlaufen worden.

Hilft eine diese visuellen Darstellungen evtl. etwas beim Verständnis?
 
Zeppi

Zeppi

Aktives Mitglied
Java:
Beispiel 1: int x = 9, int y = 7;

1.)

  benutztesFeld[9][7] = besetzt;

  aufdeckenNull(x + 1, y);

2.)

benutztesFeld[10][7] = besetzt;

aufdeckenNull(x + 1, y);

3.)

benutztesFeld[11][7] = besetzt;

aufdeckenNull(x + 1, y);

4.)

benutztesFeld[12][7] = besetzt;

if (x > 11){

return;

}
Jetzt ist doch die komplette Methode durch und die anderen Nachbarfelder in die anderen Richtungen werden doch gar nicht mehr überprüft, oder? Weil die if(benutztesFeld[x][y] != besetzt) nicht erfüllt ist.


Oder geht es jetzt so weiter?

Java:
5.)
benutztesFeld[11][7] = besetzt; //oder wird wenn von der Ausgangsposition geguckt? Also von 9,7?

aufdeckenNull(x - 1, y);

6.)

benutztesFeld[10][7] = besetzt;

if(benutztesFeld[10][7]==besetzt){

return;

}

7.)

aufdeckenNull(x , y + 1);

etc.
 
Zeppi

Zeppi

Aktives Mitglied
Ich glaub ich weiß jetzt, was passiert. Dafür habe ich mir mal das Programm geschrieben.
Java:
public class rekursion_test {
    public static void rek(int i) {
        if ( i == 0) {
            System.out.println("2");
            return;
        }if (i > 0) {
            rek(i-1);
            rek(i+2);
            System.out.println(i);
        }
    }

    public static void main(String[] args) {
        rek(5);

    }

}
Man bekommt natürlich ein StackOverFlow Error. Aber mit dem Debugger konnte ich trotzdem sehen, was Kneitzel meinte.
Das Programm läuft immer weiter, bis es auf das return kommt. Dann springt man auf rek(i+2), aber es wird dann nicht i = 0 übergeben, sondern die vorherige Zahl, also in dem Fall 1. Dann wird rek(1+2) , also i=3 wieder verwendet und die Anwendung läuft wieder von vorne los. Dann wird wieder von oben nach unten die Abfragen bearbeitet, also rek(i-1) wird wieder verwendet bis man auf das return stößt, dann kommt wieder rek(i+2) usw.... Endlos Schleife


**Edit**
Mir ist aufgefallen, wenn ich noch ein drittes rek(i+5) eintrage, wird das nie abgefragt, aber ich weiß nicht genau wieso.
 
Zuletzt bearbeitet:
kneitzel

kneitzel

Top Contributor
Durch die endlose Rekursion kommt er aus dem i+2 Aufruf nie zurück. Daher wird das, das danach kommt, die erreicht.
 
Zeppi

Zeppi

Aktives Mitglied
Durch die endlose Rekursion kommt er aus dem i+2 Aufruf nie zurück. Daher wird das, das danach kommt, die erreicht.
Oh, das ergibt Sinn. Danke
Habe mir es nochmal angeguckt, in dem ich wie in meiner Aufgabe oben die Zahlen in einem Array speicher, dadurch werden alle drei rek durchlaufen. Jetzt versteh ich, wie das abläuft.
 
Zuletzt bearbeitet:
mihe7

mihe7

Top Contributor
Hier mal eine Beispielausgabe, die die Aufrufe zeigt. Dort wird i auf 10 begrenzt, außerdem werden Zyklen entdeckt und angezeigt. Jede "Spalte" zeigt die Ausführung innerhalb eines Methodenaufrufs:
Code:
i == 5 > 0: rek(4)
|         i == 4 > 0: rek(3)
|         |         i == 3 > 0: rek(2)
|         |         |         i == 2 > 0: rek(1)
|         |         |         |         i == 1 > 0: rek(0)
|         |         |         |         |         i == 0: return
|         |         |         |         i == 1 > 0: rek(3)
|         |         |         |         |         i == 3: Zyklus
|         |         |         |         i == 1: return
|         |         |         i == 2 > 0: rek(4)
|         |         |         |         i == 4: Zyklus
|         |         |         i == 2: return
|         |         i == 3 > 0: rek(5)
|         |         |         i == 5: Zyklus
|         |         i == 3: return
|         i == 4 > 0: rek(6)
|         |         i == 6 > 0: rek(5)
|         |         |         i == 5: Zyklus
|         |         i == 6 > 0: rek(8)
|         |         |         i == 8 > 0: rek(7)
|         |         |         |         i == 7 > 0: rek(6)
|         |         |         |         |         i == 6: Zyklus
|         |         |         |         i == 7 > 0: rek(9)
|         |         |         |         |         i == 9 > 0: rek(8)
|         |         |         |         |         |         i == 8: Zyklus
|         |         |         |         |         i == 9 > 0: rek(11)
|         |         |         |         |         |         i == 11: return
|         |         |         |         |         i == 9: return
|         |         |         |         i == 7: return
|         |         |         i == 8 > 0: rek(10)
|         |         |         |         i == 10: return
|         |         |         i == 8: return
|         |         i == 6: return
|         i == 4: return
i == 5 > 0: rek(7)
|         i == 7: Zyklus
i == 5: return
 
Zeppi

Zeppi

Aktives Mitglied
Hier mal eine Beispielausgabe, die die Aufrufe zeigt. Dort wird i auf 10 begrenzt, außerdem werden Zyklen entdeckt und angezeigt. Jede "Spalte" zeigt die Ausführung innerhalb eines Methodenaufrufs:
Code:
i == 5 > 0: rek(4)
|         i == 4 > 0: rek(3)
|         |         i == 3 > 0: rek(2)
|         |         |         i == 2 > 0: rek(1)
|         |         |         |         i == 1 > 0: rek(0)
|         |         |         |         |         i == 0: return
|         |         |         |         i == 1 > 0: rek(3)
|         |         |         |         |         i == 3: Zyklus
|         |         |         |         i == 1: return
|         |         |         i == 2 > 0: rek(4)
|         |         |         |         i == 4: Zyklus
|         |         |         i == 2: return
|         |         i == 3 > 0: rek(5)
|         |         |         i == 5: Zyklus
|         |         i == 3: return
|         i == 4 > 0: rek(6)
|         |         i == 6 > 0: rek(5)
|         |         |         i == 5: Zyklus
|         |         i == 6 > 0: rek(8)
|         |         |         i == 8 > 0: rek(7)
|         |         |         |         i == 7 > 0: rek(6)
|         |         |         |         |         i == 6: Zyklus
|         |         |         |         i == 7 > 0: rek(9)
|         |         |         |         |         i == 9 > 0: rek(8)
|         |         |         |         |         |         i == 8: Zyklus
|         |         |         |         |         i == 9 > 0: rek(11)
|         |         |         |         |         |         i == 11: return
|         |         |         |         |         i == 9: return
|         |         |         |         i == 7: return
|         |         |         i == 8 > 0: rek(10)
|         |         |         |         i == 10: return
|         |         |         i == 8: return
|         |         i == 6: return
|         i == 4: return
i == 5 > 0: rek(7)
|         i == 7: Zyklus
i == 5: return
Ah Klasse. Danke
 
Zeppi

Zeppi

Aktives Mitglied
Wie kommt es eigentlich dazu, dass es keine Endlosschleife wird?
Wenn keine der if Schleifen abgelaufen wird, weil zero keine 0 ist, wird ja zum Ende der Methode gesprungen und von dort zu dem letzten Aufruf, der noch funktioniert hat, oder?
Hört die Schleife dann auf, wenn gar keine '0' gefunden werden kann? Wenn quasi jeder Aufruf nochmal rückwärts abgelaufen wird, aber keine 0 gefunden wurde?

Java:
char benutztesFeld[][] = new char[12][16];
public void aufdeckenNull(int x, int y){
char besetzt = 'B'
char zero = (minen.suche(new Koordinate(x, y))); //hier wird geguckt, welcher Char sich hinter der Koordinate x,y verbirgt.
                                              //Es kann also als Char eine 0,1,2,3...8 sein.
                                              //Es muss aber eine Null sein, da nur die Nullfelder aufgedeckt werden sollen
                                              //jedes Mal wenn die Methode neu aufgerufen wird, wird an der neuen x,y Position
                                              //nach dem Char geguckt.
    
    
if (x < 0 || x > 11 || y < 0 || y > 15) {
            return;
        }

        if (benutztesFeld[x][y] == besetzt) {
            return;
        }
        if (zero=='0' && benutztesFeld[x][y] != besetzt) {  //zero == '0' sein, da ja nur '0'Felder aufgedeckt werden sollen
            benutztesFeld[x][y] = besetzt;
            aufdeckenNull(x + 1, y);
            aufdeckenNull(x - 1, y);
            aufdeckenNull(x, y - 1);
            aufdeckenNull(x, y + 1);
        }
    }

}
 
J

Joreyk

Bekanntes Mitglied
Java:
if (x < 0 || x > 11 || y < 0 || y > 15) {
            return;
        }

        if (benutztesFeld[x][y] == besetzt) {
            return;
        }
        if (zero=='0' && benutztesFeld[x][y] != besetzt) {  //zero == '0' sein, da ja nur '0'Felder aufgedeckt werden sollen
            benutztesFeld[x][y] = besetzt;
            aufdeckenNull(x + 1, y);
            aufdeckenNull(x - 1, y);
            aufdeckenNull(x, y - 1);
            aufdeckenNull(x, y + 1);
        }
    }
das ist keine rekursion.. du benutzt nur dein return; um aus der methode raus zu kommen... eine rekursion liefert einen wert zurück und du lieferts void zurück
 
mihe7

mihe7

Top Contributor
das ist keine rekursion.. du benutzt nur dein return; um aus der methode raus zu kommen... eine rekursion liefert einen wert zurück und du lieferts void zurück
Rekursion bedeutet lediglich, dass die Definition einer Funktion/Prozedur/Methode unter Rückgriff (direkt oder indirekt) auf sich selbst erfolgt.
 
Zeppi

Zeppi

Aktives Mitglied
Java:
if (x < 0 || x > 11 || y < 0 || y > 15) {
            return;
        }

        if (benutztesFeld[x][y] == besetzt) {
            return;
        }
        if (zero=='0' && benutztesFeld[x][y] != besetzt) {  //zero == '0' sein, da ja nur '0'Felder aufgedeckt werden sollen
            benutztesFeld[x][y] = besetzt;
            aufdeckenNull(x + 1, y);
            aufdeckenNull(x - 1, y);
            aufdeckenNull(x, y - 1);
            aufdeckenNull(x, y + 1);
        }
    }
das ist keine rekursion.. du benutzt nur dein return; um aus der methode raus zu kommen... eine rekursion liefert einen wert zurück und du lieferts void zurück
warte was? Ich dachte es ist eine Rekursion, sobald man die Methode selbst aufruft.
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
K Rekursion: Rechenmauer mit Array erstellen Java Basics - Anfänger-Themen 17
K Rekursion einer Zahlenfolge (Ab- und Aufzählung) Java Basics - Anfänger-Themen 6
V Backtracking und Rekursion Java Basics - Anfänger-Themen 15
L REKURSION Java Basics - Anfänger-Themen 13
Kirby.exe Rekursion Java Basics - Anfänger-Themen 7
N for Schleife durch Rekursion ersetzen Java Basics - Anfänger-Themen 6
X Rekursion Java Basics - Anfänger-Themen 3
H Rekursion Java Basics - Anfänger-Themen 2
D Erste Schritte Rekursion Java Basics - Anfänger-Themen 13
M Rekursion Tage Ansteckung gesamte Bevölkerung Java Basics - Anfänger-Themen 15
M Java Rekursion Java Basics - Anfänger-Themen 9
G Java Rekursion Java Basics - Anfänger-Themen 5
J Rekursion Klausur Aufgabe Java Basics - Anfänger-Themen 2
N Rekursion Java Basics - Anfänger-Themen 18
M Verständnisproblem der Rekursion bei Arrays Java Basics - Anfänger-Themen 8
X Rekursion Rätsel Java Basics - Anfänger-Themen 4
N Klassen Rekursion mit Feldern von Objekten Java Basics - Anfänger-Themen 14
W Rekursion Java Basics - Anfänger-Themen 0
D Konsolenausgabe Zahlenfolge Rekursion Java Basics - Anfänger-Themen 3
J Ping Pong Methode mit Rekursion Java Basics - Anfänger-Themen 1
N Rekursion Java Basics - Anfänger-Themen 1
B Rekursion Basic Java Basics - Anfänger-Themen 15
O Rekursion Mergesort Java Basics - Anfänger-Themen 18
G Rekursion Java Basics - Anfänger-Themen 20
M Rekursion Java Basics - Anfänger-Themen 7
F Hilfe bei Rekursion... Java Basics - Anfänger-Themen 4
A Mit Rekursion Zufallszahlen erstellen und größte finden Java Basics - Anfänger-Themen 5
B Rekursion Wurzel Java Basics - Anfänger-Themen 39
O Rekursion ordentlich aufschreiben Java Basics - Anfänger-Themen 2
B Rekursion verstehen Java Basics - Anfänger-Themen 4
O Rekursion Java Basics - Anfänger-Themen 2
E Rekursion verstehen. Java Basics - Anfänger-Themen 4
E Rekursion Kisten befüllen Java Basics - Anfänger-Themen 10
E Rekursion verstehen Java Basics - Anfänger-Themen 2
O Rekursion, String Java Basics - Anfänger-Themen 8
N Invertierte Rekursion??? Java Basics - Anfänger-Themen 5
M Bitte um Hilfe bei Quellcode (Rekursion) Java Basics - Anfänger-Themen 6
T Rekursion Warum bricht meine Funktion nicht ab Java Basics - Anfänger-Themen 4
A Hilfe bei Rekursion,Ich verstehe nicht,wie funktioniert die Rekursion in der Methode "walk" Java Basics - Anfänger-Themen 13
L Rekursion im Baum Java Basics - Anfänger-Themen 9
E Pfade eines Baums angeben ohne Rekursion Java Basics - Anfänger-Themen 20
L Rekursion Baumknoten Java Basics - Anfänger-Themen 8
L Rekursion größtes Zeichen Java Basics - Anfänger-Themen 8
L Rekursion Modulo Java Basics - Anfänger-Themen 7
I Rekursion Java Basics - Anfänger-Themen 11
H Rekursion Java Basics - Anfänger-Themen 7
N Methoden zur Rekursion (catalansche Zahlen) Java Basics - Anfänger-Themen 4
S Frage zu Rekursion... Java Basics - Anfänger-Themen 15
N Java catalansche Zahlen (Rekursion) Java Basics - Anfänger-Themen 5
S Noch eine Frage zur Rekursion... Java Basics - Anfänger-Themen 11
S Frage zu einer Rekursion Java Basics - Anfänger-Themen 15
F Methoden Abbruchbedingung bei Rekursion Java Basics - Anfänger-Themen 2
Z Rekursion Primzahlen Java Basics - Anfänger-Themen 1
K Rekursion Verständnisfrage Java Basics - Anfänger-Themen 19
L Methoden Rekursion gibt alten Wert wieder Java Basics - Anfänger-Themen 37
M Rekursion Minimums Suche Java Basics - Anfänger-Themen 12
J Rekursion Java Basics - Anfänger-Themen 5
F Aufgabe Rekursion Binärer Baum Java Basics - Anfänger-Themen 15
N Rekursion Java Basics - Anfänger-Themen 2
B Rekursion - Übung Java Basics - Anfänger-Themen 2
B Problem beim grundsätzlichen Verständnis bei Rekursion mit 2-dimensionalen Array Java Basics - Anfänger-Themen 6
P Rekursion Java Basics - Anfänger-Themen 19
G Rekursion Beispiel Java Basics - Anfänger-Themen 3
M Rekursion schreiben Java Basics - Anfänger-Themen 16
A Rekursion Funktion in eine Iterativ Funktion umwandeln Java Basics - Anfänger-Themen 9
T Array Rekursion Java Basics - Anfänger-Themen 1
B lineare und schlichte Rekursion Java Basics - Anfänger-Themen 1
A Rekursion Java Basics - Anfänger-Themen 2
B Rekursion Java Basics - Anfänger-Themen 3
A Rekursion stoppt an der falschen Stelle Java Basics - Anfänger-Themen 4
A Lineare Rekursion Java Basics - Anfänger-Themen 6
P Hilfe zur Rekursion? Java Basics - Anfänger-Themen 2
B Rekursion Schneeflocke - Kurze Frage zur Methode Java Basics - Anfänger-Themen 11
L Rekursion Java Basics - Anfänger-Themen 4
S Rekursion Rückgabe - Türme von Hanoi Java Basics - Anfänger-Themen 16
kilopack15 Rekursion und Schleifen Java Basics - Anfänger-Themen 27
E Rekursion Java Basics - Anfänger-Themen 10
JavaXava rekursion nicht verstanden Java Basics - Anfänger-Themen 5
K Rekursion-Verständnisfrage Java Basics - Anfänger-Themen 4
E Methoden String wird in Rekursion nicht überschrieben Java Basics - Anfänger-Themen 2
T 2fach Rekursion. Java Basics - Anfänger-Themen 4
N Rekursion mit if-Anweisung Java Basics - Anfänger-Themen 10
K Methoden Zahlensysteme umwandeln mittels Rekursion Java Basics - Anfänger-Themen 5
H Rekursion Binäre Suche Java Basics - Anfänger-Themen 2
P Methoden Primzahltest mit Rekursion Java Basics - Anfänger-Themen 3
C Rekursion überführen in eine normale methode Java Basics - Anfänger-Themen 1
M Methoden Rekursion nachvollziehen Java Basics - Anfänger-Themen 4
C Rekursion Java Basics - Anfänger-Themen 6
B Rekursion - Variable initialisieren Java Basics - Anfänger-Themen 2
B Rekursion von Hand durchführen Java Basics - Anfänger-Themen 2
Z Rekursion Java Basics - Anfänger-Themen 4
C Rekursion auf einem Array(negative werte addieren) Java Basics - Anfänger-Themen 4
O Methoden rekursion Java Basics - Anfänger-Themen 7
P Rekursion mit 2 Aufrufen Java Basics - Anfänger-Themen 4
J Hilfe! Rekursion Java Basics - Anfänger-Themen 28
A Rekursion, Anzahl von Stellen ausgeben Java Basics - Anfänger-Themen 7
A Rekursion (anhand von Mergesort) nachvollziehen Java Basics - Anfänger-Themen 4
E Erste Schritte Verschiedene Anfängerfragen (Rekursion, Terminierung, Schleife, etc.) Java Basics - Anfänger-Themen 5
A Frage zur Rekursion Java Basics - Anfänger-Themen 8
D Klausur Vorbereitung: Listen, Rekursion, Bäume & Vererbung Java Basics - Anfänger-Themen 3

Ähnliche Java Themen


Oben