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$n como $n!$n, !. Es simplemente el producto de los enteros desde 1 hasta $n$n. Por ejemplo, 5! equivale a $1 \cdot 2 \cdot 3 \cdot 4 \cdot 5$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$n cosas? Tenemos $n$n opciones para la primera cosa. Para cada una de esas $n$n opciones, nos quedamos con $n-1$n, minus, 1 opciones para la segunda cosa, de modo que tenemos $n \cdot (n-1)$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-2$n, minus, 2 opciones para la tercera cosa, dándonos $n \cdot (n-1) \cdot (n-2)$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 \cdot (n-1) \cdot (n-2) \cdots 2 \cdot 1$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$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! \cdot (n-k)!)$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$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! \cdot (n-n)!)$n, !, slash, left parenthesis, n, !, dot, left parenthesis, n, minus, n, right parenthesis, !, right parenthesis debe ser igual a 1. Pero $(n-n)!$left parenthesis, n, minus, n, right parenthesis, ! es 0!, así que ahora sabemos que $n! / (n! \cdot 0!)$n, !, slash, left parenthesis, n, !, dot, 0, !, right parenthesis debe ser igual a 1. Si cancelamos el $n!$n, ! tanto en el numerador como en el denominador, vemos que $1/(0!)$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!$n, !. Es igual a 1 cuando $n = 0$n, equals, 0, y es igual a $1 \cdot 2 \cdots (n-1) \cdot n$1, dot, 2, \@cdots, left parenthesis, n, minus, 1, right parenthesis, dot, 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.