Recursividad aplicada: Máximo Común Divisor

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
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: %in", 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.

18 thoughts on “Recursividad aplicada: Máximo Común Divisor

  1. Ese codigo es c y en c++ es el siguiente:

    #include

    using namespace std;

    int MCD(int x, int y)
    {
    if(y==0)
    return x;
    else
    return MCD(y, x%y);
    }
    int main()
    {
    int a=0,b=0;
    cout<>a;
    cout<<"n";

    cout<>b;
    cout<<"n";

    cout<<"El resultado es:"<< MCD(a, b)<<"n";

    return 0;

    }

    1. mmmm nose pk no salio bn lo ke pegue :S

      int a=0,b=0;

      cout<>a;
      cout<<"n";

      cout<>b;
      cout<<"n";

      cout<<"El resultado es:"<< MCD(a, b)<<"n";

      return 0;

  2. Es el algoritmo de uclides : el MCD de dos números también divide al resto obtenido de dividir el mayor entre el más pequeño. lol esta en wiki

    divide y venceras

  3. Falta poner

    if(num1<num2){
    aux=num1;
    num1=num2;
    num2=aux;
    }
    antes de la llamada a la funcion para ordenar los numeros de mayor a menor

    el cartero siempre llama 2 veces

  4. Este algoritmo fue diseñado por el matemático griego Euclides, mejor conocido como “El padre de la Geometría”. Aplica eficazmente el concepto de recursividad. Para entenderlo mejor se puede hace una prueba de escritorio, veamos:

    MCD(11, 3) = 1

    x y
    11 3
    3 11-3*3
    2 3-2
    1 0

    Como y==0 entonces la respuesta es 1. Claro 1 es el máximo común divisor entre los números primos 11 y 3.

  5. En realidad el codigo no funciona por pura “rana”..
    Lo estuve analizando, y si se realiza la prueba de escritorio cumple
    con las espectativas dadas…
    Aunque admito que esta muy ingenioso por parte del creador…

  6. Hola….le capto el codigo, pero si coloca al primer valor 5 y al segundo 20…porque cumple la parte de 5%20….esto aun no lo entiendo?

  7. voy a decirles a todos una cosa, porfavor aprendan a escribir un codigo limpio y entendible, dejense de aux, a, b y denles nombres que los representen. soy un estudiante de primero de carrera de informatica y matematicas, y me alegro de no haber programado antes y estar haciendolo bien, para algun dia ser un programador de provecho. Quejas aparte, un gran aporte si señor.

  8. deben entender la operación resto:
    20 % 5 = 0 (porque 20/5 es 4 resto 0)
    5 % 20 = 5 (porque 5/20 es 0 resto 5)
    por lo que en el algoritmo pasamos los sigueintes parámetros

    x y
    5 20
    20 5
    5 0
    retorna el valor 5!!!!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s