Encontrando o Máximo Divisor Comum Usando Recursão

Introdução

Em matemática, o máximo divisor comum (MDC) de dois números é comumente definido como o maior inteiro positivo que divide os dois números sem deixar resto. Neste laboratório, aprenderemos a escrever um programa em C para encontrar o MDC de dois números usando recursão.

Nota: Você precisa criar o arquivo ~/project/main.c por conta própria para praticar a codificação e aprender como compilar e executá-lo usando gcc.

cd ~/project
## create main.c
touch main.c
## compile main.c
gcc main.c -o main
## run main
./main

Lendo os números de entrada

Primeiramente, precisamos obter dois números inteiros de entrada do usuário para encontrar seu MDC. Usaremos a função scanf() para ler a entrada.

#include<stdio.h>

int main()
{
    int a, b;
    printf("Digite dois números para encontrar o MDC: \n");
    scanf("%d%d", &a, &b);
    // rest of the code
    return 0;
}

Definindo a função recursiva para encontrar o MDC

Usaremos uma função recursiva para encontrar o MDC dos dois números de entrada. A função recursiva terá dois parâmetros inteiros. A função continuará a se chamar até que os dois números tenham o mesmo valor e retornará esse valor como o MDC.

int find_gcd(int x, int y)
{
    if(x == y)
        return x;
    if(x > y)
        return find_gcd(x-y, y);
    return find_gcd(x, y-x);
}

Chamando a função recursiva da função principal

Nesta etapa, a função recursiva será chamada com os dois números de entrada (a e b). O valor de retorno da função recursiva será armazenado em uma variável inteira (gcd).

int gcd = find_gcd(a, b);
printf("GCD of %d and %d is: %d\n", a, b, gcd);

Código de exemplo completo

#include <stdio.h>

// declarando a função recursiva
int find_gcd(int, int);

int main()
{
    int a, b, gcd;
    printf("Digite dois números para encontrar o MDC de: \n");
    scanf("%d%d", &a, &b);
    gcd = find_gcd(a, b);
    printf("MDC de %d e %d é: %d\n", a, b, gcd);
    return 0;
}

// definindo a função
int find_gcd(int x, int y)
{
    if(x == y)
        return x;
    if(x > y)
        return find_gcd(x-y, y);
    return find_gcd(x, y-x);
}

Resumo

Neste laboratório, aprendemos a escrever um programa em C para encontrar o MDC (Máximo Divisor Comum) de dois números usando recursão. Utilizámos uma função recursiva para calcular o MDC, fazendo com que a função chamasse a si mesma com parâmetros de entrada modificados até atingir um caso base. Este programa pode ser usado para resolver problemas matemáticos que exigem o cálculo do MDC de dois números.