Rekursions Algorithmus

volkard

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.

thais

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.

Bashar

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

volkard

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.

Bashar

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.

XFame

volkard schrieb:

r(0)=1
r(n)=r(0)+1/n!

Das ist doch nicht rekursiv, oder irre ich?

Skym0sh0

ja du irrst dich
das ist pseudo code...
r(0) = 1 ist die abbruch bedingung
und das andere ist das else mit return

Bashar

Das ist in der Tat nicht rekursiv.

volkard

Bashar schrieb:

Das ist in der Tat nicht rekursiv.

sie ist von recht beschränkter rekursionstiefe, aber doch rekursiv, würde ich doch meinen.

Bashar

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)"

volkard

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.