Factorial recursivo

Para valores positivos de $n$‍, vamos a escribir $n!$‍ como lo hicimos antes, como un producto de números empezando en $n$‍ y bajando hasta llegar a 1: $n!$‍ = $n\cdot (n-1)\cdots 2\cdot 1$‍. Pero observa que $(n-1)\cdots 2\cdot 1$‍ es otra manera de escribir $(n-1)!$‍, así que podemos decir que $n!=n\cdot (n-1)!$‍. ¿Viste lo que acabamos de hacer? Escribimos $n!$‍ como un producto en el cual uno de los factores es $(n-1)!$‍. Te dijimos que podemos calcular $n!$‍ calculando $(n-1)!$‍ y después multplicando el resultado de calcular $(n-1)!$‍ por $n$‍. Puedes calcular la función factorial de $n$‍ al calcular primero la función factorial de $n-1$‍. Decimos que calcular $(n-1)!$‍ es un subproblema que resolvemos para calcular $n$‍!.

Veamos un ejemplo: calcular 5!.

Así que ahora tenemos otra manera de pensar acerca de cómo calcular el valor de $n!$‍ para todos los enteros no negativos $n$‍:

Cuando estamos calculando $n!$‍ 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.