Exponentieren mit Hilfe einer Rekursion

mathon

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

Bashar

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.

mathon

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