Endlosrekursion

schlelia

Aktives Mitglied
Hallo,
ich habe eine (vielleicht) simple Frage. Es handelt sich hierbei um Java. Gan einfach gesagt geht es um Rekursion. In meinem Rekursionsfall will ich folgendes machen: Ich bekomm zwei Zahlen wie z.B. 0 und 4. Da will ich dann jede einzelne Zahl dazwischen "überprüfen". Also im ersten Rekursionschritt sollte 0,1 rauskommen, im zweiten 1,2, im dritten 2,3 und im vierten 3,4. Bzw. wenn man es ein wenig anders macht so: Im ersten 0,1 und 4,3, im zweiten 1,2 und 3,2 und im dritten dann 2,2. Ich habe schon etwas versucht und zwar das hier (id0 und id1 sind einfach zwei Zahlen):
Java:
return istErreichbar(id0, id0 + 1) && istErreichbar(id1 - 1, id1);
Bei meinem Beispiel berechnet es zwar noch 3,4 und 4,3, aber ab dann ist es in einer Endlosrekursion. Wie schreibe ich das um, damit es genau das mach was ich will?
 
K

kneitzel

Gast
Du brauchst natürlich eine Validierung: Wenn die erste Ziffer > als die zweite ist, dann musst Du abbrechen. Zumindest scheint es, dass dies der Fall ist, den Du nicht berücksichtigt hast. Aber die genauen Details sehen wir ja auch nicht, so dass dies nicht klar gesagt werden kann.
 

schlelia

Aktives Mitglied
Du brauchst natürlich eine Validierung: Wenn die erste Ziffer > als die zweite ist, dann musst Du abbrechen. Zumindest scheint es, dass dies der Fall ist, den Du nicht berücksichtigt hast. Aber die genauen Details sehen wir ja auch nicht, so dass dies nicht klar gesagt werden kann.
Java:
public static boolean istErreichbar(int id0, int id1, int e) {

        if (testeFreundschaft(id0, id1)) {
            return true;
        }
        if (Math.abs(id0 - id1) > e) {
            return false;
        }
        return istErreichbar(id0, id0 + 1, e) && istErreichbar(id1 - 1, id1, e);

    }
Hier ist mal die Aufgabe. Alle anderen Methoden fun ktionieren. Nur eben diese nicht.
Bildschirmfoto 2021-11-19 um 22.25.54.pngBildschirmfoto 2021-11-19 um 22.26.01.png
 

mihe7

Top Contributor
Fangen wir mal von vorne an: die Methode istErreichbar soll bestimmen, ob zwei gegebene Nutzer id0 und id1 innerhalb einer gegebenen Distanz e miteinander "bekannt" sind.

Für die Distanz können wir verschiedene Fälle ansehen:
e < 0: eine negative Distanz gibt es nicht. Das könnte man als Fehler betrachten oder die Frage der Erreichbarkeit sofort verneinen.

e = 0: ohne Distanz kann höchstens der Nutzer selbst "erreichbar" sein, d. h. wenn gilt id0 == id1. Wie man den Fall berücksichtigt, ist ein wenig Interpretationssache.

e = 1: die Erreichbarkeit mit Distanz von 1 ist der Tabelle zu entnehmen (bzw. Methode testeFreundschaft).

e > 1: jetzt wird es interessant. Zwei Nutzer sind offenbar dann miteinander bekannt, wenn ein Freund des Nutzers 1 (o.B.d.A.) mit Nutzer 2 bekannt ist. Jetzt müssen wir noch die Distanz berücksichtigen: der Freund von Nutzer 1 hat vom Nutzer 1 eine Distanz von e'=1. Damit muss Nutzer 2 für den Freund von Nutzer 1 innerhalb einer Distanz von e''=e-1 erreichbar sein, so dass e = e' + e'' gilt.

