Recursividad aplicada: Torres de Hanoi

Este juego matemático es clásico de los problemas de programación. Hoy vamos a ver cómo calcular el número de movimientos necesarios para resolver el juego según el número de discos, de forma recursiva en C++.

#include<stdio.h>
int hanoi(int n)
{
    if(n==1)
        return 1;
    else
        return 2 * hanoi(n-1) + 1;
}
int main()
{
    int disc, mov;
    printf("::TORRES DE HANOI::\n");
    printf("Numero de discos: ");scanf("%i",&disc);
    printf("\tMovimientos necesarios: %i\n", hanoi(disc));
    return 0;
}

Otro algoritmo raro. Lo que sabemos es que si tenemos 1 disco el número de movimientos es 1 y que ese es nuestro caso base (si n==1 retorna 1), a partir de ahí el número de movimientos se puede calcular si multiplicamos por dos el número de movimientos para n-1 y le sumamos 1, o sea: 2 + hanoi(n-1) + 1

• Si son 2 discos, entonces 2 * hanoi(1) + 1 = 2 * 1 + 1 = 3
• Si son 3 discos, entonces 2 * hanoi(2) + 1 = 2 * 3 + 1 = 7
• etc