Rekursion

[El Hadji]

Servus Communtiy,
Ich habe nach wie vor ziemliche Schwierigkeiten mir Rekursion vorzustellen. Ich habe hier eines der leichtesten Rekursionsbeispiele inklusive Code ich wäre euch sehr dankbar wenn ihr mir hiermit näher bringen könnt was Rekursion genau macht.

Beispiel ist einfach ein Hanoi-Spiel, 3 Stäbe, auf dem 1 Stab sind n Scheiben der Größe nach geordnet und man muss sie alle auf den 3ten Stab bringen.

    public static ArrayList<String> getHanoiSequence(int n)
    {
        bewegungen = new ArrayList<String>();
        String stabA = "A";
        String stabB = "B";
        String stabC = "C";
        hanoi(stabA,stabB,stabC,n);
        return bewegungen;
    }
   
    // auf Stab A liegen die n kleinsten Scheiben
   
    public static void hanoi(String stabA,String stabB,String stabC,int n)
    {
        if(n == 0) return;
        {
           
            hanoi(stabA,stabC,stabB,n-1);
            bewegungen.add(stabA+stabC);
            hanoi(stabB,stabA,stabC,n-1);
        }
    }
      
}

Nur verstehe ich nicht ganz wie in der Rekursion ein Methodenaufruf funktioniert. Natürlich gibt es den besten Fall und n ist gleich 0 also die Abbruchbedingungen. Aber danach rufe ich jedes Mal wieder die Methode auf und würde ja nie zubewegungen.add kommen oder wie läuft das ab.

mfg El Hadji

 

[Nuiton]

Ich finde nicht dass die Tuerme von Hanoi ein sehr empfehlendes Beispiel zum verstehen der Rekursion dient. Ein leichteres Beispiel waere z.B. Fakultaeten, exponentielle Funktionen (bzw. Math.pow()), oder Fibonacci.

Meine Frage ist: Was bringt dir das "stabA" und "stabB" einem String zu casten, und es schliesslich in eine ArrayList einzufuegen? Was hast du vor?

 

[El Hadji]

Ich habe nur das Rekursionbeispiel zur Verfügung und will es dadurch etwas besser verstehen für die nächsten. Die ArrayList soll einfach die Bewegungen ausgeben "AB" wenn eine Scheibe von Stab A auf Stab B geschoben wird

 

[mrBrown]

Der Code ist dir so vorgegeben? Das ist das denkbar schlechteste Beispiel, ich hab ehrlich gesagt nicht mal Ahnung, was da passieren soll, das sieht eher falsch als richtig aus und hat auch nicht wirklich viel mit Türme von Hanoi zu tun?

Besser verstehen wirst du es damit kaum, eher mit den schon genannten Beispielen wie Fibonacci...

 

[El Hadji]

So, wir haben ein Beispiel in der Übung durchgemacht und das war genau dieses hier, jetzt versuch ich die anderen Beispiele zu lösen. Aber zuerst will ich mal verstehen was wir hier gemacht haben

 

[mrBrown]

Das Beispiel ist einfach völliger Unsinn, wie es da oben steht, das hat auch mit der Beschreibung "alle auf den 3ten Stab bringen" nichts zu tun, es werden einfach nur immer zwei getauscht.

Dann die Liste Bewegungen, da werden A und C hinzugefügt, soll ja heißen, A und C werden getauscht, die werden aber nie getauscht, es wird B mit C und B mit A getauscht.

Und von den beiden Vertauschungen landet nur eine in der Liste, die Hälfte alle Bewegungen verschwindet also im Nirvana.


Rekursion kann man für Türme von Hanoi durchaus nutzen, aber dann nicht so umgesetzt.


Zu deinem Verständnis-Problem:

Nur verstehe ich nicht ganz wie in der Rekursion ein Methodenaufruf funktioniert. Natürlich gibt es den besten Fall und n ist gleich 0 also die Abbruchbedingungen. Aber danach rufe ich jedes Mal wieder die Methode auf und würde ja nie zubewegungen.add kommen oder wie läuft das ab.

