Contenido principal
Ciencias de la computación
Curso: Ciencias de la computación > Unidad 1
Lección 6: Algoritmos recursivos- Recursividad
- La función factorial
- Desafío: factorial iterativo
- Factorial recursivo
- Desafío: factorial recursivo
- Propiedades de los algoritmos recursivos
- Usar recursividad para determinar si una palabra es un palíndromo o no
- Desafío: ¿una cadena de caracteres es un palíndromo?
- Calcular potencias de un número
- Desafío: potencias recursivas
- Recursividad múltiple con el triángulo de Sierpinski
- Mejorar la eficiencia de las funciones recursivas
- Proyecto: arte recursivo
© 2023 Khan AcademyTérminos de usoPolítica de privacidadAviso de cookies
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 , en donde es cualquier número real y es cualquier número entero. Es fácil si es 0, ya que sin importar qué valor tenga . Ese es un buen caso base.
Así que ahora veamos qué pasa cuando es positivo. Empecemos por recordar que cuando multiplicas potencias de , sumas los exponentes: para cualquier base y cualesquiera exponentes y . Por lo tanto, si es positivo y par, entonces . Si fueras a calcular de manera recursiva, entonces podrías calcular como . ¿Qué pasa si es positivo e impar? Entonces , y es 0 o es positivo y par. Acabamos de ver cómo calcular las potencias de cuando el exponente es 0 o positivo y par. Por lo tanto, podrías calcular de manera recursiva, y después usar este resultado para calcular .
¿Qué pasa cuando es negativa? Entonces , y el exponente es positivo, ya que es la negación de un número negativo. Así que puedes calcular de manera recursiva y tomar su inverso.
Al juntar estas observaciones, obtenemos el siguiente algoritmo recursivo para calcular :
- El caso base es cuando
y . - Si
es positivo y par, calcula de manera recursiva y después . Observa que puedes salirte con la tuya al hacer una sola llamada recursiva en este caso, al calcular una sola vez y después multiplicar el resultado de esta llamada recursiva por sí misma. - Si
es positivo e impar, calcula de manera recursiva de modo que el exponente sea 0 o positivo y par. Después, . - Si
es negativo, calcula de manera recursiva de modo que el exponente se vuelva positivo. Después, .
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.
¿Quieres unirte a la conversación?
- alguien tiene el siguiente desafio resuelto?(1 voto)
- Claro, aquí está :)
var isEven = function(n) {
return n % 2 === 0;
};
var isOdd = function(n) {
return !isEven(n);
};
var power = function(x, n) {
println("Computing " + x + " raised to power " + n + ".");
// base case
if(n === 0) {
return 1;
}
// recursive case: n is negative
if(n < 0) {
return 1 / power(x, -n);
}
// recursive case: n is odd
if(isOdd(n)) {
return power(x, n-1) * x;
}
// recursive case: n is even
if(isEven(n)) {
var y = power(x, n/2);
return y * y;
}
};
var displayPower = function(x, n) {
println(x + " to the " + n + " is " + power(x, n));
};
displayPower(3, 0);
Program.assertEqual(power(3, 0), 1);
displayPower(3, 1);
Program.assertEqual(power(3, 1), 3);
displayPower(3, 2);
Program.assertEqual(power(3, 2), 9);
displayPower(3, -1);
Program.assertEqual(power(3, -1), 1/3);
Program.assertEqual(power(7, 3), 343);
Program.assertEqual(power(6, 5), 7776);(1 voto)
- por que JavaScript aplica la funcion pow en el calculo, teniendo en cuenta el numero entero.(1 voto)
- Hola, lo que hace la función pow() en Javascript es calcular de manera lineal, con un ciclo for, el numero de veces(n) que un numero se necesita multiplicar por si mismo.
E.j. Math.pow(4, 3);
Regresa el valor del numero 4 a la potencia de 3 (4*4*4).
Puedes aprender mas de la funcion pow() en el siguiente enlace:
https://www.w3schools.com/jsref/jsref_pow.asp(2 votos)
- Se que con pow puedo potenciar, pero lo que trataron de explicar aqui no hay por donde cogerlo.(1 voto)