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<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.