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
Factorial recursivo
Para valores positivos de , vamos a escribir como lo hicimos antes, como un producto de números empezando en y bajando hasta llegar a 1: = . Pero observa que es otra manera de escribir , así que podemos decir que . ¿Viste lo que acabamos de hacer? Escribimos como un producto en el cual uno de los factores es . Te dijimos que podemos calcular calculando y después multplicando el resultado de calcular por . Puedes calcular la función factorial de al calcular primero la función factorial de . Decimos que calcular es un subproblema que resolvemos para calcular !.
Veamos un ejemplo: calcular 5!.
- Puedes calcular 5! como
. - Ahora necesitas resolver el subproblema de calcular 4!, el cual puedes calcular como
!. - Ahora necesitas resolver el subproblema de calcular 3!, el cual es
. - Ahora 2!, el cual es
. - Ahora necesitas calcular 1!. Podrías decir que 1! equivale a 1, porque es el producto de todos los enteros desde 1 hasta 1. O puedes aplicar la fórmula de
. Vamos a hacerlo aplicando la fórmula. - Definimos 0! igual a 1.
- Ahora puedes calcular
. - Habiendo calculado
, puedes calcular . - Habiendo calculado
, puedes calcular . - Habiendo calculado
, puedes calcular . - Por último, habiendo calculado
, puedes terminar de calcular .
Así que ahora tenemos otra manera de pensar acerca de cómo calcular el valor de para todos los enteros no negativos :
- Si
, entonces declara que . - De lo contrario,
debe ser positivo. Resuelve el subproblema de calcular , multiplica este resultado por y declara que es igual al resultado de este producto.
Cuando estamos calculando de esta manera, llamamos al primer caso, en donde inmediatamente sabemos la respuesta, el caso base, y llamamos al segundo caso, en donde tenemos que calcular la misma función pero en un valor diferente, el caso recursivo.
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?
- que es el factorial recursivo(2 votos)
- calcular la misma función pero en un valor diferente(1 voto)
- Entonces... ¿Cúal es la formula?(2 votos)
- Como puedo hacer n! en codigo?(2 votos)
- como se aplica el valor recursivo ?(1 voto)
- ¿Cuál es el caso base de esta función?(1 voto)
- a que se le determina el caso recursivo y caso base(1 voto)
- Porque julio profe no me explica mejor, ARRIBA ESPAÑA(0 votos)
- Ns pq no te loexplica(1 voto)