Теоретическая часть

Пример 1. Напишите рекурсивную функцию определения наибольшего общего делителя двух целых чисел.
Программный код решения примера:
#include
#include
#include

// Прототип рекурсивной функции

int gcd(int a, int b);

int main (void) {

int a = 0, b = 0;
int in;

// Проверка ввода двух целых чисел

do {
printf("\n Enter the two different natural numbers, through the gap: ");
in = scanf_s("%d%d", &a, &b);

if (in != 2) {

printf("\n Error input. Press any key to exit: ");
_getch();
exit(1);
}

if ( (a != b) && (b != 0) )

break;
if (b == 0)
a = b;

} while ( (a == b) );

// Вывод результата на консоль

printf("\n a = %d, b = %d, GCD = %d; \n", a, b, gcd(a,b));

printf("\n\n Press any key: ");
_getch();
return 0;
}

// Определение рекурсивной функции

int gcd(int a, int b) {
if ( (a % b) == 0)
return b;
else
return gcd(b, a % b);
}
Решение примера выполнено на основе простой хвостовой рекурсии, поскольку значения вызовов функции самой себя gcd(b, a%b) возвращаются оператором return. В программе используется оператор % – операция остатка от деления двух целых чисел (целочисленное деление). Известно, что если даны два числа А и В, то максимальный остаток от деления числа А на число В будет на единицу меньше числа В. В определении рекурсивной функции gcd() условием останова является то, что остаток от деления двух данных чисел равен нулю. Рекурсивные вызовы функции gcd() связаны с изменением расположения первоначально заданных аргументов, когда аргумент, стоящий на втором месте ( b ), определяется на первом месте, а на втором месте определяется операция остатка от деления, т. е. a%b . И это происходит до тех пор, пока остаток от деления не станет равным нул ю, т. е. будет выполнено условие останова (базовое условие).
Возможный результат выполнения программы приведен на рис.