Encontrar el máximo común divisor usando recursividad

Introducción

En matemáticas, el máximo común divisor (MCD) de dos números se define comúnmente como el mayor número entero positivo que divide a los dos números sin dejar un residuo. En este laboratorio, aprenderemos a escribir un programa en C para encontrar el MCD de dos números usando recursión.

Nota: Necesitarás crear el archivo ~/project/main.c tú mismo para practicar la codificación y aprender cómo compilar y ejecutarlo usando gcc.

cd ~/project
## crear main.c
touch main.c
## compilar main.c
gcc main.c -o main
## ejecutar main
./main

Leyendo los números de entrada

Primero, necesitamos tomar dos números de entrada enteros del usuario para encontrar su MCD. Usaremos la función scanf() para leer la entrada.

#include<stdio.h>

int main()
{
    int a, b;
    printf("Enter two numbers to find GCD of: \n");
    scanf("%d%d", &a, &b);
    // rest of the code
    return 0;
}

Definiendo la función recursiva para encontrar el MCD

Usaremos una función recursiva para encontrar el MCD de los dos números de entrada. La función recursiva tendrá dos parámetros enteros. La función continuará llamándose a sí misma hasta que dos números tengan el mismo valor y devolverá ese valor como el MCD.

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);
}

Llamando a la función recursiva desde la función principal

En este paso, se llamará a la función recursiva con los dos números de entrada (a y b). El valor de retorno de la función recursiva se almacenará en una variable entera (mcd).

int gcd = find_gcd(a, b);
printf("MCD de %d y %d es: %d\n", a, b, gcd);

Código de ejemplo completo

#include <stdio.h>

// declarando la función recursiva
int find_gcd(int, int);

int main()
{
    int a, b, gcd;
    printf("Ingrese dos números para encontrar su MCD: \n");
    scanf("%d%d", &a, &b);
    gcd = find_gcd(a, b);
    printf("MCD de %d y %d es: %d\n", a, b, gcd);
    return 0;
}

// definiendo la función
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);
}

Resumen

En este laboratorio, aprendimos a escribir un programa en C para encontrar el MCD de dos números usando recursividad. Utilizamos una función recursiva para calcular el MCD haciendo que la función se llame a sí misma con parámetros de entrada modificados hasta que alcanza un caso base. Este programa se puede utilizar para resolver problemas matemáticos que requieren el cálculo del MCD de dos números.