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 x, start superscript, n, end superscript, en donde x es cualquier número real y n es cualquier número entero. Es fácil si n es 0, ya que x, start superscript, 0, end superscript, equals, 1 sin importar qué valor tenga x. Ese es un buen caso base.
Así que ahora veamos qué pasa cuando n es positivo. Empecemos por recordar que cuando multiplicas potencias de x, sumas los exponentes: 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 y cualesquiera exponentes a y b. Por lo tanto, si n es positivo y par, entonces 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, equals, x, start superscript, n, slash, 2, end superscript de manera recursiva, entonces podrías calcular x, start superscript, n, end superscript como y, dot, y. ¿Qué pasa si n es positivo e impar? Entonces x, start superscript, n, end superscript, equals, x, start superscript, n, minus, 1, end superscript, dot, x, y n, minus, 1 es 0 o es positivo y par. Acabamos de ver cómo calcular las potencias de x cuando el exponente es 0 o positivo y par. Por lo tanto, podrías calcular x, start superscript, n, minus, 1, end superscript de manera recursiva, y después usar este resultado para calcular x, start superscript, n, end superscript, equals, x, start superscript, n, minus, 1, end superscript, dot, x.
¿Qué pasa cuando n es negativa? Entonces x, start superscript, n, end superscript, equals, 1, slash, x, start superscript, minus, n, end superscript, y el exponente minus, n es positivo, ya que es la negación de un número negativo. Así que puedes calcular 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, start superscript, n, end superscript:
- El caso base es cuando n, equals, 0 y x, start superscript, 0, end superscript, equals, 1.
- Si n es positivo y par, calcula y, equals, x, start superscript, n, slash, 2, end superscript de manera recursiva y después x, start superscript, n, end superscript, equals, y, dot, y. Observa que puedes salirte con la tuya al hacer una sola llamada recursiva en este caso, al calcular x, start superscript, n, slash, 2, end superscript una sola vez y después multiplicar el resultado de esta llamada recursiva por sí misma.
- Si n es positivo e impar, calcula x, start superscript, n, minus, 1, end superscript de manera recursiva de modo que el exponente sea 0 o positivo y par. Después, x, start superscript, n, end superscript, equals, x, start superscript, n, minus, 1, end superscript, dot, x.
- Si n es negativo, calcula x, start superscript, minus, n, end superscript de manera recursiva de modo que el exponente se vuelva positivo. Después, x, start superscript, n, end superscript, equals, 1, slash, x, start superscript, minus, 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.
¿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)