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.


Log in to reply