Rekursion

[Noob1234_1234]

Ich habe seit einigen Monaten mit dem Lernen von Java anfangen auf Hobby- und Spasbasis. Vor kurzem bin ich aufs Themenfeld Rekursion gestoßen und hab mich darin eingelesen. Einige Basic Aufgaben wie Fakultät, Potenzrechnen, Multiplikation hab ich auch alleine geschafft. Deswegen hab ich ich im Netz weitergesucht und bin auf die Aufgabe ( siehe Bild) gestoßen und ich kann wirklich nichts aber wirklich gar nichts damit anfangen. Es ist von einer Tabelle die Rede, wo man seine Einträge speichern kann, damit sie sich nicht doppeln (Collections?), aber kann mir bitte wer input geben. Diese Aufgabe sollte eigentlich nicht schwer sein, aner ich komm zu nichts

 

[kneitzel]

Tabelle kann ein einfaches Array sein. Wenn Du n Werte berechnen willst, dann brauchst Du ein Array entsprechender Größe.
Dabei ist noch zu beachten: Da wir mit dem 0ten Wert anfangen, braucht man zur Speicherung des Wertes Ln ein Array mit eine Größe von mindestens n+1. (Ein Array der Größe x hat die Indices von 0 bis x-1!)

Und Du brauchst einen Wert, der Signalisiert, dass etwas noch nicht berechnet wurde. Das kann z.B. ein Wert sein, der nicht vorkommen kann (-1, 0, Integer.MIN_VALUE, ...) oder man nutz einen Typ, der null erlaubt (also z.B. Array von Integer statt int).
Es gibt auch noch weitere Möglichkeiten aber die zwei Möglichkeiten reichen evtl. schon aus ....

Reichen die Informationen, um weiter zu machen?

 

[Noob1234_1234]

Tabelle kann ein einfaches Array sein. Wenn Du n Werte berechnen willst, dann brauchst Du ein Array entsprechender Größe.
Dabei ist noch zu beachten: Da wir mit dem 0ten Wert anfangen, braucht man zur Speicherung des Wertes Ln ein Array mit eine Größe von mindestens n+1. (Ein Array der Größe x hat die Indices von 0 bis x-1!)

Und Du brauchst einen Wert, der Signalisiert, dass etwas noch nicht berechnet wurde. Das kann z.B. ein Wert sein, der nicht vorkommen kann (-1, 0, Integer.MIN_VALUE, ...) oder man nutz einen Typ, der null erlaubt (also z.B. Array von Integer statt int).
Es gibt auch noch weitere Möglichkeiten aber die zwei Möglichkeiten reichen evtl. schon aus ....

Reichen die Informationen, um weiter zu machen?

Danke erstmal für den Hilfsansatz aber ich werd nicht schlau aus dieser Aufgabe. Ich hab es jetzt anders versucht. In der Aufgabe steht ja irgendwas von Fibonnaci nummern und Pell folgen. Beides sagt mir was und die beiden Sachen als Methode umzusetzen war auch wirklich kein Problem.

public class LukasFolgen {

    public static void main(String[] args) {
        LukasFolgen l = new LukasFolgen();

        l.printAllFib(7);
        System.out.println(" Jetzt pell");
        l.printAllPell(7);
    }

    public static int fib(int a) {
        if (a == 0)
            return 0;
        if (a == 1)
            return 1;

        else
            return fib(a - 1) + fib(a - 2);
    }

    public void printAllFib(int a) {
        for (int i = 0; i < a; i++) {
            System.out.println(fib(i));
        }
    }

    public static int pell(int n) {
        if (n <= 2) {
            return n;
        }
        return 2 * pell(n - 1) + pell(n - 2);
    }

    public void printAllPell(int a) {
        for (int i = 0; i < a; i++) {
            System.out.println(pell(i));
        }
    }
}

Ausgabe:
0
1
1
2
3
5
8
Jetzt pell
0
1
2
5
12
29
70

Aber wie verallgemeinere ich das bitte auf eine Allgemeine Formel, die dann automatisch bei den jeweiligen Kommandozeilenargumenten diese jeweiligen Folgen bestimmt. Außerdem merk ich jetzt, was du meintest mit n+1, mir fehlt im Vergleich zur Aufgabe eine Zeile bei Fibonnaci (die 13). Kannst du mir vielleicht doch noch helfen

 