Wir können nun davon ausgehen, dass die Methode istErreichbar bereits korrekt implementiert ist, d. h. für jeden Freund f von Nutzer id0 brauchen wir nur zu testen, ob Nutzer id1 vom Freund aus in Distanz e-1 erreichbar ist, also ob istErreichbar(snmp, f, id1, e-1) gilt.

Ohne Optimierung -> fertig.
 

schlelia

Aktives Mitglied
Fangen wir mal von vorne an: die Methode istErreichbar soll bestimmen, ob zwei gegebene Nutzer id0 und id1 innerhalb einer gegebenen Distanz e miteinander "bekannt" sind.

Für die Distanz können wir verschiedene Fälle ansehen:
e < 0: eine negative Distanz gibt es nicht. Das könnte man als Fehler betrachten oder die Frage der Erreichbarkeit sofort verneinen.

e = 0: ohne Distanz kann höchstens der Nutzer selbst "erreichbar" sein, d. h. wenn gilt id0 == id1. Wie man den Fall berücksichtigt, ist ein wenig Interpretationssache.

e = 1: die Erreichbarkeit mit Distanz von 1 ist der Tabelle zu entnehmen (bzw. Methode testeFreundschaft).

e > 1: jetzt wird es interessant. Zwei Nutzer sind offenbar dann miteinander bekannt, wenn ein Freund des Nutzers 1 (o.B.d.A.) mit Nutzer 2 bekannt ist. Jetzt müssen wir noch die Distanz berücksichtigen: der Freund von Nutzer 1 hat vom Nutzer 1 eine Distanz von e'=1. Damit muss Nutzer 2 für den Freund von Nutzer 1 innerhalb einer Distanz von e''=e-1 erreichbar sein, so dass e = e' + e'' gilt.

Wir können nun davon ausgehen, dass die Methode istErreichbar bereits korrekt implementiert ist, d. h. für jeden Freund f von Nutzer id0 brauchen wir nur zu testen, ob Nutzer id1 vom Freund aus in Distanz e-1 erreichbar ist, also ob istErreichbar(snmp, f, id1, e-1) gilt.

Ohne Optimierung -> fertig.
Aber es soll ja auch mit größerer "Entfernung" funktionieren. Z.B. id0 = 0 und id1 = 10. Ich wäre halt so vorgegangen, dass man alle Freunschaft dazwischen überprüft. Also ob 0 und 1, 1 und 2, 2 und 3 ..... 9 und 10 miteinander befreundet sind. Nur wenn das bei allen true ist, ist auch istErreichbar true
 
K

kneitzel

Gast
Aber das ist doch so komplett falsch. So eine Kette brauchst du nicht.

Du brauchst eine beliebige Kette, die von A nach B geht, die über beliebige Stationen geht.

Also wenn du 5 und 10 prüfst, dann kann es sein, dass 5 die 1 kennt. Und die 1 kennt die 10. Also gibt es die Kette 5 - 1 - 10
 

mihe7

Top Contributor
Ich werde es mal versuchen

Bloß, damit Du nicht irgendwas rumprobierst: das ist, was ich in #4 skizziert habe:

Wir können nun davon ausgehen, dass die Methode istErreichbar bereits korrekt implementiert ist, d. h. für jeden Freund f von Nutzer id0 brauchen wir nur zu testen, ob Nutzer id1 vom Freund aus in Distanz e-1 erreichbar ist, also ob istErreichbar(snmp, f, id1, e-1) gilt.

Sagen wir mal, Du willst wissen, ob 5 und 10 sich in einer Entfernung von max. 3 kennen und sagen wir mal, 5 hätte 1, 4, 7 als Freunde.

Die Entfernung ist 3 also größer als 0, also kannst Du erstmal die Freunde von 5 ermitteln, bekommst 1, 4, 7 als Ergebnis. Die 10 ist nicht dabei, also prüfst Du für jeden dieser Freunde ob die 10 in einer Entfernung von max. 2 erreichbar ist. An der Stelle hast Du den rekursiven Aufruf.

