Programação C | Cálculo do MMC | Recursão

Introdução

Neste laboratório, vamos escrever um programa em C para encontrar o MMC (Mínimo Múltiplo Comum - LCM, em inglês) de dois números usando recursão. O MMC é o menor inteiro positivo que é divisível por ambos os números sem deixar resto.

Entenda o conceito de MMC

Antes de começarmos com a programação, vamos entender o conceito de MMC. O MMC de dois inteiros é o menor inteiro positivo que é um múltiplo de ambos os números. Para encontrar o MMC de dois números, podemos usar a seguinte fórmula:

MMC = (número1 * número2) / MDC

Onde número1 e número2 são os dois números para os quais precisamos encontrar o MMC e MDC é o Máximo Divisor Comum (Greatest Common Divisor - GCD, em inglês) dos dois números.

Crie um novo arquivo C

Vamos criar um novo arquivo C chamado main.c no diretório ~/project/ onde escreveremos nosso programa.

Escreva o código

Copie e cole o seguinte código no arquivo main.c.

#include<stdio.h>

int find_lcm(int, int); // declaração do protótipo da função

int main()
{
    int a, b, lcm;
    printf("Digite dois inteiros para encontrar o MMC:\n");
    scanf("%d %d", &a, &b);
    lcm = find_lcm(a, b); // chamada da função
    printf("MMC de %d e %d é %d.\n", a, b, lcm);

    return 0;
}

int find_lcm(int a, int b) // definição da função
{
    static int temp = 1;
    if(temp % a == 0 && temp % b == 0)
        return temp;
    else
    {
        temp++;
        find_lcm(a, b);
        return temp;
    }
}

Compile e execute o programa

Salve o arquivo main.c e compile o programa usando o seguinte comando no terminal:

gcc main.c -o main

Execute o programa usando o seguinte comando:

./main

Insira dois inteiros quando solicitado e o programa exibirá o MMC dos dois números.

Entenda o código

Vamos entender o código que acabamos de escrever.

Primeiro, incluímos a biblioteca padrão de entrada e saída em nosso programa usando #include<stdio.h>.
Declaramos o protótipo da função find_lcm, que definiremos mais tarde em nosso programa. Isso é necessário porque estamos chamando a função find_lcm em nossa função principal antes de sua definição real.
Na função principal, declaramos três variáveis inteiras a, b e lcm.
Solicitamos ao usuário que insira dois inteiros usando printf e aceitamos a entrada usando scanf.
Em seguida, chamamos a função find_lcm e passamos a e b como seus argumentos.
A função find_lcm recebe dois argumentos inteiros a e b e retorna o MMC dos dois números usando recursão.
Inicializamos uma variável estática temp com 1, que manterá o valor atual que estamos verificando para um múltiplo.
Em cada recursão, verificamos se temp é um múltiplo de a e b.
Se for um múltiplo, retornamos temp como o MMC.
Se não for um múltiplo, incrementamos temp e chamamos a função find_lcm recursivamente até encontrarmos o MMC.

Teste o programa

Teste o programa com diferentes valores de entrada e verifique se ele produz a saída do MMC correta.

Código completo

Aqui está o código completo para o Programa C para encontrar o MMC de dois números usando recursão:

#include<stdio.h>

int find_lcm(int, int); // declaração do protótipo da função

int main()
{
    int a, b, lcm;
    printf("Digite dois inteiros para encontrar o MMC:\n");
    scanf("%d %d", &a, &b);
    lcm = find_lcm(a, b); // chamada da função
    printf("MMC de %d e %d é %d.\n", a, b, lcm);

    return 0;
}

int find_lcm(int a, int b) // definição da função
{
    static int temp = 1;
    if(temp % a == 0 && temp % b == 0)
        return temp;
    else
    {
        temp++;
        find_lcm(a, b);
        return temp;
    }
}

Resumo

Neste laboratório, aprendemos como escrever um programa C para encontrar o MMC de dois números usando recursão. Usamos uma função recursiva para encontrar o MMC e explicamos cada etapa do programa em detalhes. Também aprendemos como compilar e executar um programa C usando o terminal.

Cálculo do MMC Recursivo em C