[mihe7]

Wenn ich mich nicht verschaut habe, erhältst Du den primitiv-rekursiven Ansatz der Lukasfolge doch einfach aus der fib-Methode, indem Du p und q einführst:

    public static int lukas(int a, int p, int q) {
        if (a == 0)
            return 0;
        if (a == 1)
            return 1;

        else
            return p*fib(a - 1) - q*fib(a - 2);
    }

EDIT: das else am Ende kannst Du Dir übrigens sparen.

 

[Noob1234_1234]

Wenn ich mich nicht verschaut habe, erhältst Du den primitiv-rekursiven Ansatz der Lukasfolge doch einfach aus der fib-Methode, indem Du p und q einführst:

    public static int lukas(int a, int p, int q) {
        if (a == 0)
            return 0;
        if (a == 1)
            return 1;

        else
            return p*fib(a - 1) - q*fib(a - 2);
    }

EDIT: das else am Ende kannst Du Dir übrigens sparen.

Oha gerade, wo du es geschrieben hast, hab ich es ausprobiert gehabt und ja es klappt mehr oder weniger, aber so einfach ist die Aufgabe, dann doch nicht.
1. Mich verwirrt in der Aufgabenstellung die Variablen i und n; wo liegt denn der unterschied zwischen den beiden erfragen?
2. Ich muss ja jetzt alle Berechnungen irgendwo speichern und sicherstellen, dass jedes Element nur 1 Mal gespeichert ist. Hier wurde dafür eine Arraylist empfohlen, aber in einer ArrayList kann man ja Duplikate haben. Ich meine gelesen zu haben, dass es im Collection Framework bzw in java.util bessere Datenstrukturen gibt, die von Vornherein verhindern, dass es Duplikate gibt oder irre ich mich da ?

 

[Noob1234_1234]

Darf ich euch etwas fragen? Ich bin ja eh noch ein Amateur, was Java angeht, aber wenn ihr die Aufgabe so lest, findet ihr sie trivial? Weil da, wo ich sie gefunden habe, gab es mehrere solcher Aufgaben. 1 Block solcher Aufgaben ist 20 Punkte und diese hier gibt davon nur 2 punkte. Dementsprechend folgere ich, dass diese Aufgabe trivial sein müsste oder ?

 

[mihe7]

Mich verwirrt in der Aufgabenstellung die Variablen i und n; wo liegt denn der unterschied zwischen den beiden erfragen?

Naja, das sind normale mathematische Formulierungen: i kennzeichnet das i-te Folgenglied und n kennzeichnet die Anzahl der zu berechnenden Folgenglieder. Dein Parameter a von printAllFib entspricht also dem n, und der Parameter a von fib entspricht dem i

muss ja jetzt alle Berechnungen irgendwo speichern und sicherstellen, dass jedes Element nur 1 Mal gespeichert ist. Hier wurde dafür eine Arraylist empfohlen

Hier wurde ein Array empfohlen, keine ArrayList. Wenn Du ein Array der Größe n nimmst, kannst Du die i-te Lukaszahl ja an der i-ten Stelle des Arrays speichern.

 

[httpdigest]

Du brauchst weder ein Array noch eine Liste noch irgend eine andere Klasse aus java.util, wenn du es effizient implementieren möchtest. Zwei "Laufvariablen" in deiner rekursiven Methode reichen aus.

 

[Noob1234_1234]

Wenn ich mich nicht verschaut habe, erhältst Du den primitiv-rekursiven Ansatz der Lukasfolge doch einfach aus der fib-Methode, indem Du p und q einführst:

    public static int lukas(int a, int p, int q) {
        if (a == 0)
            return 0;
        if (a == 1)
            return 1;

        else
            return p*fib(a - 1) - q*fib(a - 2);
    }

EDIT: das else am Ende kannst Du Dir übrigens sparen.

