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\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$‍ cosas? Tenemos $n$‍ opciones para la primera cosa. Para cada una de esas $n$‍ opciones, nos quedamos con $n-1$‍ opciones para la segunda cosa, de modo que tenemos $n\cdot (n-1)$‍ opciones para las dos primeras cosas, en orden. Ahora, para cada una de estas dos primeras opciones, tenemos $n-2$‍ opciones para la tercera cosa, dándonos $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\cdot (n-1)\cdot (n-2)\cdots 2\cdot 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!/(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$‍ 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!/(n!\cdot (n-n)!)$‍ debe ser igual a 1. Pero $(n-n)!$‍ es 0!, así que ahora sabemos que $n!/(n!\cdot 0!)$‍ debe ser igual a 1. Si cancelamos el $n!$‍ tanto en el numerador como en el denominador, vemos que $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!$‍. Es igual a 1 cuando $n=0$‍, y es igual a $1\cdot 2\cdots (n-1)\cdot 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.