SoloCodigo

Hola phoenix, aqui tienes los dos algoritmos que buscabas (bueno, uno pero en sus dos versiones). Imagino que funcionan, el no recursivo lo he probado, compilado, utilizado, etc. y funciona bien. El recursivo no lo he probado (me parece bastante inutil teniendo el otro) pero imagino que tambien funciona (sino funciona dilo). Te lo paso en pseudocodigo, imagino que lo sabras pasar a C, sino dimelo.

Saludos.

funcion mcd(a:entero, b:entero):entero
inicio
mientras ( a != b )   
   si ( a > b )
      a = a - b
   sino
      b = b - a
   fin si
fin mientras
retorna (a)
fin

funcion mcd(a:entero , b:entero):entero
inicio
si (a = b)
   retorna (a)
sino
   si (a > b)
      retorna (mcd(a-b, b))
   sino
      retorna (mcd(a , b-a))
   fin si
fin si
fin

me parece extraño que no te funcionase y mas que siempre te de uno (quiza es que todos las pruebas que has hecho las has hecho con numeros coprimeros). Lo acabo de compilar (con gcc pero debe funcionar en todos, es codigo ANSI C) y ha funcionado perfectamente. No se que puede haber pasado. Aqui te mando mi codigo, pero es exactamente igual. Tambien he probao el tuyo (cambiando el cout y cin por printf y scanf) y funciona perfectamente. Pos no se. Prueba de compilar esto y te debe funcionar.

Saludos.

#ifdef HAVE_CONFIG_H
#include <config.h>
#endif

#include <stdio.h>
#include <stdlib.h>

int mcd(int a, int b);

int main(int argc, char *argv[])
{
   int a, b;
   printf("Introduce el primer numero: ");
   scanf("%d", &a);
   printf("nIntroduce el segundo numero: ");
   scanf("%d", &b);
   printf("nEl mcd de %d y %d es: %d", a,b,mcd(a,b));
   return EXIT_SUCCESS;
}

int mcd(int a, int b)
{
   while (a != b)
   {
      if (a > b)
         a = a - b;
      else
         b = b - a;
   }
   return a;
}

en el siguiente enlace puedes ver el algoritmo de euclides implementado en C++ , saludos
site-informatica.blogspot.com/2010/09/algoritmo-de-euclides.html