Im rekursiven Abstieg für 1 geht das Spiel von vorne los: die Entfernung ist 2 also größer als 0, also kannst Du erstmal die Freunde von 1 ermitteln. Ist die 10 dabei, bist Du fertig. Ansonsten prüfst Du für jeden der Freunde von 1, ob die 10 in einer Entfernung von max. 1 erreichbar ist. An der Stelle hast Du wieder einen rekursiven Aufruf.

Jetzt geht das Spiel wieder von vorne los: die Entfernung ist 1 also größer als 0, damit kannst Du erstmal die Freunde ermitteln, ist die 10 dabei, bist Du fertig, ansonsten ... in einer Entfernung von max. 0 erreichbar ist. An der Stelle hast Du wieder einen rekursiven Aufruf.

Und noch eine Runde: diesmal ist die Entfernung aber 0 und damit kannst Du sofort das Ergebnis zurückgeben. Das wird in diesem konkreten Fall immer false sein, was schon ein Hinweis darauf ist, dass der letzte rekursive Aufruf unnötig ist.
 

schlelia

Aktives Mitglied
Bloß, damit Du nicht irgendwas rumprobierst: das ist, was ich in #4 skizziert habe:



Sagen wir mal, Du willst wissen, ob 5 und 10 sich in einer Entfernung von max. 3 kennen und sagen wir mal, 5 hätte 1, 4, 7 als Freunde.

Die Entfernung ist 3 also größer als 0, also kannst Du erstmal die Freunde von 5 ermitteln, bekommst 1, 4, 7 als Ergebnis. Die 10 ist nicht dabei, also prüfst Du für jeden dieser Freunde ob die 10 in einer Entfernung von max. 2 erreichbar ist. An der Stelle hast Du den rekursiven Aufruf.

Im rekursiven Abstieg für 1 geht das Spiel von vorne los: die Entfernung ist 2 also größer als 0, also kannst Du erstmal die Freunde von 1 ermitteln. Ist die 10 dabei, bist Du fertig. Ansonsten prüfst Du für jeden der Freunde von 1, ob die 10 in einer Entfernung von max. 1 erreichbar ist. An der Stelle hast Du wieder einen rekursiven Aufruf.

Jetzt geht das Spiel wieder von vorne los: die Entfernung ist 1 also größer als 0, damit kannst Du erstmal die Freunde ermitteln, ist die 10 dabei, bist Du fertig, ansonsten ... in einer Entfernung von max. 0 erreichbar ist. An der Stelle hast Du wieder einen rekursiven Aufruf.

Und noch eine Runde: diesmal ist die Entfernung aber 0 und damit kannst Du sofort das Ergebnis zurückgeben. Das wird in diesem konkreten Fall immer false sein, was schon ein Hinweis darauf ist, dass der letzte rekursive Aufruf unnötig ist.
Die Freunde von z.B. 5 ermittle ich am besten mit einer Schleife oder? Die das Array an der Stelle untersucht
 

schlelia

Aktives Mitglied
Java:
public static boolean istErreichbar(SNMP snmp, int id0, int id1, int e) {
        snmp.istErreichbar(id0, id1, e);
        if (e == 0) {
            return false;
        }
        for (int i = 0; i < freundschaft[id0].length; i++) {
            if (freundschaft[id0][i]) {
                return true;
            }
            else {
                return istErreichbar(snmp, i, id1, e - 1);
            }
        }

    }
Bin ich mit sowa hier auf der richtigen Spur?
 

mihe7

Top Contributor
Zeile 2 ist natürlich unsinnig. Zeile 4 muss man sich überlegen, ob das in Ordnung ist -> Interpretationsspielraum.

Zeile 11 ist jedenfalls falsch, damit brichst Du die Schleife in der ersten Iteration ab.
 

schlelia

Aktives Mitglied
Zeile 2 ist natürlich unsinnig. Zeile 4 muss man sich überlegen, ob das in Ordnung ist -> Interpretationsspielraum.

