Rekursive Methode Stack Overflow

[Csircc]

Hey ich soll eine Rekursive Methode ohne for oder while schleifen schreiben.
Ich hab mein bestes versucht bekomme beim Ausführen jedoch einen stack overflow. Das liegt meines wissens daran, dass die Vabiable ich beim ausführen immer wieder zurück gesetzt wird. aber ich weiß nicht wie ich das ändern kann. Hilfe!!

public class Rekursiv
{

    public static int apply(int[] arr, int i)
    {
        int x=0;
        int j=0;

        if (0 <= i && i<arr.length)
        {

            if (0<=x && x<=i)
            {
                x++;
                if(arr[x]<4 && arr[x]>(-4))
                {
                    j++;

                }

                apply(arr, i);
            }

        }
        else
        {
            return 0;
        }
        return j;
    }
}

 

[mihe7]

Beim rekursiven Aufruf muss es einen Unterschied zum ursprünglichen Aufruf geben (in der Regel ändert sich direkt etwas an den Parametern), ansonsten wirst Du nie die Abbruchbedingung erreichen

 

[Csircc]

das hört sich logisch an! Ich sehe aber nicht an welcher stelle ich da was verändern kann. (Wahrscheinlich wegen mangelnder Erfahrung.

Das ist die Aufgabenstellung.
Vervollständige die Klasse Testat mit der Methode apply, die folgende Signatur besitzt:
public static int apply( int[] arr, int i )

Die Methode apply soll die folgende Funktionalität bereitstellen:
• Die Methode apply muss rekursiv arbeiten. Bei der Implementierung von apply dürfen die Schlüsselwörter for und while nicht verwendet werden. • Für alle i mit 0<=arr.length soll die Methode apply ermitteln, für wie viele x mit 0<=x<=i der Wert von arr[x] echt größer als -4 und echt kleiner als +4 ist. Die ermittelte Anzahl soll zurückgegeben werden.
• Für alle i, die außerhalb des Bereichs 0<=i<arr.length liegen, soll die Methode apply den Wert 0 zurückgeben.
• Es dürfen keine Attribute und keine weiteren Methoden in der Klasse Testat angelegt werden.
• Die Methode apply muss in einem Programm mehrfach nacheinander aufgerufen werden können und bei jedem Aufruf das entsprechend der Aufgabenbeschreibung korrekte Ergebnis zurückgeben.

 

[mihe7]

Vielleicht mal ein Beispiel:

public void countDown(int n) {
    if (n <= 0) {
        return;
    }
    System.out.println(n);
    countDown(n-1);
}

Zeile 2 prüft die Abbruchbedingung. Ist sie erfüllt, d. h. gilt n <= 0, dann ist die Sache erledigt und die Rekursion wird in Zeile 3 beendet.

Ansonsten (d. h. n > 0) wird in Zeile 5 das n ausgegeben. In Zeile 6 wird nun die Methode rekursiv aufgerufen. Diesmal jedoch mit n-1.

Ruft man also countDown(2) auf, wird die 2 ausgegeben, anschließend wird countDown(1) aufgerufen. Es wird die 1 ausgegeben, anschließend wird countDown(0) aufgerufen. Jetzt ist die Abbruchbedingung erfüllt, die Rekursion wird beendet.

 

[Csircc]

Ich hab jetzt ein bisschen rumprobiert. Das hat mir beim Verständnis der Rekursion sehr weiter geholfen jedoch funktioniert es immer noch nicht richtig (aber wenigstens kein Overflow mehr.) Gegeben werden mir jetzt aber nicht die Anzahl der indizies an deren stelle die bedingung erfüllt ist.

public static int apply(int[] arr, int i)
    {

        int x=i;
        int j =0;
        
        
        if (0 <= i && i<arr.length)
        {

            if (0<=x && x<=i)
            {

                if(arr[x]<4 && arr[x]>(-4))
                {
                    j++;
                    
                }
                if(x >0)
                {
                    apply(arr,x-1);
                }
                else
                {
                    return j;
                }
            }

        }
        else
        {
            return 0;
        }
        return j;
    }

 

[kneitzel]

Das generelle Vorgehen einer Rekursion ist oft:
- Check: Bin ich fertig? -> Ergebnis zurückgeben
- Aktuelles Element auswerten und zusammen mit Ergebnis der restlichen Elemente das Ergebnis ermitteln und zurück geben.

Deine rekursive Methode hat einen Rückgabewert. Aber beim rekursiven Aufruf interessiert Dich das Ergebnis nicht. Das sieht nicht wirklich korrekt aus.

 

[Csircc]

Ich hab aber das problem, dass ich die variable mit 0 initialisiere und dann beim Rekursiven aufruf ich diese immer wieder auf 0 zurück setze

 

[fhoffmann]

Schreibe dein Programm folgendermaßen:

1. Wenn i < 0 oder i >= arr.length: gib 0 zurück.
2. Ruf apply(arr, i-1) auf und merke dir den Rückgabewert!
3. Wenn das Array an der Stelle i zwischen -4 und 4 liegt, addiere 1 zu der gemerkten Zahl.
4. Gib diese Zahl zurück.

 

[Csircc]

Habs, danke euch sehr!!!

public static int apply(int[] arr, int i)
    {
        int x=i;
        int k=0;
        if(x<0)
        {
            return k;
        }
        if(0<=i && i<arr.length)
        {
            if(arr[x]>(-4) && arr[x]<4)
            {
                k=1 + apply(arr,i-1);
            }
            else
            {
                k= apply(arr, i-1);
            }
        }
        return k;
    }

 

[Csircc]

Das generelle Vorgehen einer Rekursion ist oft:
- Check: Bin ich fertig? -> Ergebnis zurückgeben
- Aktuelles Element auswerten und zusammen mit Ergebnis der restlichen Elemente das Ergebnis ermitteln und zurück geben.

Deine rekursive Methode hat einen Rückgabewert. Aber beim rekursiven Aufruf interessiert Dich das Ergebnis nicht. Das sieht nicht wirklich korrekt aus.

Hat mir sehr geholfen danke!

 

[mihe7]

Ein paar Anmerkungen:

1. Du kannst, wie von @fhoffmann vorgeschlagen, den Aufruf in Zeile 17 noch vor das if ziehen. Dann hast Du nur einen rekursiven Aufruf im Code, musst im then-Teil nur noch k um 1 erhöhen und der else-Teil fällt weg.
2. Ich würde in der Abbruchbedingung auch nicht k sondern ganz klar 0 zurückgeben.
3. Wofür Du eine Variable x benötigst, leuchtet auch nicht ganz ein, das i wird im Code ja nirgends verändert.
4. Die Bedingung 0<=i (also i >= 0) ist überflüssig, da zuvor schon der Fall i < 0 abgefangen wurde.
5. Leerraum erleichtert das Lesen

Das liefert zunächst:

    public static int apply(int[] arr, int i) {
        if (i < 0) {
            return 0;
        }

        int k=0;
        if (i < arr.length) {
            k = apply(arr, i-1);
            if (arr[i] > (-4) && arr[i] < 4) {
                k++;
            }
        }

        return k;
    }

Die Bedingung des zweiten ifs sorgt dafür, dass im Fall von i >= arr.length einfach 0 zurückgegeben wird. Das könnte man auch zu Beginn abfangen und so erhält man

    public static int apply(int[] arr, int i) {
        if (i < 0 || i >= arr.length) {
            return 0;
        }

        int k = apply(arr, i-1);
        if (arr[i]>(-4) && arr[i]<4) {
            k++;
        }

        return k;
    }

Das erste if entspricht dann auch genau der Anforderung der Aufgabenstellung: "Für alle i, die außerhalb des Bereichs 0<=i<arr.length liegen, soll die Methode apply den Wert 0 zurückgeben."

Das nur nebenbei, Dein Code ist ja nicht falsch.

Was mir in der Aufgabenstellung noch fehlt ist, mit welchem i die Methode apply später aufgerufen werden soll: mit 0 oder mit arr.length-1? Falls die Methode mit 0 augerufen werden soll, musst Du natürlich den rekursiven Aufruf anpassen, denn dann würde ja von unten nach oben gezählt.