Recursive Algorithm

Well, recursively the code gets pretty small; remembering that the recursion must have a return value that stops it if that value is reached, otherwise, the recursion will continue to make the substitution (also remembering that, in the substitution, some value should change, otherwise there is an infinite loop risk .):

Computing example (Java code, for example):

import java.util.Scanner;

public class MDC{

    public static void main(String[] args) {

        Scanner input = new Scanner(System.in);

        int a, b;

        System.out.print("Digite dois inteiros: ");

        a = input.nextInt();
        b = input.nextInt();

        System.out.printf("Máximo divisor comum: %d\n", calcularMdc(a, b));
    }

    static int calcularMdc(int a, int b){

        // Se o novo valor tiver módulo zero, 
        // imprime b("a" depois da primeira vez)
        if ( a == 0 ) 
            return b;

        // Substitui na função, em "a",
        // o valor do resto da divisão de "b" por "a",
        // pois enquanto esse resto não for zero, e também
        // "a" não zerar ele irá continuar o loop.
        // (pois para iteração anteiror, o valor de "a"
        //  será o menor possível, portanto a fração a maior possível)
        return calcularMdc( b % a, a );
    }
}

For the algorithm it is enough to translate the calcularMdc function into Portuguese, flowchart, or something like that. I think that's what your teacher wants. Anything carry the code.

It is interesting to note, still in the code, that the values can be inserted in any order, because in the recursive call there is a change of side of the parameters, which is always being replaced until the condition is reached.