Exponentieren mit Hilfe einer Rekursion



  • hi,

    ich habe versucht das Exponentieren mit Hilfe einer Rekursion in einer Funktion zu berechnen:

    double power(double x, int n)
    {
        double product;
        int count;
    
        if (x==0)
           assert(n>0);
    
        if(n >= 0)
        {
              product = 1;
              for (count = 1; count <= n; ++count)
                 product = product * x;
              return product;
        }
        else
           return 1/power(x, -n);
    }
    

    Jetzt habe ich aber ein kleines problem, da die Funktion eine Laufzeit von log(n) haben sollte, ich denke ich muss dazu folgende Formel verwenden: x^2n = x^n x^n.
    Leider ist mir nicht ganz klar, wie ich meine Funktion am besten dafür umschreiben könnte, hat hier jemand vielleicht ein paar Tipps für mich...? 😞

    matti



  • Das ist keine Rekursion. Du meinst wohl eher sowas:

    double power(double x, int n) {
      if (n < 0)
        return 1/power(x, -n);
      else if (n == 0)
        return 1.0;
      else
        return x * power(x, n-1);
    }
    

    Da kannst du jetzt auch (als zusätzlichen else-Zweig denk ich mal) deine Formel unterbringen.



  • ah super...danke...die frage ist für was ich jetzt überhaupt diese formel noch brauche x^2n = x^n x^n? ist die laufzeit bei dieser rekursion noch nicht log(n) oder...


Log in to reply