Zeile 11 ist jedenfalls falsch, damit brichst Du die Schleife in der ersten Iteration ab.
Java:
public static boolean istErreichbar(SNMP snmp, int id0, int id1, int e) {
        snmp.istErreichbar(id0, id1, e);
        if (e == 0) {
            return false;
        }
        if (freundschaft[id0][id1]) {
            return true;
        }
        int temp = 0;
        for (int i = 0; i < freundschaft[id0].length; i++) {
            if (freundschaft[id0][i]) {
                temp = i;
            }
        }
        return istErreichbar(snmp, temp, id1, e - 1);

    }
So müsste es passen oder?
 

mihe7

Top Contributor
Nein, das ist total falsch. Die Schleife vorhin (aus #12) war schon nicht schlecht, nur darfst Du nicht in jedem Fall sofort zurückkehren.
 

Neumi5694

Top Contributor
Außerdem brauch ich ja auch noch ein return außerhalb der Schleife. Sonst kommt die Meldung missing return statement
Das ist richtig. Und sofern du es nirgendwo anders getan hast, musst du an dieser Stelle entscheiden, ob du bereits ein Ergebnis hast und dieses lieferst oder ob du weiter in die Rekursion rein musst.
Als du noch die Returns in der Schleife hattest, war dein Problem, dass du in jedem Fall ein return stehen hattest, was zur Folge hat, dass nur das erste Element betrachtet wird.
 

schlelia

Aktives Mitglied
Das ist richtig. Und sofern du es nirgendwo anders getan hast, musst du an dieser Stelle entscheiden, ob du bereits ein Ergebnis hast und dieses lieferst oder ob du weiter in die Rekursion rein musst.
Als du noch die Returns in der Schleife hattest, war dein Problem, dass du in jedem Fall ein return stehen hattest, was zur Folge hat, dass nur das erste Element betrachtet wird.
Verstehe ich das richtig so, dass der Rekursionsfall dann nicht in die Schleife gehört?
 

Neumi5694

Top Contributor
Verstehe ich das richtig so, dass der Rekursionsfall dann nicht in die Schleife gehört?
Ich hab das Problem jetzt nur kurz überflogen, aber gefühlt würde ich sagen, dass der andere Fall nicht in die Schleife gehört.

Stell einfach die Frage: Falls die Bedingung in der Schleife erfüllt ist? Muss ich dann nach dem Freund des Freundes suchen oder hab ich einen gültigen Rückgabewert? Was ist, falls der Wert false ist? Abbruch oder nächstes Element?
Draußen kommt dann noch das, was gemacht werden muss, wenn kein Element der Schleife die Bedingung erfüllt.
 
Zuletzt bearbeitet:

schlelia

Aktives Mitglied
Ich hab das Problem jetzt nur kurz überflogen, aber gefühlt würde ich sagen, dass der andere Fall nicht in die Schleife gehört.

Stell einfach die Frage: Falls
Code:
(freundschaft[id0][i])
, muss ich dann nach dem Freund des Freundes suchen oder hab ich einen gültigen Rückgabewert?
Was mach ich, wenn keines der Elemente (das war das Problem, du hattest nur das erste überprüft) in dieser Schleife die Bedingung erfüllt hat?
Naja der erste Fall in der Schleife wäre ja, dass an dieser Stelle eine Freundschaft gefunden wurde (5 befreundet mit 1). Das heißt ich muss dann noch mal für 1 und eine niedrigere Umgebung (e) die Freundschaften untersuchen. Aber da ist doch genau der rekursive Aufruf. Was muss ich denn dann bei
Java:
(freundschaft[id0][i])
genau zurückgeben? Meine Idee in #15 war, dass ich eine Variable temp erstelle, die das den zu untersuchenden Nutzer (hier 1) weiterleitet (in den Rekursionsfall).
 

Neumi5694

Top Contributor
Naja der erste Fall in der Schleife wäre ja, dass an dieser Stelle eine Freundschaft gefunden wurde (5 befreundet mit 1). Das heißt ich muss dann noch mal für 1 und eine niedrigere Umgebung (e) die Freundschaften untersuchen. Aber da ist doch genau der rekursive Aufruf. Was muss ich denn dann bei (freundschaft[id0]) zurückgeben? Meine Idee in #15 war, dass ich eine Variable temp erstelle, die den zu untersuchenden Nutzer (hier 1) weiterleitet zum Rekursionsfall
Das ist ein neuer Ansatz und auch absolut ok. In dem Fall musst du NACH der Schleife prüfen, ob du was gefunden hast oder nicht und dann entsprechend reagieren.

In beiden Vorgehensweisen solltest du dir noch überlegen, was du tun willst, falls 2 Freundschaft gefunden werden. Reagierst du bereits in der Schleife, dann wird keine weitere gesucht.
Mit deinem aktuellen Code - wo du nach der Schleife reagierst - würde die jeweils letzte gefundene Freundschaft verwendet, da du weiterprüfst, auch wenn du bereits ein Ergebnis gefunden hast.
 

schlelia

Aktives Mitglied
Das ist ein neuer Ansatz und auch absolut ok. In dem Fall musst du NACH der Schleife prüfen, ob du was gefunden hast oder nicht und dann entsprechend reagieren.

In beiden Vorgehensweisen solltest du dir noch überlegen, was du tun willst, falls 2 Freundschaft gefunden werden. Reagierst du bereits in der Schleife, dann wird keine weitere gesucht.
Mit deinem aktuellen Code - wo du nach der Schleife reagierst - würde die jeweils letzte gefundene Freundschaft verwendet, da du weiterprüfst, auch wenn du bereits ein Ergebnis gefunden hast.
Java:
public static boolean istErreichbar(SNMP snmp, int id0, int id1, int e) {
        snmp.istErreichbar(id0, id1, e);
        if (e == 0) {
            return false;
        }
        int temp = 0;
        for (int i = 0; i < freundschaft[id0].length; i++) {
            if (freundschaft[id0][i]) {
                temp = i;
            }
            else {
               return false;
            }
        }
        return istErreichbar(snmp, temp, id1, e - 1);

    }
Ich verstehe nicht so ganz wo da jetzt genau mein Fehler ist...
 

Neumi5694

Top Contributor
Java:
public static boolean istErreichbar(SNMP snmp, int id0, int id1, int e) {
        snmp.istErreichbar(id0, id1, e);
        if (e == 0) {
            return false;
        }
        int temp = 0;
        for (int i = 0; i < freundschaft[id0].length; i++) {
            if (freundschaft[id0][i]) {
                temp = i;
            }
            else {
               return false;
            }
        }
        return istErreichbar(snmp, temp, id1, e - 1);

    }
Ich verstehe nicht so ganz wo da jetzt genau mein Fehler ist...
Wird ein Element in der Liste gefunden, für das gilt
Code:
freundschaft[id0][i] == false
, so wird abgebrochen und false geliefert. Ist das so beabsichtigt? Müssen alle Elemente
Code:
freundschaft[id0][i] == true
ergeben oder reicht dir eines?
In dem Fall wäre das hier der Weg:
[CODE lang="java" title="Möglichkeit 1. Bei einem gefundenen Element in der Schleife agieren"]for (int i = 0; i < freundschaft[id0].length; i++) {
if (freundschaft[id0]) {
//TODO: was immer auch getan werden muss, falls ein gültiges Element gefunden wurde.
return istErreichbar(snmp, temp, id1, e - 1);
}
}
//TODO: Hier landen wir nur, wenn alle Abfragen false ergaben. Was ist jetzt zu tun?
[/CODE]
[CODE lang="java" title="Möglichkeit 2: Auswertung NACH der Schleife"]int validIndex = -1; //-1, da 0 ein gültiger Wert ist
for (int i = 0; i < freundschaft[id0].length; i++) {
if (freundschaft[id0]) {
validIndex = i;
break; //falls der erste gültige Wert verwendet werden soll, danach brauchen wir ja nicht weiterzusuchen.
}
}
if (validIndex < 0) {
//TODO: nichts gefunden, was jetzt?
} else {
return istErreichbar(snmp, validIndex, id1, e - 1);
}[/CODE]
ps: Anstatt dem break kannst du auch im Mittelteil der for-Schleife prüfen, ob validIndex immer noch < 0 ist, das wird von vielen als die sauberere Lösung angesehen.
 

schlelia

Aktives Mitglied
Wird ein Element in der Liste gefunden, für das gilt
Code:
freundschaft[id0][i] == false
, so wird abgebrochen und false geliefert. Ist das so beabsichtigt? Müssen alle Elemente
Code:
freundschaft[id0][i] == true
ergeben oder reicht dir eines?
In dem Fall wäre das hier der Weg:
[CODE lang="java" title="Möglichkeit 1. Bei einem gefundenen Element in der Schleife agieren"]for (int i = 0; i < freundschaft[id0].length; i++) {
if (freundschaft[id0]) {
//TODO: was immer auch getan werden muss, falls ein gültiges Element gefunden wurde.
return istErreichbar(snmp, temp, id1, e - 1);
}
}
//TODO: Hier landen wir nur, wenn alle Abfragen false ergaben. Was ist jetzt zu tun?
[/CODE]
[CODE lang="java" title="Möglichkeit 2: Auswertung NACH der Schleife"]int validIndex = -1; //-1, da 0 ein gültiger Wert ist
for (int i = 0; i < freundschaft[id0].length; i++) {
if (freundschaft[id0]) {
validIndex = i;
break; //falls der erste gültige Wert verwendet werden soll, danach brauchen wir ja nicht weiterzusuchen.
}
}
if (validIndex < 0) {
//TODO: nichts gefunden, was jetzt?
} else {
return istErreichbar(snmp, validIndex, id1, e - 1);
}[/CODE]
ps: Anstatt dem break kannst du auch im Mittelteil der for-Schleife prüfen, ob validIndex immer noch < 0 ist, das wird von vielen als die sauberere Lösung angesehen.

Wenn es nichts gefunden hatt, dann muss es doch false rausgeben oder?
 

mihe7

Top Contributor
Ist Zeile 7 - 9 in #12 richtig? Muss ich nur etwas am Rekursionsfall ändern?
Also, ich löse mal das Rätsel zu "Die Schleife vorhin (aus #12) war schon nicht schlecht, nur darfst Du nicht in jedem Fall sofort zurückkehren."

In Deinem Code hast Du zwei Fälle, in denen Du immer sofort zurückkehrst. Das kann nicht funktionieren, weil Du damit die Schleife in der ersten Iteration abbrichst. Genauso gut könntest Du Dir die Schleife sparen und direkt
Java:
if (freundschaft[id0][0]) return true; else return istErreichbar(snmp, 0, id1, e-1);
schreiben.

Abgesehen davon, ist das natürlich auch von der Logik her unsinnig, denn wenn 0 kein Freund von id0 ist, dann spielt die Frage, ob id1 von 0 aus erreichbar ist, ja gerade keine Rolle.

Wann aber darfst Du die Schleife sofort beenden? Natürlich dann (und nur dann!), wenn für irgendeinen Freund von id0 die Erreichbarkeit von id1 festgestellt wurde. D. h. wenn (und nur wenn!) einmal feststeht, dass die Erreichbarkeit gegeben ist, musst Du keinen anderen Fall mehr untersuchen.

Heißt: i muss ein Freund von id0 sein UND id1 muss innerhalb einer Distanz von e-1 von i aus erreichbar sein. Wenn das der Fall ist, ist die Erreichbarkeit festgestellt und die Antwort kann sofort zurückgegeben werden:
Java:
        for (int i = 0; i < freundschaft[id0].length; i++) {
            if (freundschaft[id0][i] && istErreichbar(snmp, i, id1, e-1)) {
                return true;
            }
        }

Natürlich könntest Du hier auch mit einer Variablen arbeiten:
Java:
        boolean erreichbar = false;
        for (int i = 0; !erreichbar && i < freundschaft[id0].length; i++) {
            erreichbar = freundschaft[id0][i] && istErreichbar(snmp, i, id1, e-1);
        }
Durch die Schleifenbedingung endet die Schleife sofort, sobald erreichbar true ist.

Jetzt muss nur noch der Code außenrum, also vor und nach der Schleife stimmen. Das überlasse ich jetzt Dir, sonst kann ich gleich die ganze Lösung posten :)
 

