Obliczanie potęgi danej liczby

JavaScript ma wprawdzie wbudowaną funkcję pow, która oblicza potęgi danej liczby ale korzystając z rekurencji możesz napisać taką funkcję samemu tak, by była bardzo wydajna. Jedyny szkopuł polega na tym że wykładnik potęgi musi być liczbą całkowitą.

Załóżmy że chcesz obliczyć $x^n$x, start superscript, n, end superscript, gdzie $x$xjakąś liczbą rzeczywistą a $n$n jest dowolną liczbą całkowitą. Łatwo podać odpowiedź gdy $n$n równa się 0, ponieważ $x^0 = 1$x, start superscript, 0, end superscript, equals, 1 niezależnie od tego ile wynosi $x$x . To dobry przypadek bazowy.

Więc teraz zobaczmy, co stanie się kiedy $n$n jest dodatnie. Zacznijmy od przypomnienia, że kiedy mnożysz potęgi zmiennej $x$x, dodajesz wykładniki: $x^a \cdot x^b = x^{a+b}$x, start superscript, a, end superscript, dot, x, start superscript, b, end superscript, equals, x, start superscript, a, plus, b, end superscript dla dowolnej podstawy $x$x oraz dowolnych wykładników $a$a i $b$b. Dlatego jeśli $n$n jest dodatnie i parzyste, wtedy $x^n = x^{n/2} \cdot x^{n/2}$x, start superscript, n, end superscript, equals, x, start superscript, n, slash, 2, end superscript, dot, x, start superscript, n, slash, 2, end superscript. Jeśli miałeś policzyć $y = x^{n/2}$y, equals, x, start superscript, n, slash, 2, end superscript przy użyciu rekurencji, wtedy możesz obliczyć $x^n$x, start superscript, n, end superscript jako $y \cdot y$y, dot, y. Co w przypadku, gdy $n$n jest dodatnie i nieparzyste? Wtedy $x^n = x^{n-1} \cdot x$x, start superscript, n, end superscript, equals, x, start superscript, n, minus, 1, end superscript, dot, x, a$n-1$n, minus, 1 wynosi albo 0, albo jest dodatnie i parzyste. Właśnie zobaczyliśmy jak obliczyć potęgi liczby $x$x kiedy wykładnik jest równy 0 lub jest dodatni i parzysty. Dlatego możesz policzyć $x^{n-1}$x, start superscript, n, minus, 1, end superscript przez zastosowanie rekurencji, a następnie użyć tego wyniku, aby obliczyć $x^n = x^{n-1} \cdot x$x, start superscript, n, end superscript, equals, x, start superscript, n, minus, 1, end superscript, dot, x.

Co w przypadku, gdy $n$n jest ujemne? Wtedy $x^n = 1 / x^{-n}$x, start superscript, n, end superscript, equals, 1, slash, x, start superscript, minus, n, end superscript, a wykładnik $-n$minus, n jest dodatni, ponieważ jest to liczba przeciwna do liczby ujemnej. Czyli możesz obliczyć $x^{-n}$x, start superscript, minus, n, end superscript stosując rekurencję i wziąć odwrotność tej liczby.

Łącząc wszystkie powyższe rozważania w całość, otrzymujemy następujący algorytm rekurencyjny do obliczania $x^n$x, start superscript, n, end superscript:

Materiał powstał we współpracy profesorów z Dartmouth Computer Science Thomasa Cormena i Devina Balkcoma oraz zespołu nauczycieli informatyki Khan Academy. Materiał jest udostępniony na licencji CC-BY-NC-SA.