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
La función factorial
Para nuestro primer ejemplo de recursividad, vamos a ver cómo calcular la función factorial. Indicamos el factorial de n como n, !. Es simplemente el producto de los enteros desde 1 hasta n. Por ejemplo, 5! equivale a 1, dot, 2, dot, 3, dot, 4, dot, 5, o 120. (Nota: siempre que estemos hablando acerca de la función factorial, todos los signos de exclamación se refieren a la función factorial y no son para enfatizar).
Puedes preguntarte por qué nos podría importar la función factorial. Es muy útil para cuando estamos tratando de contar de cuántas maneras diferentes podemos ordenar cosas o de cuántas maneras diferentes podemos combinar cosas. Por ejemplo, ¿de cuántas maneras diferentes podemos acomodar n cosas? Tenemos n opciones para la primera cosa. Para cada una de esas n opciones, nos quedamos con n, minus, 1 opciones para la segunda cosa, de modo que tenemos n, dot, left parenthesis, n, minus, 1, right parenthesis opciones para las dos primeras cosas, en orden. Ahora, para cada una de estas dos primeras opciones, tenemos n, minus, 2 opciones para la tercera cosa, dándonos n, dot, left parenthesis, n, minus, 1, right parenthesis, dot, left parenthesis, n, minus, 2, right parenthesis opciones para las tres primeras cosas, en orden. Y así sucesivamente, hasta que llegamos a solo dos cosas restantes, y después a una sola cosa restante. Todo junto, tenemos n, dot, left parenthesis, n, minus, 1, right parenthesis, dot, left parenthesis, n, minus, 2, right parenthesis, \@cdots, 2, dot, 1 formas en que podemos ordenar n cosas. Y ese producto es simplemente n, ! (n factorial), pero con el producto escrito desde n hasta 1 en vez de ir desde 1 hasta n.
Otro uso para la función factorial es contar de cuántas maneras puedes escoger cosas de una colección de cosas. Por ejemplo, supón que te vas de viaje y quieres escoger cuáles playeras llevar. Digamos que tienes n playeras pero tienes espacio para empacar solo k de ellas. ¿De cuántas maneras diferentes puedes escoger k playeras de una colección de n playeras? La respuesta (la cual no trataremos de justificar aquí) resulta ser n, !, slash, left parenthesis, k, !, dot, left parenthesis, n, minus, k, right parenthesis, !, right parenthesis. Así que la función factorial puede ser bastante útil. Puedes aprender más acerca de permutaciones y combinaciones aquí, pero no necesitas entenderlas para implementar un algoritmo factorial.
La función factorial está definida para todos los enteros positivos, junto con el 0. ¿Qué valor debe tener 0! ? Es el producto de todos los enteros mayores o iguales que 1 y menores o iguales que 0. Pero no hay tales enteros. Por lo tanto, definimos que 0! equivale a la identidad multiplicativa, que es 1. (Definir 0! = 1 empata bien con la fórmula para escoger k cosas de n cosas. Supón que queremos saber cuántas maneras hay para escoger n cosas de n cosas. Eso es fácil, porque solo hay una manera: escoge todas las n cosas. Así que ahora sabemos que, usando nuestra fórmula, n, !, slash, left parenthesis, n, !, dot, left parenthesis, n, minus, n, right parenthesis, !, right parenthesis debe ser igual a 1. Pero left parenthesis, n, minus, n, right parenthesis, ! es 0!, así que ahora sabemos que n, !, slash, left parenthesis, n, !, dot, 0, !, right parenthesis debe ser igual a 1. Si cancelamos el n, ! tanto en el numerador como en el denominador, vemos que 1, slash, left parenthesis, 0, !, right parenthesis debe ser igual a 1, y sí lo es porque 0! es igual a 1).
Así que ahora tenemos una manera de pensar acerca de n, !. Es igual a 1 cuando n, equals, 0, y es igual a 1, dot, 2, \@cdots, left parenthesis, n, minus, 1, right parenthesis, dot, n cuando n es positivo.
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?
- para que nos sirve hallar la funcion factorial ?(2 votos)
- es para probabilidad el numero de combinaciones(4 votos)
- ¿Alguien tuvo que cambiar el código?
Aquí mi versión.
var factorial = function(n) {
var result = 1;
for(var i = n; i > 0; i--){
result = result*i;
}
return result;
};
println("The value of 5! should be " + 5*4*3*2*1);
println("The value of 5! is " + factorial(5));
println("The value of 0! should be 1");
println("The value of 0! is " + factorial(0));
Program.assertEqual(factorial(5), 120);
Program.assertEqual(factorial(0), 1);
Program.assertEqual(factorial(6), 720);
Program.assertEqual(factorial(4),24);(2 votos) - para que nos sirve hallar la funcion factorial ?(1 voto)
- para explicar la recursividad de u programa y cada vez sea mas sencillo(3 votos)
- para que sirve la función factorial ?(1 voto)
- la funcion factorial solo se podra aplicar con los numeros enteros(1 voto)
- Es muy útil para cuando estamos tratando de contar de cuántas maneras diferentes podemos ordenar cosas o de cuántas maneras diferentes podemos combinar cosas(2 votos)
- porque ricardo se parece a vector?(1 voto)