Der Ansatz funktioniert doch nicht so einfach wie da. Für die Fibonnaci nummern funktioniert zwar alles, aber wenn ich die Pellnummern will, kommen falsche Zahlen. Uff was nun

 

[kneitzel]

Also wenn man etwas sehr viel macht, dann wird das für einen relativ einfach. Es ist halt wie so vieles im Leben vor allem eins: Praxis und Erfahrung! Und ja - die Anforderung dieser Aufgabe ist nicht besonders hoch - aber wenn man gerade erst die Anfänge hat, dann ist es natürlich erst einmal schwer und kaum zu lösen.

Daher ist es wichtig, dass man versucht, möglichst viel Erfahrung mit solchen Aufgabenstellungen zu sammeln.

Und nun schauen wir einmal an, wie man noch den offenen Punkt mit der Lookup Tabelle hin bekommen kann:

Also so eine Tabelle kann man als Array nehmen. Also brauchst Du so ein Array. Das bedeutet: Die Methodensignatur verändert sich:
public static int lukas(int a, int p, int q, Integer[] werte) {

Beim ersten Aufruf ist werte null. Also erstellen wir nun einfach ein Array mit Größe n+1.

Also müssen wir als erstes prüfen: Ist die Tabelle null? Wenn ja: dann erstellen wir eine neue Tabelle in der Größe:

if (werte == null) {
    werte = new Integer[a];
}

Wenn werte nicht null ist, dann können wir schauen, ob wir schon einen Wert gespeichert haben. Dazu schauen wir, ob der Wert an der gesuchten Stelle a != null ist. if (werte[a] != null)
Wenn dies der Fall ist, dann haben wir einen Wert und wir können direkt diesen Wert zurück geben.

Und nun kann der normale Rest der Methode kommen mit der Berechnung wie es in #4 zu sehen ist. Was wir aber ändern müssen:
Aus dem return Berechnung machen wir ein wert[a]=Berechnung; return wert[a]; ==> Wir müssen den Wert ja speichern, damit der Wert nur einmal berechnet wird. Und in den Rekursiven Aufrufen muss natürlich das Array auch mit übergeben werden.

 

[Noob1234_1234]

Du brauchst weder ein Array noch eine Liste noch irgend eine andere Klasse aus java.util, wenn du es effizient implementieren möchtest. Zwei "Laufvariablen" in deiner rekursiven Methode reichen aus.

So habe ich es gerade auch und bei Fibonnaci krieg ich die gewünschte Ausgabe, aber ich will es wie in der Aufgabe implementieren, dass jedes Folgeglied der entsprechenden Zahlen irgendwo gespeichert ist

 

[kneitzel]

Du brauchst weder ein Array noch eine Liste noch irgend eine andere Klasse aus java.util, wenn du es effizient implementieren möchtest. Zwei "Laufvariablen" in deiner rekursiven Methode reichen aus.

Die Aufgabe verlangt aber explizit eine Lookup-Tabelle. Daher sind Optimierungen schön, aber wohl nicht Zielführung wenn es um die Lösung der Aufgabe geht.

 

[httpdigest]

Okay... die Lookup Tabelle (z.B. das int[] Array) braucht nur 2 Einträge. Dieses Array kann man dann gerne durch die rekursiven Aufrufe schubsen.
EDIT: Außerdem wird es auf solch eine "Optimierung"/Lösung hinauslaufen müssen, da du wohl kaum (2^31)-1 Einträge (= 8 Gigabytes) wie laut der Aufgabenstellung als Bereich für `n` gefordert, im Array halten möchtest.
EDIT2: Ich muss meine Anmerkungen bezüglich des nötigen `n` Elemente großen Array allerdings damit relativieren, als dass man sowieso lange vor erreichen von `n` in einen StackOverflowError kommt... da die JVM keine tail-recursion Optimierung unterstützt und somit der notwendige Speicher für `n` schon alleine durch die Stackgröße beschränkt wird.

 

[Noob1234_1234]

Die lookUp Tabelle ist noch unwichtig. Erstmal sollte die Formel klappen xD

public class LukasFolgen {

    public static void main(String[] args) {

        if (args.length == 3) {
            try {
                printlukas(Integer.parseInt(args[0]), Integer.parseInt(args[1]), Integer.parseInt(args[2]));
            } catch (Exception e) {
                System.out.println("Error " + e.getMessage());
            }
        } else {
            System.out.println("Fehler");
        }
    }

    public static int fib(int a) {
        if (a == 0)
            return 0;
        if (a == 1)
            return 1;

        else
            return fib(a - 1) + fib(a - 2);
    }

    public void printAllFib(int a) {
        for (int i = 0; i < a; i++) {
            System.out.println(fib(i));
        }
    }

    public static int lukas(int a, int p, int q) throws Exception {
        if (a == 0)
            return 0;
        if (a == 1)
            return 1;

        return p * fib(a - 1) - q * fib(a - 2);
    }

    public static void printlukas(int a, int p, int q) throws Exception {
        for (int i = 0; i < a + 1; i++) {
            System.out.println(lukas(i, p, q));
        }
    }
}

Das habe ich bisher. Fehlerbehandlung ist auch schon drinnen, aber die allgemeine Folge klappt eben nur für Fibonnaci und das ist das Problem. Ist der Sinn von Rekursion nicht eh eigentlich, dass sich die Methode selbst aufruft und nicht eine andere Methode ( wie hier fib())?

EDIT : Ich hab die allgemeine Formel. War doch einfacher als gedacht. Aber das mit der i Variable check immernoch net und ich versuche das mit dem Array zu verstehen

 

[Noob1234_1234]

Die lookUp Tabelle ist noch unwichtig. Erstmal sollte die Formel klappen xD

public class LukasFolgen {

    public static void main(String[] args) {

        if (args.length == 3) {
            try {
                printlukas(Integer.parseInt(args[0]), Integer.parseInt(args[1]), Integer.parseInt(args[2]));
            } catch (Exception e) {
                System.out.println("Error " + e.getMessage());
            }
        } else {
            System.out.println("Fehler");
        }
    }

    public static int fib(int a) {
        if (a == 0)
            return 0;
        if (a == 1)
            return 1;

        else
            return fib(a - 1) + fib(a - 2);
    }

    public void printAllFib(int a) {
        for (int i = 0; i < a; i++) {
            System.out.println(fib(i));
        }
    }

    public static int lukas(int a, int p, int q) throws Exception {
        if (a == 0)
            return 0;
        if (a == 1)
            return 1;

        return p * fib(a - 1) - q * fib(a - 2);
    }

    public static void printlukas(int a, int p, int q) throws Exception {
        for (int i = 0; i < a + 1; i++) {
            System.out.println(lukas(i, p, q));
        }
    }
}

Das habe ich bisher. Fehlerbehandlung ist auch schon drinnen, aber die allgemeine Folge klappt eben nur für Fibonnaci und das ist das Problem. Ist der Sinn von Rekursion nicht eh eigentlich, dass sich die Methode selbst aufruft und nicht eine andere Methode ( wie hier fib())?

Und kann es sein, dass ich noch einen Denkfehler habe ? Diese Formel soll doch, dass i te Folgeglied berechnen und n hingegen wird der Methode mitgeben und die beiden müssen verglichen werden ? Aber wie setz ich das um bzw wie mach ich ersichtlich, dass das i-te Glied berechnet wird ?

 

[Noob1234_1234]

Wieso sollte ich nicht einfach einen TreeSet benutzen? Der steckt im util Paket und hört sich doch genau nach dem an, was ich brauche oder ? Keine duplikate und sortiert

 

[httpdigest]

Okay, hier mal die Lösungsschritte für eine rekursive Methode mit einem zweielementigen "Lookup":
Fangen wir mal mit einer korrekten aber naiven rekursiven Definition ohne Lookup an:

static int lukas(int n, int p, int q) {
  if (n == 0)
    return 0;
  if (n == 1)
    return 1;
  return p * lukas(n - 1, p, q) - q * lukas(n - 2, p, q);
}

Was wir hier sehen ist, dass die Berechnung des `i`-ten Elementes der Folge von dem `i-1`-ten und dem `i-2`-ten Element abhängt. Das heißt, zu jedem Zeitpunkt in der Berechnung der Folge benötigen wir nur Zugriff auf die zwei vorherigen/letzten Berechnungsergebnisse. Hierfür können wir uns schonmal zwei Parameter reservieren und diese erstmal für die beiden rekursiven Aufrufe einsetzen (nennen wir sie `nMinus1` und `nMinus2` und sie sollen das Ergebnis der lukas() Methode für `n-1` und `n-2` repräsentieren):

static int lukas(int n, int p, int q, int nMinus1, int nMinus2) {
  return p * nMinus1 - q * nMinus2;
}

Das Problem jetzt ist, dass wir natürlich keine rekursive Methode mehr haben. Aber konstruieren wir uns ersteinmal eine Einstiegsmethode, die die geforderten drei Parameter bekommt und die unsere rekursive Methode aufruft. Überlegen wir uns, was die ersten beiden Elemente der Reihe sind, nämlich 0 und 1, und verwenden dies als unsere ersten "Lookup"-Werte:

static int lukas(int n, int p, int q) {
  return lukas(n, p, q, 1, 0);
}

Unsere nicht-rekursive Methode kann also das dritte Element der Reihe aus den vorgegebenen ersten beiden Elementen berechnen. Wie geht es jetzt aber weiter?
Um unsere Methode wieder rekursiv zu machen, so dass sie eben auch andere Elemente der Reihe als nur das dritte berechnen kann, überlegen wir, dass ja für jeden weiteren rekursiven Aufruf sich die zwei vorherigen Berechnungsergebnisse aus dem aktuellen Berechnungsergebnis und aus dem direkt letzten Ergebnis ergeben. Das direkt letzte Ergebnis ist in `nMinus1`. Wir verwenden also das `nMinus1` als das neue `nMinus2` für den nächsten rekursiven Aufruf und berechnen das `nMinus1` für den neuen rekursiven Aufruf gemäß der Formel:

static int lukas(int n, int p, int q, int nMinus1, int nMinus2) {
  return lukas(n, p, q, p * nMinus1 - q * nMinus2, nMinus1);
}

Was ist jetzt aber mit einer Abbruchbedingung? Wir müssen ja auch irgendwann aufhören. Da wir `n` sonst in der Berechnung nicht benötigen, können wir es einfach dekrementieren und prüfen, ob es noch größer als 0 ist.
Falls nicht, liefern wir `nMinus2`:

static int lukas(int n, int p, int q, int nMinus1, int nMinus2) {
  return n <= 0 ? nMinus2 : lukas(n - 1, p, q, p * nMinus1 - q * nMinus2, nMinus1);
}

Jetzt müssen wir nur noch alle Elemente von 0 bis einschließlich `n` ausgeben. Das können wir mit einer Schleife tun:

for (int i = 0; i <= n; i++) {
  System.out.println(lukas(i, 1, -1));
}

Um weitere Berechnungen (oder auch lookups) zu vermeiden, könnte man aber die Ausgabe des `i`-ten Elementes der Reihe direkt in die rekursive Methode einbauen, so dass man sich die Schleife spart:

static void lukas(int n, int p, int q) {
  lukas(n, p, q, 1, 0);
}
static void lukas(int n, int p, int q, int nMinus1, int nMinus2) {
  System.out.println(nMinus2);
  if (n > 0) {
    lukas(n - 1, p, q, p * nMinus1 - q * nMinus2, nMinus1);
  }
}
public static void main(String[] args) {
  lukas(7, 1, -1);
}

 

[lennero]

Wieso sollte ich nicht einfach einen TreeSet benutzen? Der steckt im util Paket und hört sich doch genau nach dem an, was ich brauche oder ? Keine duplikate und sortiert

Weil du beim Taubenschießen auch keinen Raketenwerfer benutzt

 

[mihe7]

Der Ansatz funktioniert doch nicht so einfach wie da. Für die Fibonnaci nummern funktioniert zwar alles, aber wenn ich die Pellnummern will, kommen falsche Zahlen. Uff was nun

Sorry, in meinem Code hatte sich ein Copy & Paste-Fehler eingeschlichen Am Ende habe ich vergessen, den Aufruf von fib() durch den Aufruf von lukas() zu ersetzen.