schlelia

Aktives Mitglied
Also, ich löse mal das Rätsel zu "Die Schleife vorhin (aus #12) war schon nicht schlecht, nur darfst Du nicht in jedem Fall sofort zurückkehren."

In Deinem Code hast Du zwei Fälle, in denen Du immer sofort zurückkehrst. Das kann nicht funktionieren, weil Du damit die Schleife in der ersten Iteration abbrichst. Genauso gut könntest Du Dir die Schleife sparen und direkt
Java:
if (freundschaft[id0][0]) return true; else return istErreichbar(snmp, 0, id1, e-1);
schreiben.

Abgesehen davon, ist das natürlich auch von der Logik her unsinnig, denn wenn 0 kein Freund von id0 ist, dann spielt die Frage, ob id1 von 0 aus erreichbar ist, ja gerade keine Rolle.

Wann aber darfst Du die Schleife sofort beenden? Natürlich dann (und nur dann!), wenn für irgendeinen Freund von id0 die Erreichbarkeit von id1 festgestellt wurde. D. h. wenn (und nur wenn!) einmal feststeht, dass die Erreichbarkeit gegeben ist, musst Du keinen anderen Fall mehr untersuchen.

Heißt: i muss ein Freund von id0 sein UND id1 muss innerhalb einer Distanz von e-1 von i aus erreichbar sein. Wenn das der Fall ist, ist die Erreichbarkeit festgestellt und die Antwort kann sofort zurückgegeben werden:
Java:
        for (int i = 0; i < freundschaft[id0].length; i++) {
            if (freundschaft[id0][i] && istErreichbar(snmp, i, id1, e-1)) {
                return true;
            }
        }

