Código C++

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

Ooootro post sobre recursividad, pero no se preocupen ya solo queda este y otro. Esta vez vamos a calcular el máximo común divisor de dos números de forma recursiva en c++.

#include<stdio.h>
int MCD(int x, int y)
{
    if(y==0)
        return x;
    else
        return MCD(y, x%y);
}
int main()
{
    int num1=0,num2=0;
    printf("::MAXIMO COMUN DIVISOR::\n");
    printf("Introduce el primer numero: ");scanf("%i",&num1);
    printf("Introduce el segundo numero: ");scanf("%i",&num2);
    printf("\tEl resultado es: %i\n", MCD(num1, num2));
    return 0;
}

Este es uno de esos algoritmos recursivos raros o, mejor dicho, difíciles de comprender, mi cerebro estuvo un buen rato echando humo tratando de comprender la lógica con que lo armaron y mi conclusión es que funciona de pura rana. Bueno, al final si supe como funciona pero no porque.

0, 1, 1, 2, 3, 5, 8, 13, 21, …, la serie de Fibonacci es bastante interesante e incluso aparece en la naturaleza. Comienza con un 0, luego un 1 y a partir de ahí cada número es la suma de los dos siguientes. Eso último nos indica recursividad. Veamos como mostrar n números de la serie de Fibonacci de forma recursiva en C++.

#include<stdio.h>
int fibonacci(int n)
{
    if (n<2)
        return n;
    else
        return fibonacci(n-1) + fibonacci(n-2);
}
int main()
{
    int num=0,res=0;
    printf("::NUMEROS DE FIBONACCI::\n");
    printf("Introduce el numero de numeros: ");scanf("%i",&num);
    printf("\t");
    for(int i=0;i<=num-1;i++)
    {
        res = fibonacci(i);
        printf("%i  ", res);
    }
    printf("\n");
    return 0;
}

Es la primera vez que vemos un la llamada a la función dentro de un ciclo. Eso es porque la función calcula el n-ésimo número de la serie, y para mostrarlos todos tenemos que hacer un ciclo que repita la función tantas veces como sea necesario.

Siguiendo con esto de la recursividad hoy les traigo un nuevo programín, Convertir Decimal a Binario de forma recursiva.

#include<stdio.h>
void binario(int n)
{
    if (n!=0)
    {
        binario(n/2);
        printf("%i",n%2);
    }
}
int main()
{
    int num=0;
    printf("::CONVERTIR DECIMAL A BINARIO::\n");
    printf("Introduce un numero: ");scanf("%i",&num); //Pedir variable num
    printf("\t");binario(num);printf("\n"); //Llamar la función
    return 0;
}

Está basado en el método que usamos para convertir un número decimal a binario “a mano”: dividir el número entre dos hasta que quede 0 y apuntar los residuos del último al primero.

Hola de nuevo, ¿cuánto tiempo pasó? mmm no sé pero bueno… lo importante es que ya estoy de vuelta y ahora sí me voy a dar el tiempo de actualizar este blog más seguido, pero basta de cosas personales.

No me quiero meter en rollos de explicar lo que es la recursividad (googleen y diviértanse leyendo), lo que quiero es mostrarles algunos ejemplos muy sencillos de dónde podemos aplicar la recursividad. Hoy toca calcular el factorial de un numero de forma recursiva.

Es el código recursivo más fácil que se pueden encontrar:

#include<stdio.h>
int factorial(int n)
{
  if(n<2)
    return 1;
  else
    return n * factorial(n-1);
}
int main()
{
  int num=0;
  printf("::CALCULAR FACTORIAL::\n");
  printf("Introduce un numero: ");scanf("%i",&num); //Pedir variable num
  printf("\tEl resultado es: %i\n", factorial(num)); //Llama la funcion e imprime resultado
  return 0;
}

Explicación

El caso base es que cuando n valga 1 o 0 retorna un 1, de lo contrario retorna la multiplicación de n * el factorial del numero anterior n-1. Supongamos que introducimos el número 3, cuyo factorial es 6 (3*2*1 = 6).

1. n=3 No entra al caso base. Guardamos para después la operación 3 * factorial(2)
2. n=2 No entra al caso base. Guardamos para después la operación 2 * factorial(1)
3. n=1 Entra al caso base. Retorna 1, por lo tanto factorial(1) = 1
4. Hacemos la última operación que guardamos 2 * factorial(1) = 2 * 1 = 2, por lo tanto factorial(2) = 2
5. Hacemos la siguiente operación que guardamos 3 * factorial(2) = 3 * 2 = 6
6. El factorial es 6

¡Uh que fácil!