Emezeta.com

Recursividad: Entender lo entendible


Hace una semana, en la asignatura de Metodología de la Programación I hemos empezado a dar un tema que me interesaba bastante dentro del temario de la programación básica, que es la recursividad.

recursividad

La recursividad tiene una curiosa definición, que intentaré explicar sin meterme en detalles técnicos: Se trata de realizar una función, de modo que antes de terminarla la has vuelto a comenzar a realizar.

Para comprender esta enrevesada definición se me ocurre un ejemplo sencillo: Nos encontramos en un gran apartamento y estamos buscando a una persona. Para encontrarla realizamos una acción (abrir la puerta de una habitación) para comprobar si está dentro esa persona. Ocurre que dentro de esa misma habitación pueden haber varias habitaciones más (baño y cocina por ejemplo) y a su vez, dentro de la cocina un trastero. Así pues, una vez entrado en la primera habitación mencionada y no encontrar a la persona que buscamos, nos meteremos en la cocina y si no está, buscaremos en el trastero.

Aprovechando ya este ejemplo desarrollado, en el caso de que tampoco encontraramos a la persona en el trastero, deberíamos retroceder hasta encontrar una habitación anterior que posea una habitación -valga la «rebuznancia»- en la que aún no hayamos mirado, y así sucesivamente. A esto último se le denomina Backtracking (Volver atrás).

las torres de hanoi

Investigando un poco más sobre el tema, doy con algunos de los ejercicios propuestos en años anteriores en mi facultad como el juego de Las torres de Hanoi -donde se entiende muy bien el uso de la recursividad en ámbitos de programación-, la función de Ackermann o la sucesión o serie de Fibonacci.

Además de todos estos ejemplos, existe uno que me llamó mucho la atención. Se trata del número de oro (Φ), que se mantiene presente -por ejemplo- en la forma en la que se crean las caracolas o los árboles y que era considerada una cifra con multitud de propiedades mágicas por los antiguos filosofos griegos:

numero aureo

Este año nos ha tocado hacer un asistente para resolver sudokus, juego numérico que se ha puesto muy de moda últimamente, y práctica que me ha resultado bastante interesante. En cuánto pase la semana de entrega de la práctica subiré el código, si a alguien le interesa.

EDITADO: En este artículo explicativo del backtracking (volviéndo atrás) podrás encontrar el Asistente para resolver sudokus en Pascal.