Natürlich könntest Du hier auch mit einer Variablen arbeiten:
Java:
        boolean erreichbar = false;
        for (int i = 0; !erreichbar && i < freundschaft[id0].length; i++) {
            erreichbar = freundschaft[id0][i] && istErreichbar(snmp, i, id1, e-1);
        }
Durch die Schleifenbedingung endet die Schleife sofort, sobald erreichbar true ist.

Jetzt muss nur noch der Code außenrum, also vor und nach der Schleife stimmen. Das überlasse ich jetzt Dir, sonst kann ich gleich die ganze Lösung posten :)
Erstmal vielen Dank.
Vor der Schleife brauch ich ja noch den Basisfall , damit die Rekursion irgendwann abbricht.
Java:
 if (e == 0) {
            return false;
        }
Nach der Schleife brauch ich eigentlich nur ein return Statement mit einem weiteren Rekursionsaufruf
 

schlelia

Aktives Mitglied
Warum willst Du nach der Schleife nochmal rekursiv aufrufen?
Java:
public static boolean istErreichbar(SNMP snmp, int id0, int id1, int e) {
        snmp.istErreichbar(id0, id1, e);
        if (e == 0) {
            return false;
        }
        if (freundschaft[id0][id1]) {
            return true;
        }
        for (int i = 0; i < freundschaft[id0].length; i++) {
            if (freundschaft[id0][i] && istErreichbar(snmp, i, id1, e-1)) {
                return true;
            }
        }
        return false;

    }
