Recursividad

¿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í:

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!

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:

Y una vez más:

Y puedes continuar. Eventualmente encontrarás la muñeca rusa más pequeña. Es de una sola pieza, así que no se abre:

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 ya no puede 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.