Contenido principal
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
© 2024 Khan AcademyTérminos de usoPolítica de privacidadAviso de cookies
Propiedades de los algoritmos recursivos
Esta es la idea básica detrás de los algoritmos recursivos:
Para resolver un problema, resuelve un subproblema que sea una instancia más pequeña del mismo problema, y después usa la solución de esa instancia más pequeña para resolver el problema original.
Cuando calculamos
Para que un algoritmo recursivo funcione, los subproblemas más pequeños eventualmente deben llegar al caso base. Cuando calculamos
Por ejemplo, ¿qué pasaría si tratáramos de calcular el factorial de un número negativo al usar nuestro método recursivo? Para calcular
Incluso aunque puedas garantizar que el valor de
Podemos extraer la idea de la recursión en dos reglas sencillas:
- Cada llamada recursiva debe ser sobre una instancia más pequeña del mismo problema, es decir, un subproblema más pequeño.
- Las llamdas recursivas eventualmente deben alcanzar un caso base, el cual se resuelve sin más recursividad.
Regresemos a las muñecas rusas. Aunque no aparecen en ningún algoritmo, puedes ver que cada muñeca encierra a todas las muñecas más pequeñas (de manera análoga al caso recursivo), hasta que la muñeca más pequeña no encierra a ninguna otra (como el caso base).
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?
Me costó trabajo pero lo logré ¿Alguién lo hizo distinto? pongo el código a ver si alguien le sirve.
var factorial = function(n) {
// base case:
if (n < 1 ) {
return 1;
}
// recursive case:
return n*factorial(n-1);
};
println("The value of 0! is " + factorial(0) + ".");
println("The value of 5! is " + factorial(5) + ".");
Program.assertEqual(factorial(0), 1);
Program.assertEqual(factorial(5), 120);
Program.assertEqual(factorial(6), 720);
Program.assertEqual(factorial(3), 6);(4 votos)- var factorial = function(n) {
// base case:
if ( n === 0) {
return 1;(1 voto)
- Hola, alguien lo hizo asi:
var factorial = function(n) {
// base case:
if ( n === 0) {
return 1;
}
// recursive case:
else {
return n * factorial(n - 1);
}
};
println("The value of 0! is " + factorial(0) + ".");
println("The value of 5! is " + factorial(5) + ".");
Program.assertEqual(factorial(0), 1);
Program.assertEqual(factorial(5), 120);
Program.assertEqual(factorial(2), 2);
Program.assertEqual(factorial(3), 6);(2 votos) - se puede indentificar o determinar que cada regla de este tema se podria decir se puede ver ejemplos muy faciles para enterder como son las muñecas rusas.(1 voto)
- Const findFactorial = n => n > 0 ? n * findFactorial(n): 1;
Se retorna el 1 para detener la recursividad.(1 voto)