Für einen Fall funktioniert es schonmal. Bei einem anderen bekomm ich einen Timeout
 

mihe7

Top Contributor
Ah, das ist ein anderes istErreichbar, sorry übersehen. Dann kann es ja nur noch daran liegen, dass in der Schleife auch der Fall freundschaft[id0][id0] rekursiv behandelt wird.
 

mihe7

Top Contributor
Nein, nicht abbrechen. Nur nicht rekursiv absteigen.
Java:
if (id0 != i && freundschaft[id0][i] && istErreichbar(snmp, i, id1, e-1)) {
Was mir außerdem gerade auffällt: der Fall e < 0 ist noch nicht korrekt behandelt.
 

schlelia

Aktives Mitglied
Nein, nicht abbrechen. Nur nicht rekursiv absteigen.
Java:
if (id0 != i && freundschaft[id0][i] && istErreichbar(snmp, i, id1, e-1)) {
Was mir außerdem gerade auffällt: der Fall e < 0 ist noch nicht korrekt behandelt.
Okay funktioniert jetzt alles. Aber im Text steht glaub ich nicht explizit dass man e < 0 beachten soll
 

mihe7

Top Contributor
Aber im Text steht glaub ich nicht explizit dass man e < 0 beachten soll
Wenn das so angegeben ist, dann erübrigt sich von meiner Seite alles dazu :)

Schön, wenn es jetzt funktioniert, die Frage, die Du Dir jetzt stellen musst: hast Du es auch verstanden? Schau Dir alles nochmal genau an und versuche es, nachzuvollziehen. Wenn was unklar ist, einfach fragen. Wichtig ist das Verständnis, nicht der Code.
 

Neumi5694

Top Contributor
Wenn es nichts gefunden hatt, dann muss es doch false rausgeben oder?
Scheint ja jetzt zu klappen, super :)
Aber nur noch zu dieser Frage: "nichts finden" heißt, dass die Bedingung im keinem Fall zutreffen darf. Wenn sie in EINEM Fall nicht zutrifft, sollte nicht sofort false zurückgegeben werden, sie könnte ja für das nächste Element zutreffen. Deine ursprüngliche Schleife lieferte schon beim ersten Fehlversuch false.

