Rekursion Wurzel

[baker333]

Guten Abend,

erstmal vielen Dank für all die Hilfe in den verschiedenen Themen hier.
Als nächstes soll ich eine rekursive Methode für das folgende Nährungsverfahren erstellen:

Die n-te Näherung der Quadratwurzel von a ist wie folgt definiert:

x_(n+1) = (x_n + (a/ x_n))/2

Wenn ich mich jetzt richtig erinnere, dann handelt es sich um das Heron-Verfahren.
Bei bspw. rekursiven Methoden zu den Fibonacci Zahlen oder der Fakultät hatte ich keine Probleme. Allerdings weiß ich nun wirklich nicht, wie ich den Basisfall definieren soll.
Die Methode soll wie folgt aussehen:

public double berechneWurzel(double a, int n){
}

 

[JCODA]

Du musst dir offensichtlich Gedanken um x_0 machen, denn für x_n benötigst du x_(n-1). Und dementsprechend um z.B. x_5 aufzurechnen musst du x_4,x_3,x_2,x_1 berechnen und für x_1 brauchst du eben x_0.
Ein Blick ins Wiki hilft:

Der Startwert

der Iteration kann, solange er nicht gleich Null ist, beliebig festgesetzt werden, die Iteration konvergiert immer. Zu beachten ist, dass bei negativen Startwerten die Iteration gegen die negative Quadratwurzel konvergiert. Eine qualifizierte Schätzung für den Startwert erhält man aus der Taylorreihen-Entwicklung der binomischen Reihe um 1, deren zwei erste Glieder diese Gleichung liefern:

 

[baker333]

Dann wäre x_o = 1

 

[JCODA]

Das kannst du so machen ... aber bedenke dass bei x_0 nicht a=0 sondern n=0 ist ...

 

[baker333]

Ich bin überfordert. Es werden doch einzelne Nährungen addiert? Ähnlich wie bei dem rekursiven Fibonacci Algorithmus muss immer vorher n-1 berechnet werden, oder?

 

[JCODA]

Das stimmt, das n wird, zumindest laut deiner Methoden-Signatur, in jedem Schritt um eins reduziert. Das a bleibt allerdings konstant.

 

[baker333]

Gut, a ist natürlich konstant, weil daraus will ich ja die Wurzel ziehen. Wenn dann der Basisfall:

if (n==0){
     return 1;
}

dann muss ich danach mittels return die Methode wieder aufrufen?

 

[JCODA]

dann muss ich danach mittels return die Methode wieder aufrufen?

Ich denke du meinst das Richtige, die Ausdrucksweise ist allerdings nicht richtig.
Zeig doch einfach mal wie du jetzt weitermachen würdest

Zu deinem Basisfall: Ja der funktioniert. (Ist aber laut Wiki-Zitat oben nicht optimal, return (a+1)/2; wäre besser.)

 

[baker333]

Ich bin echt doof. In der Aufgabe steht der Basisfall:
x_0 = a

 

[JCODA]

Ich bin echt doof. In der Aufgabe steht der Basisfall:
x_0 = a

Ja, der funktioniert, laut Wiki-Artikel, auch.

 

[baker333]

