Para nuestro primer ejemplo de recursividad, vamos a ver cómo calcular la función factorial. Indicamos el factorial de n n como n! n! . Es simplemente el producto de los enteros desde 1 hasta n n . Por ejemplo, 5! equivale a 12345 1 \cdot 2 \cdot 3 \cdot 4 \cdot 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 n cosas? Tenemos n n opciones para la primera cosa. Para cada una de esas n n opciones, nos quedamos con n1 n-1 opciones para la segunda cosa, de modo que tenemos n(n1) n \cdot (n-1) opciones para las dos primeras cosas, en orden. Ahora, para cada una de estas dos primeras opciones, tenemos n2 n-2 opciones para la tercera cosa, dándonos n(n1)(n2) n \cdot (n-1) \cdot (n-2) 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(n1)(n2)21 n \cdot (n-1) \cdot (n-2) \cdots 2 \cdot 1 formas en que podemos ordenar n n cosas. Y ese producto es simplemente n! n! (n n factorial), pero con el producto escrito desde n n hasta 1 en vez de ir desde 1 hasta n 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 n playeras pero tienes espacio para empacar solo k k de ellas. ¿De cuántas maneras diferentes puedes escoger k k playeras de una colección de n n playeras? La respuesta (la cual no trataremos de justificar aquí) resulta ser n!/(k!(nk)!) n! / (k! \cdot (n-k)!) . 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 k cosas de n n cosas. Supón que queremos saber cuántas maneras hay para escoger n n cosas de n n cosas. Eso es fácil, porque solo hay una manera: escoge todas las n n cosas. Así que ahora sabemos que, usando nuestra fórmula, n!/(n!(nn)!) n! / (n! \cdot (n-n)!) debe ser igual a 1. Pero (nn)! (n-n)! es 0!, así que ahora sabemos que n!/(n!0!) n! / (n! \cdot 0!) debe ser igual a 1. Si cancelamos el n! n! tanto en el numerador como en el denominador, vemos que 1/(0!) 1/(0!) 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! n! . Es igual a 1 cuando n=0 n = 0 , y es igual a 12(n1)n 1 \cdot 2 \cdots (n-1) \cdot n cuando n 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.
Cargando