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