Calcular potencias de un número

Aunque JavaScript tiene una función pow interna que calcula potencias de un número, puedes escribir una función parecida de manera recursiva, y puede ser muy eficiente. El único problema es que el exponente tiene que ser un número entero.

Supón que quieres calcular $x^n$x, start superscript, n, end superscript, en donde $x$x es cualquier número real y $n$n es cualquier número entero. Es fácil si $n$n es 0, ya que $x^0 = 1$x, start superscript, 0, end superscript, equals, 1 sin importar qué valor tenga $x$x. Ese es un buen caso base.

Así que ahora veamos qué pasa cuando $n$n es positivo. Empecemos por recordar que cuando multiplicas potencias de $x$x, sumas los exponentes: $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 para cualquier base $x$x y cualesquiera exponentes $a$a y $b$b. Por lo tanto, si $n$n es positivo y par, entonces $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. Si fueras a calcular $y = x^{n/2}$y, equals, x, start superscript, n, slash, 2, end superscript de manera recursiva, entonces podrías calcular $x^n$x, start superscript, n, end superscript como $y \cdot y$y, dot, y. ¿Qué pasa si $n$n es positivo e impar? Entonces $x^n = x^{n-1} \cdot x$x, start superscript, n, end superscript, equals, x, start superscript, n, minus, 1, end superscript, dot, x, y $n-1$n, minus, 1 es 0 o es positivo y par. Acabamos de ver cómo calcular las potencias de $x$x cuando el exponente es 0 o positivo y par. Por lo tanto, podrías calcular $x^{n-1}$x, start superscript, n, minus, 1, end superscript de manera recursiva, y después usar este resultado para calcular $x^n = x^{n-1} \cdot x$x, start superscript, n, end superscript, equals, x, start superscript, n, minus, 1, end superscript, dot, x.

¿Qué pasa cuando $n$n es negativa? Entonces $x^n = 1 / x^{-n}$x, start superscript, n, end superscript, equals, 1, slash, x, start superscript, minus, n, end superscript, y el exponente $-n$minus, n es positivo, ya que es la negación de un número negativo. Así que puedes calcular $x^{-n}$x, start superscript, minus, n, end superscript de manera recursiva y tomar su inverso.

Al juntar estas observaciones, obtenemos el siguiente algoritmo recursivo para calcular $x^n$x, start superscript, n, end superscript:

Este contenido es una colaboración de los profesores de Dartmouth Computer Science Thomas Cormen y Devin Balkcom, con el equipo de contenidos de computación de Khan Academy. El contenido está bajo licencia CC-BY-NC-SA.