¿Alguna vez has visto un juego de muñecas rusas? Al principio, solo ves una figurilla, generalmente de madera pintada, que se ve más o menos así:
Foto de la primera muñeca rusa
Puedes quitar la mitad de arriba de la primera muñeca, ¿y qué ves adentro? ¡Otra muñeca rusa, un poco más pequeña!
Foto de la segunda muñeca rusa dentro de la primera muñeca rusa
Puedes quitar esa muñeca y separar sus mitades superior e inferior. Y ves, una vez más, otra muñeca más pequeña:
Foto de la tercera muñeca rusa dentro de la segunda muñeca rusa, junto a la primera muñeca rusa
Y una vez más:
Foto de la cuarta muñeca rusa dentro de la tercera muñeca rusa
Y puedes continuar. Eventualmente encontrarás la muñeca rusa más pequeña. Es solo una pieza, así que no se abre:
Foto de todas las muñecas rusas
Empezamos con un muñeca rusa grande, y vimos muñecas rusas más y más pequeñas, hasta que vimos una que era tan pequeña que no podría contener a otra.
¿Qué tienen que ver las muñecas rusas con los algoritmos? Así como una muñeca rusa tienen una muñeca rusa más pequeña dentro de ella, que tiene una muñeca rusa aún más pequeña dentro de ella, hasta llegar a una muñeca rusa tan pequeña que ya no puede contener otra, vamos a ver cómo diseñar un algoritmo para resolver un problema de modo que resuelva una instancia más pequeña del mismo problema, a menos que el problema sea tan pequeño que lo podamos resolver directamente. A esta técnica la llamamos recursividad.
La recursividad tiene muchas, muchas aplicaciones. En este módulo vamos a ver cómo usar la recursividad para calcular la función factorial, para determinar si una palabra es un palíndromo, para calcular potencias de un número, para dibujar un tipo de fractal y para resolver el antiguo problema de las Torres de Hanoi. En módulos más adelante usaremos recursividad para resolver otros problemas, incluyendo ordenamientos.

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.