Ich denke, hier muss auch noch aufgepasst werden, dass man nicht womöglich in einer Endlosfreundschaftsschleife landet z.B. 1-2-4-5-2-4-5-2-4-5...
Vielleicht hab ich's übersehen, aber irgendwie vermiss ich hier, welche Ausgangspersonen bereits behandelt wurden.
 

schlelia

Aktives Mitglied
Wenn das so angegeben ist, dann erübrigt sich von meiner Seite alles dazu :)

Schön, wenn es jetzt funktioniert, die Frage, die Du Dir jetzt stellen musst: hast Du es auch verstanden? Schau Dir alles nochmal genau an und versuche es, nachzuvollziehen. Wenn was unklar ist, einfach fragen. Wichtig ist das Verständnis, nicht der Code.
Ja. Andere Rekursionsaufgaben hab ich eigentlich sehr gut verstanden, nur hier war das Problem irgendwie nicht so richtig greifbar für mich
 

mihe7

Top Contributor
Ja. Andere Rekursionsaufgaben hab ich eigentlich sehr gut verstanden, nur hier war das Problem irgendwie nicht so richtig greifbar für mich
Es kommen mit Sicherheit noch weitere Aufgaben in der Richtung, z. B. suche rekursiv in einer verketteten Liste oder in einem Baum nach einem Element oder gib die Elemente einer verkettete Liste rekursiv rückwärts aus usw. Kannst Du auch als Übungsaufgaben verwenden. Das Verständnis für die Rekursion ist nicht unwichtig aber ob Du das hast, kann ich nicht sagen (anhand dieses Thread würde ich zu einem Nein tendieren, aber das muss ja nichts bedeuten), das musst Du selbst beurteilen.
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
U Scheinbare Endlosrekursion Java Basics - Anfänger-Themen 3

Ähnliche Java Themen

Neue Themen


Oben