Para nuestro primer ejemplo de recursividad, vamos a ver cómo calcular la función factorial. Indicamos el factorial de n como n! 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(n1)(n2)21 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! (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!(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 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!(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, equals, 0, y es igual a 12(n1)n 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.