Rekursion mit Feldern - ich raffe es nicht :(

[der-andyman]

Hi Leute, ich werde am Freitag ein Testat schreiben über Rekursion mit Feldern, aber ich kann das einfach nicht.
Also, unter anderem ist das eine Beispielaufgabe, die auf das Testat vorbereitet:
Bestimmung des Maximums

Entwickeln Sie eine rekursive Methode int maximum( int[] arr, int i ), die für ein Feld arr das Maximum im
Bereich von arr[0] bis arr mit 0<=i<arr.length bestimmt und zurückgibt.
Verzichten Sie bei der Lösung der Aufgabe völlig auf die Benutzung von for- oder while-Schleifen!

Mein Gedanke dazu war folgender Code:

public static int maximum(int[] arr, int i)
    {
        if (i >= arr.length)
        {
           return 0;
        }
        else
        {
            if (i == 0)
            {
               return arr[0];
            }
            else 
            {
                if (arr[i] > maximum(arr, i-1)  )
                { 
                    return arr[i];
                }
                else 
                {
                    return arr[i-1];
                }
            }
        }
    }

Warum springt der Funke bei mir nicht über?? Normale rekursionen kann ich ja auch

 

[der-andyman]

Ok, also dieses Programm habe ich nun doch geschrieben, keine Ahnung warum, aber diese Lösung fiel mir gerade einfach ein:

public static int maximum(int[] arr, int i)
    {
        if (i >= arr.length)
        {
           return 0;
        }
        else
        {
            if (i == 0)
            {
               return arr[0];
            }
            else 
            {
                if (arr[i] > maximum(arr, i-1)  )
                { 
                    return arr[i];
                }
                else 
                {
                    return maximum (arr, i-1);
                }
            }
        }
    }

Jetzt habe ich ein anderes Problem:
Warum funktioniert das, bzw. wie funkzt das??

 

[rme]

Hm. Zeilen 15 - 17: "Wenn das aktuelle Element größer ist, als das Maximum der Elemente davor, gib das aktuelle Element als Maximum aus (klingt OK). Ansonsten gib das Element vor dem aktuellen als Maximum aus (klingt nicht OK)". Siehst du nun das Problem und die Lösung?

Edit: Bezogen auf 1. Post

 

[der-andyman]

Naja, mein zweiter Post funktioniert zwar, aber ich weiß noch immer nicht sooo ganz, warum :S


aber gut, hauptsache es geht, ich mache mich mal an die anderen Aufgaben, eine weitere habe ich noch gelöst:

Prüfen einer Sortierung

Entwickeln Sie eine rekursive Methode boolean isSorted( int[] arr, int i ), die für ein Feld arr im Bereich
von arr[0] bis arr mit 0<=i<arr.length feststellt, ob das Feld aufsteigend sortiert ist, also für alle k mit
0<=k<i gilt: arr[k]<=arr[k+1]. Ist das der Fall, soll true zurückgegeben werden, sonst false.
Verzichten Sie bei der Lösung der Aufgabe völlig auf die Benutzung von for- oder while-Schleifen!

public static boolean isSorted(int[] arr, int i)
    {
        if (i >= arr.length)
        {
           return false;
        }
        else
        {
            if (i == 0)
            {
               return true;
            }
            else 
            {
                if (arr[i] >= arr[i-1])
                { 
                    return isSorted (arr, i-1);
                }
                else 
                {
                    return false;
                }
            }
        }
    }

 

[der-andyman]

Sorry, dass ich wieder auf meinen eigenen Beitrag antworte!

Also die letzte Aufgabe bereitet mir sehr große Kopfschmerzen:

Palindrome
Ein Palindrom ist eine Zeichenfolge, die vorwärts und rückwärts identisch gelesen werden kann.
Entwickeln Sie eine rekursive Methode boolean palindromCheck( char[] arr, int i ), die durch den Aufruf
palindromCheck( a, 0 ) für ein Feld a von Zeichen ermittelt, ob die Folge der Zeichen in a ein Palindrom bildet.
Der Parameter i soll dazu benutzt werden, den betrachteten Bereich des Feldes arr einzuschränken. Die Methode soll
einen Wert des Typs boolean zurückgeben.
Verzichten Sie bei der Lösung der Aufgabe völlig auf die Benutzung von for- oder while-Schleifen!

Und auch finde ich hier keinen Ansatz, denn es heißt ja "wenn man palindrom (a,0) eingibt, soll er das ganze Array durchlaufen, bei palindromCheck(a, x) das Array bis zur Stelle x begrenzen" leider weiß ich dann überhaupt nicht, wie ich mit dem palindrom (a,0) weiterarbeiten soll, wo doch das i = 0 ist.

 

[Alph0r]

Ich weiß nicht, ob ich deine Frage richtig verstehe. Dein Problem ist im Moment einfach nur, wie du bei i = 0 das gesamte Array durchlaufen sollst? Den Sonderfall kann man am einfachsten mit einem if else lösen.

Falls i = 0, gehe bis array.length, ansonsten gehe bis i.

Ich würde außerdem wahrscheinlich eine private rekursive Hilfsfunktion benutzen.

 

[Alph0r]

Ok, also dieses Programm habe ich nun doch geschrieben, keine Ahnung warum, aber diese Lösung fiel mir gerade einfach ein:

public static int maximum(int[] arr, int i)
    {
        if (i >= arr.length)
        {
           return 0;
        }
        else
        {
            if (i == 0)
            {
               return arr[0];
            }
            else 
            {
                if (arr[i] > maximum(arr, i-1)  )
                { 
                    return arr[i];
                }
                else 
                {
                    return maximum (arr, i-1);
                }
            }
        }
    }

Jetzt habe ich ein anderes Problem:
Warum funktioniert das, bzw. wie funkzt das??

Gibt 2 Möglichkeiten darüber Nachzudenken, entweder du gehst es vom Rekursionasnker aufwärts in Gedanken Schritt für Schritt, oder du denkst etwas abstrakter, mit Rekursionsinvarianten.

Gehen wir es mal Schritt für Schritt durch. Nehmen wir zB an i = 1.

Er geht in

 if (arr[i] > maximum(arr, i-1)  )
                { 
                    return arr[i];
                }

und guckt was arr ist, verleicht das mit arr[i - 1] was arr[0] ist. Bei i = 0 ist der Abbruch, d.h. er kann jetzt direkt was returnen und geht nciht weiter in eine Rekursion.

Das ergebnis von maximum(arr, i-1) ist jetzt also arr[0], das wird mit arr[1] verglichen und der größere Wert wird zurückgegeben.

Wenn i größer wäre, gäbe es mehr Schritte. Wenn i = 2 wäre, würde er in

 if (arr[i] > maximum(arr, i-1)  )
                { 
                    return arr[i];
                }

und würde die gleichen Schritte durchgehen, was wir vorhin für maximum(arr, 1) als Endergebniss hatten, wäre jetzt nur das Zwischenergebnis, was auf höchster ebene nochmal mit arr[2] verglichen würde und das größere Element würde zurückgegeben werde.

Das gleiche würde dann für höhere i gelten.

Du kannst auch mit Invarianten argumentieren Für i = 0, gibt es nur ein Element, dieses element ist automatisch das Maximum. Bei jedem Rekursionsschritt wird das Maximum von arr und arr[0] bis arr[i-1] zurückgegeben. Also wird am ende das Maximum des arrays von 0 bis zum übergebenen i zurückgegeben.