# Rekursion Wurzel



## baker333 (27. Jan 2019)

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 (27. Jan 2019)

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
> 
> 
> 
> ...


----------



## baker333 (27. Jan 2019)

Dann wäre x_o = 1


----------



## JCODA (27. Jan 2019)

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


----------



## baker333 (27. Jan 2019)

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 (27. Jan 2019)

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


----------



## baker333 (27. Jan 2019)

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 (27. Jan 2019)

baker333 hat gesagt.:


> 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 (27. Jan 2019)

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


----------



## JCODA (27. Jan 2019)

baker333 hat gesagt.:


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


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


----------



## baker333 (27. Jan 2019)

```
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 (27. Jan 2019)

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 (27. Jan 2019)

httpdigest hat gesagt.:


> 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 (27. Jan 2019)

baker333 hat gesagt.:


> 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 (27. Jan 2019)

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


----------



## baker333 (27. Jan 2019)

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 (27. Jan 2019)

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 (27. Jan 2019)

```
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 (27. Jan 2019)

Sieht irgendwie komisch aus


----------



## JCODA (27. Jan 2019)

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 (27. Jan 2019)

Das ganze dynamisch machen und bereits berechnete Werte speichern?


----------



## httpdigest (27. Jan 2019)

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


----------



## baker333 (27. Jan 2019)

httpdigest hat gesagt.:


> 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 (27. Jan 2019)

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


----------



## baker333 (27. Jan 2019)

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


----------



## httpdigest (27. Jan 2019)

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 (27. Jan 2019)

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


----------



## httpdigest (27. Jan 2019)

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 (27. Jan 2019)

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 (27. Jan 2019)

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


----------



## httpdigest (27. Jan 2019)

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 (27. Jan 2019)

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


----------



## baker333 (27. Jan 2019)

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 (27. Jan 2019)

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


----------



## httpdigest (27. Jan 2019)

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 (27. Jan 2019)

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


----------



## httpdigest (27. Jan 2019)

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 (27. Jan 2019)

httpdigest hat gesagt.:


> 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 (27. Jan 2019)

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 (27. Jan 2019)

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


----------

