Написать рекурсивную функцию нахождения наибольшего общего делителя двух целых чисел - C (СИ)

Формулировка задачи:

Сделайте пожалуйста из моей обычной функции по нахождению НОДа

рекурсивную

#include <iostream>
#include <windows.h>
using namespace std;
 
char bufRus[256];
 
void main(void);
int nod(int, int);
char* Rus(const char*);
 
void main(void)
{
    cout << Rus("\t\tЗадание 2 к Домашнему заданию 4 к модулю 6.\n");
    cout << Rus("Написать рекурсивную функцию нахождения наибольшего общего делителя двух целых чисел.\n");
    int a, b;
    cout << (Rus("Введите первое число: \n "));
    cin >> a;
    while (a < 0)
    {
        cout << (Rus("\nОшибка: Число должно быть целым положительным. Будьте внимательны!!!"));
        cin >> a;
    }
    cout << (Rus("Введите второе число: \n"));
    cin >> b;
    while (b < 0)
    {
        cout << (Rus("\nОшибка: Число должно быть целым положительным. Будьте внимательны!!!"));
        cin >> b;
    }
    nod(a, b);
}
 
int nod(int a, int b)
{
    while (a && b)
    if (a >= b)
    {
        a %= b;
        cout << Rus("Наибольший общий делитель ваших чисел = ")<<b<<"\n";
    }
 
    else
    {
        b %= a;
        cout << Rus("Наибольший общий делитель ваших чисел = ") << a << "\n";
    }

    return a | b;
}
 
char* Rus(const char* text)
{
    CharToOemA(text, bufRus);
    return bufRus;
}

Решение задачи: «Написать рекурсивную функцию нахождения наибольшего общего делителя двух целых чисел»

Листинг программы

int gmd(int  a,int  b)
{
    if(!b) return a;
    return gmd(b,a%b);
}

Объяснение кода листинга программы

Входные параметры функции: a и b - два целых числа.
Проверка условия: если b равно 0, то возвращается значение a.
Если же b не равно 0, то происходит рекурсивный вызов функции gmd, но уже с параметрами b и (a % b).
Значение (a % b) представляет собой остаток от деления a на b.
Таким образом, в случае, если b не равно 0, функция gmd будет вызывать саму себя, пока не будет выполнено условие (b = 0).
Когда условие выполняется, функция возвращает значение a.
Функция gmd предназначена для нахождения наибольшего общего делителя (НОД) двух целых чисел.
Рекурсивный алгоритм нахождения НОД является одним из самых простых и эффективных алгоритмов.
Он основан на идее разложения обоих чисел на простые множители и поиска наибольшего общего делителя этих простых множителей.
Но в данном коде алгоритм упрощен до нахождения остатка от деления, что также является корректным решением, но не является наиболее эффективным.
Временная сложность данного алгоритма составляет O(log n), где n - это наибольшее из двух чисел.
Поэтому, если необходимо найти НОД двух больших чисел, то данная реализация может быть неэффективной и может привести к переполнению стека вызовов.
Однако, для небольших чисел, данная реализация может быть вполне приемлемой.
В данном коде нет использования каких-либо дополнительных библиотек или структур данных.
Код достаточно компактный и может быть использован в качестве самостоятельной функции или в составе другой функции.
Данный код может быть использован для решения различных задач, связанных с нахождением НОД, например, для проверки целочисленности делителей или для нахождения обратного элемента в кольце по модулю.
Важно отметить, что данная реализация не является единственной возможной и существуют и другие алгоритмы для нахождения НОД.
Например, алгоритм Евклида, который также основан на рекурсии, но использует дополнительную переменную для хранения последнего ненулевого делителя.
В данном коде не предусмотрена обработка ошибок, например, если входные значения отрицательны или превышают максимальное значение для типа данных int.
Также в данном коде не предусмотрена оптимизация для ускорения работы алгоритма, например, использование таблицы предварительно вычисленных значений НОД для небольших чисел.