Rekursive Methode

[Ru$h]

Hallo,

folgende Methode ist eine Scheinrekursion, da man hier auch eine for-´Schleife verwenden kann.

 public ArrayList zuordnen (ArrayList reiter){
            if (reiter.isEmpty()){
                return reiter;
            }
            Reiter DerReiter = waehlerischsterReiter(reiter);
            if (passendesPferd(DerReiter)){
                DerReiter.setpassendesPferd(zuordnungPferd(DerReiter));           
            }
            reiter.remove(DerReiter);
            DerReiter.removeWuensche();
            return zuordnen(reiter);   
        }

Wie kann ich eine richtige Rekursion daraus machen?

 

[httpdigest]

folgende Methode ist eine Scheinrekursion, da man hier auch eine for-´Schleife verwenden kann.

Ja, man _kann_ eine for-Schleife verwenden. Wurde ja aber nicht. Stattdessen wurde eine Rekursion verwendet. Warum ist das dann jetzt keine Rekursion?
Hint zum Schluss: Endrekursionen[1] können immer als Iteration implementiert werden.
[1]: https://de.wikipedia.org/wiki/Endrekursion

 

[Ru$h]

Weil die "Rekursion" nur in eine Richting funktioniert. Das heist wenn reiter.isEmpty, dann soll die Liste von unten nach oben aufgebaut werden und nicht nur wie in diesem Fall von oben nach unten.
Also so, dass man keine for-Schleife verwenden kann.

 

[mrBrown]

Weil die "Rekursion" nur in eine Richting funktioniert. Das heist wenn reiter.isEmpty, dann soll die Liste von unten nach oben aufgebaut werden und nicht nur wie in diesem Fall von oben nach unten.
Also so, dass man keine for-Schleife verwenden kann.

Häh? Ich habe keine Ahnung, was du damit sagen willst...

 

[Blender3D]

Wie kann ich eine richtige Rekursion daraus machen?

Ein iterative Lösung ist hier immer zu bevorzugen.
Rekursion:
Vorteil: schwierige Probleme lassen sich dadurch oft leichter formulieren.
Nachteil: Mit der Rekursionstiefe steigt der Speicherbedarf.
Obiges Problem ist als Schleife leicht zu formulieren. --> keine Rekursion benutzen. Es wird durch sie Scheinrekursion zwar kein Mehrspeicher benötigt, da der rekursive Aufruf am Ende der Funktion erfolgt. Und daher der Stack nicht mit dem Speicherzustand des augenblicklichen Funktion Aufrufes speichern muss.
Warum willst da etwas rekursiv machen ?
Schreib es lieber als Schleife hin.

 

[Ru$h]

Die Aufgabenstellung fordert eine Rekursion.
Vergleicht man meine Methode mit zum Beispiel der Fakultätsberechnung, so ist meine Methode umgeschrieben auf die Rekursion folgende:

private int value = 1;
public int fak(int n) {
            if(n==1) return 1;
            else {
                this.value *= n;
                return fak(n-1);
            }

Da ich hier aber auch eine for-Schleife verwenden kann, ist es eine Scheinrekursion und keine "richtige" Rekursion.
Zurück zu meiner eigentlichen Methode möchte ich wissen, wie ich aus dieser Methode eine richtige rekursive Methode machen kann. Denn wenn reiter.isEmpty, so wird eine leere Liste zurückgeben, das soll aber doch nicht sein, denn die Liste soll ja gefüllt werden, deshalb meine Frage, wie ich meine Methode rekursiv machen kann.

 

[httpdigest]

Man kann dir hier nur schwer helfen. Erstmal, weil du ein Wort verwendest, das es so in der Geschichte der Informatik noch niemals gab: Scheinrekursion.
Google Suchergebnisse: 1 (außer dieser Thread hier).
Das heißt, du musst erstmal definieren, was für dich denn eine sogenannte "Scheinrekursion" genau ist.
Desweiteren verwendest du sehr viele Methoden, die du nicht weiter definiert hast:
- waehlerischsterReiter
- passendesPferd
- Reiter.setpassendesPferd
- zuordnungPferd
- Reiter.removeWuensche
so dass es schwierig wird, hier überhaupt durchzusteigen, was was macht.
Nehme dein Problem doch mal komplett auseinander und definiere für Randfälle, wie du möchtest, dass deine Rekursion genau aussieht. Was passiert, wenn es keinen Reiter gibt? Das ist doch vermutlich immer noch deine Rekursionsabbruchbedingung, also genau wie jetzt auch...
Dann definiere, was passieren sollte, wenn es einen Reiter gibt, aber keine Pferde (oder so).
Spiele einfach mal ganz viele Fälle durch. Dann solltest du vielleicht zu einer Lösung kommen.

 

[Blender3D]

wie ich aus dieser Methode eine richtige rekursive Methode machen kann

Also am Beispiel Fakultät.
Deine rekursive Lösung würde ich so nicht machen weil das Attribut value vollkommen überflüssig ist.

private int value = 1;
public int fak(int n) {
if(n==1) return 1;
else {
this.value *= n;
return fak(n-1);
}

Ich würde ein Rekursion immer vermeiden wenn es eine gut iterative Lösung gibt, weil eine Rekursion bei jedem Funktionsaufruf den Speicher belastet. Rekursion ist immer dann angebracht wenn die iterative Lösung zu komplex wird.
Iterative:

static long facIterativ(int n) {
        long result = 1;
        for (int i = 2; i <= n; ++i)
            result *= i;
        return result;
    }

Rekursive: ohne Member auch das else kann Du Dir sparen.

    static long factRekursiv(long n) {
        if (n == 1)
            return 1;
        return factRekursiv(n - 1) * n;
    }

Jetzt zur Frage wie schreib man das rekursiv so hin, dass es keine Endrekursion mehr ist?
Ich sehe das so:
Aus meiner Sicht macht das keinen Sinn. Bei einer Endrekursion kann die JVM optimieren und sich das Zwischenspeichern der Speicherzustände einsparen. Eine, so wie Du sie nennst richtige Rekursion, wäre ja dann eine Verschlechterung der Lösung.
Wichtig ist es aber zu wissen, dass bei einer Endrekursion wahrscheinlich ein einfache iterative Lösung existiert.
Die sollte man wählen, da es die bessere Lösung ist.
Sag mir aber bitte bescheid, was Dein Professor damit gemeint hat


Eventuell so etwas

static long factRekursivStupid(long n) {
        long tmp = n;
        if (n > 1)
            tmp = n * factRekursivStupid(n - 1);
        return tmp;
    }

 

[Blender3D]

static long factRekursiv(long n) {
if (n == 1)
return 1;
return factRekursiv(n - 1) * n;
}

Korrektur: Da hier der letzte Aufruf mit einer Multiplikation verknüpft ist, handelt es sich hier nicht um eine Endrekursion. Also ist das bereits die gesuchte nicht so gute Lösung.
Endrekursion:

static long factEndRecursiv(long n, long akk) {
        if (n == 1)
            return akk;
        return factEndRecursiv(n - 1, akk * n);
    }