Recursive algorithm

Question

I have a job at college that I just have no idea where to start.

Display the recursive mathematical function that defines mdc (maximum common divisor) between two natural. Based on it, do: 1. Define a recursive algorithm to compute mdc and illustrate it with at least one computer example.

Can someone translate this text for me? Because I don’t know what to do..

Answer 1

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

Example of Computation (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 just translate the function calcularMdc in portugol, flowchart, or something like that. I think that’s what your teacher is wanting. Anything take 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 side exchange of the parameters, which is always replacing, until the condition is reached.