Rekursions Algorithmus
-
Hallo,
ich würde gerne die Eulersche Reihe rekursiv berechnen, finde aber keinen Ansatz
kann mir jemand helfen?Hier die Reihe: 1 + 1/1! + 1/2! + 1/3! ......
gruß danke
-
r(0)=1
r(n)=r(0)+1/n!
-
danke!!
ich hab aber jetzt das Problem es in den Code umzusetzen
-
double r(double n) { if(n==0) return 1; else return r(n-1)+1.0/fact(n); }nebst
double fact(double n) { if(n==0) return 1; else return n*fact(n-1); }müßte vielleicht gehen.
oben meinte ich wohl eher r(n)=r(n-1)+1/n!
meine lösung ist zwar für mich naheliegend, aber die ist nicht lecker schnell.
mit ein wenig nachdenken, geht das auch in einer funktion. leider fällt's mir heute nicht leicht. bin da nicht so schnell wie Bashar, der rekursiv denkt.
-
super funktioniert danke!!!
-
Endstämmig geht's zum Beispiel so:
double r2(long n, double acc) { if(n == 1) return acc + 1; else return r2(n-1, acc + 1.0/fact(n)); } #define r(x) (r2(x, 0.0))Sollte aber auch nicht schneller sein als volkards Variante.
-
Ohne explizit die Fakultät auszurechnen:
double r(int n, int k = 0) { if (n == 0) return 1; else return 1 + r(n-1, k+1)/(k+1); }In der Form ungetestet, aber in Lisp funktionierts
-
Bashar schrieb:
Interessant, aber nicht schön, weil man damit die Reihe "rückwärts" ausrechnet. In der Form ungetestet, aber in Lisp funktionierts
heißt "rückwärts" am ende sogar, daß es in der reihenfolge
1/n! + 1/(n-1)! + 1/(n-2)! ... 1
berechnet wird?
uih, das wäre geil aus numerischer sicht. man soll immer die kleinen summanden zuerst summieren, das macht das ergebnis genauer.
-
Sieht aus, als hätte ich zu spät editiert. Na gut
Es wird eigentlich (...((1/n + 1)/(n-1) + 1).../1 + 1) ausgerechnet, d.h. dass die 1, die für n=0 zurückgegeben wird, dem 1/n!-Summanden, und nicht der 1 von r(0) entspricht. Die Idee ist eigentlich wie beim Horner-Schema. Dass das numerisch besser ist, kann ich mir gut vorstellen.
-
volkard schrieb:
r(0)=1
r(n)=r(0)+1/n!Das ist doch nicht rekursiv, oder irre ich?
-
ja du irrst dich
das ist pseudo code...
r(0) = 1 ist die abbruch bedingung
und das andere ist das else mit return
-
Das ist in der Tat nicht rekursiv.
-
Bashar schrieb:
Das ist in der Tat nicht rekursiv.
sie ist von recht beschränkter rekursionstiefe, aber doch rekursiv, würde ich doch meinen.
-
In einem haarspalterischen Sinne vielleicht, aber man wird dem Begriff dadurch nicht gerecht.
-
volkard schrieb:
r(0)=1
r(n)=r(0)+1/n!Das rechnet doch etwas ganz anderes aus, als "sum(1/(i!),i=1,n)"
-
Mathematikker schrieb:
volkard schrieb:
r(0)=1
r(n)=r(0)+1/n!Das rechnet doch etwas ganz anderes aus, als "sum(1/(i!),i=1,n)"
sicher. war ja auch ein tippfehler, den ich im vierten posting korrigiert hab.