Esta es la idea básica detrás de los algoritmos recursivos:
Para resolver un problema, resuelve un subproblema que sea una instancia más pequeña del mismo problema, y después usa la solución de esa instancia más pequeña para resolver el problema original.
Cuando calculamos n! n! , resolvimos el problema de calcular n! n! (el problema original) al resolver el subproblema de calcular el factorial de un número menor, es decir, al calcular (n1)! (n-1)! (la instancia más pequeña del mismo problema), y después al usar la solución del subproblema para calcular el valor de n! n! .
Para que un algoritmo recursivo funcione, los subproblemas más pequeños eventualmente deben llegar al caso base. Cuando calculamos n! n! , los subproblemas se hacen más y más pequeños hasta que calculamos 0! 0! . Debes asegurarte de que, eventualmente, llegues al caso base.
Por ejemplo, ¿qué pasaría si tratáramos de calcular el factorial de un número negativo al usar nuestro método recursivo? Para calcular (1)! (-1)! , primero tratarías de calcular (2)! (-2)! , para poder multiplicar el resultado por minus, 1. Pero para calcular (2)! (-2)! , primero tratarías de calcular (3)! (-3)! , para poder multiplicar el resultado por minus, 2. Y después tratarías de calcular (3)! (-3)! , y así sucesivamente. Claro, los números se están haciendo más pequeños, pero también se están alejando cada vez más del caso base de calcular 0! 0! . Nunca obtendrías una respuesta.
Incluso aunque puedas garantizar que el valor de n no sea negativo, aún así puedes meterte en problemas si no haces los subproblemas progresivamente más pequeños. Aquí hay un ejemplo. Vamos a tomar la fórmula n!=n(n1)! n! = n \cdot (n-1)! y dividir ambos lados entre n, para obtener n!/n=(n1)! n! / n = (n-1)! . Hagamos una nueva variable , m, que sea igual a n, plus, 1. Como nuestra fórmula aplica para cualquier número positivo, vamos a sustituir m por n, para obtener m!/m=(m1)! m! / m = (m-1)! . Como m, equals, n, plus, 1, ahora tenemos (n+1)!/(n+1)=(n+11)! (n+1)! / (n+1) = (n+1-1)! . Al intercambiar lados y observar que n, plus, 1, minus, 1, equals, n, obtenemos n!=(n+1)!/(n+1) n! = (n+1)! / (n+1) . Esta fórmula nos hace creer que puedes calcular n! n! al primero calcular (n+1)! (n+1)! y después dividir el resultado entre n, plus, 1. Pero para calcular (n+1)! (n+1)! , tendrías que calcular (n+2)! (n+2)! , luego (n+3)! (n+3)! , y así sucesivamente. Nunca llegarías al caso base de 0. ¿Por qué no? Porque cada problema recursivo te pide calcular el valor de un número más grande, no de un número más pequeño. Si n es positivo, nunca llegarías al caso base de 0.
Podemos extraer la idea de la recursión en dos reglas sencillas:
  1. Cada llamada recursiva debe ser sobre una instancia más pequeña del mismo problema, es decir, un subproblema más pequeño.
  2. Las llamdas recursivas eventualmente deben alcanzar un caso base, el cual se resuelve sin más recursividad.
Regresemos a las muñecas rusas. Aunque no aparecen en ningún algoritmo, puedes ver que cada muñeca encierra a todas las muñecas más pequeñas (de manera análoga al caso recursivo), hasta que la muñeca más pequeña no encierra a ninguna otra (como el caso base).

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.