Der erste Aufruf von hanoi(stabA,stabC,stabB,n-1); returned ja irgendwann (durch die Abbruchbedingung), dann wird bewegung.add(...); ausgeführt, und dann das zweite hanoi(...);, und dann returned das aktuelle hanoi.
Und eben dieses Schema lässt sich ohne das ganze Sinnlose drumherum dieses Hanois leichter verstehen, zB an Fibonacci oä.

Ist das 'ne Übung an 'ner Uni gewesen?

 

[Meniskusschaden]

Das Programm funktioniert schon korrekt. Die Benennungen sind aber nicht gut verständlich. Vielleicht erkennt man es mit folgender Kommentierung etwas besser:

        hanoi(stabA, stabC, stabB, n - 1); // Bewege oberste n-1 Scheiben von A nach B
        bewegungen.add(stabA + stabC);     // Bewege oberste Scheibe von A nach C
        hanoi(stabB, stabA, stabC, n - 1); // Bewege oberste n-1 Scheiben von B nach C

Für n=3 bekommt man folgendes Ergebnis:

[AC, AB, CB, AC, BA, BC, AC]

 

[mrBrown]

Das funktioniert wirklich? Ich hätte es mal ausprobieren sollen...
Das ist die unverständlichste Implementierung davon die ich je gesehen hab...

 

[Meniskusschaden]

Habe es getestet und das Ergebnis mit einem physikalischen Spiel aus Holz überprüft. Intuitiv verständlich ist die Implementierung wirklich nicht.

 

[El Hadji]

Ja ist eine Übung auf der Uni. Ok ich habe ja eben nur nicht verstanden wann bewegungen.add ausgeführt wird und wann nicht

 

[Meniskusschaden]

Du kannst dir ja mal zwischendurch etwas ausgeben lassen. Dadurch wird es vielleicht anschaulicher. Dieses Beispiel

public class Hanoi {
    private static final int N = 3;
    private static ArrayList<String> bewegungen;

    public static void main(String[] args) {
        getHanoiSequence(N);
        System.out.println(bewegungen);
    }

    public static ArrayList<String> getHanoiSequence(int n) {
        bewegungen = new ArrayList<String>();
        String stabA = "A";
        String stabB = "B";
        String stabC = "C";
        hanoi(stabA, stabB, stabC, n);
        return bewegungen;
    }

    public static void hanoi(String stabA, String stabB, String stabC, int n) {
        print(n, ">" + stabA + stabB + stabC);
        if (n == 0) {
            print(n, "<" + stabA + stabB + stabC);
            return;
        }

        hanoi(stabA, stabC, stabB, n - 1);
        print(n, "move " + stabA + "-" + stabC);
        bewegungen.add(stabA + stabC);
        hanoi(stabB, stabA, stabC, n - 1);
        print(n, "<" + stabA + stabB + stabC);
    }

    public static void print(int n, String s) {
        for (int i = 0; i < N - n; i++) {
            System.out.print(" ");
        }
        System.out.println(s);
    }
}

erzeugt folgendes Ergebnis:

>ABC
>ACB
  >ABC
   >ACB
   <ACB
  move A-C
   >BAC
   <BAC
  <ABC
move A-B
  >CAB
   >CBA
   <CBA
  move C-B
   >ACB
   <ACB
  <CAB
<ACB
move A-C
>BAC
  >BCA
   >BAC
   <BAC
  move B-A
   >CBA
   <CBA
  <BCA
move B-C
  >ABC
   >ACB
   <ACB
  move A-C
   >BAC
   <BAC
  <ABC
<BAC
<ABC
[AC, AB, CB, AC, BA, BC, AC]

EDIT: Beim Einfügen wurden offenbar ein paar Einrückungen verfälscht. Am besten ruft man es selbst auf.