publich double berechneWurzel (double a, int n){
//Basisfall definieren
       if (n==0){
            return a;
       else { 
       return (n+(a/n))/2 * berechneWurzel(a, n-1);
}

 

[httpdigest]

Wenn du für x_0 = a nimmst, wirst du feststellen, dass du noch eine Sonderbehandlung einführen musst für den Fall, dass a = 0 ist. Denn sqrt(0) = 0.
Bei x_0 = 1 oder x_0 = (a+1)/2 bräuchtest du diese nicht.

Bezüglich deines Codes oben: Nein. Hast du das mal selbst ausprobiert?
In der Formel `(x_n + a / x_n) / 2` ist `x_n` nicht `n`, sondern das Ergebnis der Näherung in Stufe `n`.

 

[baker333]

Wenn du für x_0 = a nimmst, wirst du feststellen, dass du noch eine Sonderbehandlung einführen musst für den Fall, dass a = 0 ist. Denn sqrt(0) = 0.
Bei x_0 = 1 oder x_0 = (a+1)/2 bräuchtest du diese nicht.

Bezüglich deines Codes oben: Nein. Hast du das mal selbst ausprobiert?

Die Sonderbehandlung brauche ich laut Aufgabenstellung nicht, aber ich weiß was Du meinst.

Wo genau liegt der Fehler im Code?

 

[httpdigest]

Wo genau liegt der Fehler im Code?

Sorry, hatte ich innerhalb der "5 Minuten unbemerkt editieren"-Zeit noch schnell in der obigen Antwort reingeschrieben.

 

[baker333]

Ah okay, das ist so ähnlich wie bei den Fibonacci Zahlen

 

[baker333]

Sorry, ich bin überfragt, ich weiß nicht wie ich das vorherige Ergebnis dort richtig einbringe, da in der Ausgangsformel ja X_n+1 steht, meine Methode allerdings auf n-1 ausgelegt ist.

 

[httpdigest]

Du kannst die Formel natürlich umformulieren:
`x_(n+1) = (x_n + a / x_n) / 2`
ist dasselbe wie:
`x_n = (x_(n-1) + a / x_(n-1)) / 2`

 

[baker333]

publich double berechneWurzel (double a, int n){
//Basisfall definieren
       if (n==0){
            return a;
       else {
       return (berechneWurzel(a, n-1) + a /berechneWurzel (a, n-1)) /2;

}

 

[baker333]

Sieht irgendwie komisch aus

 

[JCODA]

Das sieht schon Mal gut aus.
was könntest du noch tun, um nur einmal die Methode für n-1 aufrufen zu müssen?

 

[baker333]

Das ganze dynamisch machen und bereits berechnete Werte speichern?

 

[httpdigest]

Und jetzt noch die Sonderfälle a==0 -> 0 und a < 0 -> Double.NaN abdecken.

 

[baker333]

Und jetzt noch die Sonderfälle a==0 -> 0 und a < 0 -> Double.NaN abdecken.

Dagegen wehre ich mich in der Aufgabe steht, dass a immer positiv ist und n nicht-negativ ist

 

[httpdigest]

Von `n` rede ich ja auch garnicht.
Und, ob 0 eine positive Zahl ist, darüber lässt sich auch vorzüglich streiten.

 

[baker333]

gut, falls a==0 ist, dann return a;
sonst das ganze noch dynamisch machen?

 

[httpdigest]

Du brauchst hier keine dynamische Programmierung oder Memoization...
Schau mal, du hast vereinfacht gesehen genau diesen Fall (mit <+> als einen Stellvertreter für eine beliebige Operation):

return ziemlichKostspieligeMethode(n)
   <+> ziemlichKostspieligeMethode(n);

Du hast also zwei Aufrufe der exakt selben Methode mit den exakt selben Argumenten. Ja, wie würde man das denn jetzt ändern, dass du nur noch einmal `ziemlichKostspieligeMethode(n)` aufzurufen brauchst?

 

[baker333]

Ehrlich gesagt keine Ahnung, hatte den Fall noch nie. Ich muss doch zweimal auf die Methode mit n-1 zugreifen.

 

[httpdigest]

Ne, das glaub ich jetzt nicht. Darauf musst du jetzt kommen. Das kann doch nicht sein.
Mal eine komplett davon losgelöste Frage:

/**
 * Läuft sehr lange und berechnet für dasselbe `a` (Parameter) _IMMER_ dasselbe Ergebnis.
 */
public static double gaaanzLangeBerechnung(double a) {
  ...
}
public static double f() {
  return gaaanzLangeBerechnung(1) + gaaanzLangeBerechnung(1);
}

Bekomme es irgendwie hin, dass in f() die Methode gaaanzLangeBerechnung() nur noch einmal aufgerufen wird.

 

[JCODA]

Du musst nicht zweimal auf die Methode zugreifen, du musst nur einmal auf die Methode zugreifen ... und zweimal auf den Rückgabewert. Hilft das?

 

[baker333]

Ich komme mir gerade echt dumm vor Ich muss mal kurz überlegen wo ich mal wieder auf dem Schlauch stehe

 

[httpdigest]

Ein Dozent in meiner ehemaligen Uni würde jetzt sagen, dass das davon kommt, wenn man Studenten/Schüler zuerst mit imperativen Programmiersprachen (wo Methoden Seiteneffekte haben können) statt mit puren funktionalen Sprachen (in denen Ausdrücke referenzielle Integrität besitzen - und man gleiches mit gleichem ersetzen kann) bekannt macht.

 

[baker333]

Wie komme ich denn zweimal an den Rückgabewert? Hä?

 

[baker333]

Ich muss zu meiner Verteidigung sagen, dass das ein Kurs an der FernUni Hagen ist und ich mir das alles selber beibringe und an die Skripte gebunden bin. Im richtigen Leben bin ich Biochemiker.

 

[JCODA]

Du könntest die Methode ja einmal vor der Formel aufrufen ...

 

[httpdigest]

Japp, oder äquivalent: Stell dir vor, du hättest die eigentliche Formel `(x_n + a/x_n) / 2` in einer separaten/weiteren Methode ausgelagert, was vielleicht eine gute Idee ist, z.B. so:

private static double f(double a, double x_n) {
  return (x_n + a / x_n) / 2;
}

 

[baker333]

Sorry Leute, stehe auf dem Schlauch. Ich soll die Methode auslagern, um dann auf die ausgelagerte Methode zuzugreifen?

 

[httpdigest]

Ganz genau! Mit dem großen Unterschied: Wie oft würdest du dort dann deine `berechneWurzel` Methode rekursiv aufrufen, um das Ergebnis als Argument für den Methodenaufruf von f(...) mitzugeben?

 

[Xyz1]

Ein Dozent in meiner ehemaligen Uni würde jetzt sagen, dass das davon kommt, wenn man Studenten/Schüler zuerst mit imperativen Programmiersprachen (wo Methoden Seiteneffekte haben können) statt mit puren funktionalen Sprachen (in denen Ausdrücke referenzielle Integrität besitzen - und man gleiches mit gleichem ersetzen kann) bekannt macht

Aber man könnte entgegnen dass dieser Effekt "nur" bei partiellem Lernen der "imperativen Sprachen" einsetzen würde. Also sprich es geht "nur" um die "vollumfänglichen" Kenntnisse der Grundlagen.

 

[httpdigest]

Das Problem ist, dass es so etwas notwendiges wie Aktionen mit Nebeneffekten gibt, wie etwa auf der Konsole etwas ausgeben, einen HTTP-Request machen oder den Benutzer etwas fragen. Imperative Sprachen sind um die Idee herum entstanden, dass jede Aktion im Prinzip inhärent einen Nebeneffekt darstellt, bis herunter zu Instruktionen, die Register in der CPU ändern. Und jedes Programm muss wissen, welche Änderungen wie vorgenommen wurden. Entsprechende Compiler übernahmen dann diesen Job zumindest für Register und heute muss man wissen, dass es Variablen gibt, die als veränderbarer und potenziell gemeinsam genutzter Speicherplatz existieren und immer im Vordergrund der imperativen Programmierung stehen.
Im Gegensatz dazu sind funktionale Programmiersprachen nicht so sehr von der von Neumann Architektur und der Idee, Variablen/Speicherplätze zu lesen und zu modifizieren und durch Zustandsänderungen motiviert, sondern von der Idee mathematischer Ausdrücke. Natürlich werden solche Programme nach unten hin auch in zustandsändernde Maschineninstruktionen übersetzt, aber kontrolliert, so dass der Programmierer sich nicht darum zu kümmern braucht und hier keine Fehler machen kann.
Beide Seiten haben sich gegenseitig viel eingestanden und mittlerweile viel voneinander übernommen. So ziemlich jede imperative Programmiersprache besitzt heute funktionale Aspekte und fast jede funktionale Sprache besitzt Elemente, die Berechnungen mit Nebeneffekten ausdrücken.
Ich kann hier nur allerwärmstens den sehr guten Vortrag über die Evolution von Haskell empfehlen, der auch sehr für Haskell-Neulinge interessant ist:

 

[baker333]

Vielen Dank Euch! Ich schaue mir das morgen nochmal an und dann werde ich bestimmt eine Lösung finde. Weitere Aufgaben warten dann ja auch schon