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
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 n, !, resolvimos el problema de calcular n, ! (el problema original) al resolver el subproblema de calcular el factorial de un número menor, es decir, al calcular left parenthesis, n, minus, 1, right parenthesis, ! (la instancia más pequeña del mismo problema), y después al usar la solución del subproblema para calcular el valor de n, !.
Para que un algoritmo recursivo funcione, los subproblemas más pequeños eventualmente deben llegar al caso base. Cuando calculamos n, !, los subproblemas se hacen más y más pequeños hasta que calculamos 0, !. Debes asegurarte de que, eventualmente, llegues al caso base.
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 left parenthesis, minus, 1, right parenthesis, !, primero tratarías de calcular left parenthesis, minus, 2, right parenthesis, !, para poder multiplicar el resultado por minus, 1. Pero para calcular left parenthesis, minus, 2, right parenthesis, !, primero tratarías de calcular left parenthesis, minus, 3, right parenthesis, !, para poder multiplicar el resultado por minus, 2. Y después tratarías de calcular left parenthesis, minus, 3, right parenthesis, !, y así sucesivamente. Claro, los números se están haciendo más pequeños, pero también se están alejando cada vez más del caso base de calcular 0, !. Nunca obtendrías una respuesta.
Incluso aunque puedas garantizar que el valor de n no sea negativo, aún así puedes meterte en problemas si no haces los subproblemas progresivamente más pequeños. Aquí hay un ejemplo. Vamos a tomar la fórmula n, !, equals, n, dot, left parenthesis, n, minus, 1, right parenthesis, ! y dividir ambos lados entre n, para obtener n, !, slash, n, equals, left parenthesis, n, minus, 1, right parenthesis, !. Hagamos una nueva variable , m, que sea igual a n, plus, 1. Como nuestra fórmula aplica para cualquier número positivo, vamos a sustituir m por n, para obtener m, !, slash, m, equals, left parenthesis, m, minus, 1, right parenthesis, !. Como m, equals, n, plus, 1, ahora tenemos left parenthesis, n, plus, 1, right parenthesis, !, slash, left parenthesis, n, plus, 1, right parenthesis, equals, left parenthesis, n, plus, 1, minus, 1, right parenthesis, !. Al intercambiar lados y observar que n, plus, 1, minus, 1, equals, n, obtenemos n, !, equals, left parenthesis, n, plus, 1, right parenthesis, !, slash, left parenthesis, n, plus, 1, right parenthesis. Esta fórmula nos hace creer que puedes calcular n, ! al primero calcular left parenthesis, n, plus, 1, right parenthesis, ! y después dividir el resultado entre n, plus, 1. Pero para calcular left parenthesis, n, plus, 1, right parenthesis, !, tendrías que calcular left parenthesis, n, plus, 2, right parenthesis, !, luego left parenthesis, n, plus, 3, right parenthesis, !, y así sucesivamente. Nunca llegarías al caso base de 0. ¿Por qué no? Porque cada problema recursivo te pide calcular el valor de un número más grande, no de un número más pequeño. Si n es positivo, nunca llegarías al caso base de 0.
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)