Entendiendo la recursividad con las Torres de Hanoi

la recursividad es un concepto muy utilizado en matemáticas y en programación en el que para poder definir algo como puede ser una función un proceso dentro del cuerpo de esa definición tiene que además la propia cosa definida el ejemplo más básico es el caso de los factoriales el factorial de un número n equivale a multiplicar todos los números enteros comprendidos entre 1 y n por ejemplo 5 factoriales uno por dos por tres por cuatro por cinco sin embargo esto se puede definir de forma recursiva simplemente diciendo que 5 factorial es 5 por 4 factorial el factorial es uno de los ejemplos que se ponen la mayoría de casos para explicar la recursividad porque es la forma más sencilla de explicarlo pero no es ni mucho menos la única cuando uno construye funciones recursivas es importante establecer un caso base en el que no necesitamos recurrir de nuevo esto es importante ya que si nuestra función se recurre infinitamente nunca tendrá solución por ejemplo si quieres usar recursividad para calcular un factorial deberás establecer un caso en el que puedas dar el factorial sin tener que recurrir por ejemplo el factorial del 0 es un sin embargo hay más problemas que se pueden beneficiar de la recursividad y uno de esos es el de las torres de hanoi en esencia en el problema de las torres dejando ahí tenemos tres torres donde discos apilados en un momento inicial tenemos una torre con los discos en forma de pirámide donde cada disco es más pequeño que el disco que tiene debajo en este problema de lógica tenemos que pasar la pirámide de la primera de las torres a la tercera recordando un par de reglas clave en primer lugar que tiene que quedarnos la pirámide por lo que la torre final también tiene que estar ordenada de la más pequeña a la más grande y además solo podemos mover el disco a la vez y un disco no puede descansar sobre otro que sea más pequeño que el si nunca te has enfrentado este problema en internet existen multitud de páginas web donde puedes jugar online este problema de lógica en la descripción ha dejado algunas simplemente abre una y para ordenar los discos por tu cuenta si no estás acostumbrado a este problema lo más normal es que al principio de datas que es un paso y no sepas cómo continuar afortunadamente existe una forma fácil de resolver este problema y es con recursividad el truco está en dividir un problema gordo como puede ser mover discos de una torre a otra en un problema más sencillo para ello lo que tienes que hacer es que si quieres mover una pirámide de n discos de una tonada a otra lo mejor que puedes hacer es lo siguiente en primer lugar mover en uno o varios pasos los primeros n menos un discos a la torre del medio que es la torre auxiliar después mueves el disco de abajo a la tercera torre y después otra vez en uno o varios pasos mueves los discos que tenemos ahora en la torre del medio a la torre de la derecha y con esto ya nos hemos sacado de la manga un problema cursi vo porque cuando esto hemos conseguido que para poder mover los discos de una torre a otra uno de los pasos sean mover discos de una torre a otra en todos los casos vamos a tener una torre origen una torre destino y una torre que usaremos como auxiliar para ayudarnos a mover los discos de una torre a otra obviamente si queremos formular el problema recursivo en condiciones tenemos que definir un caso base que no dependa de la recursividad y este caso es cuando nuestra torre de origen solo tiene un disco si solo tiene un disco no necesitas operaciones intermedias te basta con mover tu único disco de la torre inicial a la torre final y boom problema resuelto ahora viene la pregunta del millón como escribimos esto en código lo más sencillo sería representar cada disco con un número comprendido entre 1 y n donde los números más altos representan los discos más grandes lo apropiado será representar las torres como pilas donde introduces enteros ya que al fin y al cabo en una pila al igual que en una torre solo puedes meter y sacar elementos que estén en la cima si el pseudo código general para este algoritmo podría ser una función llamada hanoi a la que le indiquemos cuántos discos tienen nuestra torre ya que si no el algoritmo no sabrá cuándo ha llegado el último disco cuáles son las torres origen auxiliar y destino el algoritmo se debe comportar de este modo primero tiene que determinar si eso lo tiene que mover un disco y si solo tienen que mover un disco entonces lo va a mover directamente de la torre origen destino en cambio si tenemos más del disco primero tiene que mover los primeros n sus discos de la torre origen a la torre auxiliar después debe mover el disco que quede en la torre eiffel a la torre destino y finalmente debe mover los n - un discos que en la tele auxiliar a la torre de destino si esto lo convertimos a pseudo código nos queda algo como lo que aparece en pantalla para saber cuántos pasos deben correrse como mínimo para poder desplazar n discos podemos utilizar un modelo inductivo para mover un disco vamos a necesitar un paso para mover dos discos vamos a necesitar un paso para mover un disco a la segunda torre un paso para mover el disco de abajo y otro paso para mover el disco de arriba la tercera torre en total tres pasos para mover tres discos vamos a necesitar los tres pasos que hacen falta para mover dos torres el paso intermedio y luego otros tres pasos en total 7 y para mover cuatro discos van a ser siete pasos un paso y otros siete pasos en total 15 viendo todas estas fórmulas podemos inducir que el número de pasos para mover n discos es siempre 2 ^ en el -1 por ejemplo para mover siete discos van a ser necesarios dos alas 7 - con pasos es decir 127 como reseña histórica la leyenda cuenta que en un templo indio un rey mando 64 discos de oro y las diosas instrucciones a los monjes para que manipulasen los discos la leyenda cuenta que cuando el último disco fuese colocado en la tercera torre el fin del mundo llegaría preocupado no deberías recordemos por la fórmula que para mover 64 discos van a ser necesarios 2 a las 64 menos sus movimientos 2 a las 64 menos 1 es un numero grotescamente grande incluso si los monjes fuesen capaces de hacer un movimiento cada segundo necesitaría en casi 585.000 millones de años y por que se les llama torres de hanoi si la leyenda está basada en la india bueno eso es porque la leyenda ha sido escrita cambiando cosas muchas veces desde aquí en orden instalar los discos hasta donde estaba el templo y según una de las leyendas el templo estaba situado en hanoi la capital de vietnam por eso al problema se le llama torres de hanoi