Нахождение наибольшего общего делителя с использованием рекурсии

Введение

В математике наибольший общий делитель (НОД) двух чисел обычно определяется как наибольшее положительное целое число, которое делит эти два числа без остатка. В этом практическом занятии мы научимся писать программу на C для нахождения НОД двух чисел с использованием рекурсии.

Примечание: вам нужно самостоятельно создать файл ~/project/main.c, чтобы практиковаться в написании программ и изучать процесс компиляции и запуска программы с использованием gcc.

cd ~/project
## создать main.c
touch main.c
## скомпилировать main.c
gcc main.c -o main
## запустить main
./main

Чтение входных чисел

Сначала нам нужно получить от пользователя два целых числа для нахождения их НОД. Мы будем использовать функцию scanf() для чтения входных данных.

#include<stdio.h>

int main()
{
    int a, b;
    printf("Введите два числа, чтобы найти их НОД: \n");
    scanf("%d%d", &a, &b);
    // остальной код
    return 0;
}

Определение рекурсивной функции для нахождения НОД

Мы будем использовать рекурсивную функцию для нахождения НОД двух введенных чисел. Рекурсивная функция будет иметь два параметра целого типа. Функция будет продолжать вызывать себя, пока два числа не станут равными, и возвращать это значение в качестве НОД.

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

Вызов рекурсивной функции из главной функции

В этом шаге рекурсивная функция будет вызвана с двумя входными числами (a и b). Возвращаемое значение рекурсивной функции будет сохранено в целочисленную переменную (gcd).

int gcd = find_gcd(a, b);
printf("НОД от %d и %d равен: %d\n", a, b, gcd);

Полный пример кода

#include <stdio.h>

// объявление рекурсивной функции
int find_gcd(int, int);

int main()
{
    int a, b, gcd;
    printf("Введите два числа, чтобы найти их НОД: \n");
    scanf("%d%d", &a, &b);
    gcd = find_gcd(a, b);
    printf("НОД от %d и %d равен: %d\n", a, b, gcd);
    return 0;
}

// определение функции
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);
}

Резюме

В этом практическом занятии мы научились писать программу на C для нахождения НОД двух чисел с использованием рекурсии. Мы использовали рекурсивную функцию для вычисления НОД, вызывая функцию самой себя с измененными входными параметрами, пока не достигнем базового случая. Эта программа может быть использована для решения математических задач, требующих вычисления НОД двух чисел.