Вычисление НОД - в чем преимущество рекурсивного подхода перед нерекурсивным? - C (СИ)

Узнай цену своей работы

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

Даны натуральные числа n, m; найти НОД(n, m). Использовать программу, включающую рекурсивную процедуру вычисления НОД, основанную на соотношении НОД(n, m) = НОД(m, r)- остаток от деления n на m. Чем эта программа хуже нерекурсивной программы вычисления НОД(n, m)? Помогите, пожалуйста, ни как не могу разобраться.

Решение задачи: «Вычисление НОД - в чем преимущество рекурсивного подхода перед нерекурсивным?»

textual
Листинг программы
#include <iostream.h>
 
int GCD(int n, int m)
{
    if (m > n) 
        return GCD(m,n);
    else
        if (m == 0)
            return n;
        else
            return GCD(m, n % m);
}
 
int main(int argc, char* argv[])
{
 
    cout << GCD(42,14) << endl;       // вывод 14
    cout << GCD(1024,768) << endl;  // вывод 256
    return 0;
}

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

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

  1. Входные данные: В функции main мы передаем два целых числа в функцию GCD через аргументы командной строки.
  2. Рекурсивный подход: Функция GCD написана с использованием рекурсии. Рекурсия - это процесс, когда функция вызывает саму себя. В этом коде, если m больше n, то функция GCD вызывает саму себя с аргументами m и n. Это продолжается до тех пор, пока m не станет меньше или равным n. Когда это произойдет, функция начинает возвращать значения вверх по рекурсивной лестнице, пока не вернется в основную программу.
  3. Нерекурсивный подход: В этом коде, если m меньше или равно n, то функция начинает анализировать значения m и n поочередно. Если m равно 0, то n возвращается как результат. В противном случае, функция вызывает саму себя с аргументами m и n % m, где % - это оператор взятия остатка от деления. Этот процесс продолжается до тех пор, пока m не станет равным 0.
  4. Вывод: В функции main мы вызываем функцию GCD дважды и выводим результаты. Первый вызов возвращает НОД(42, 14) = 14, а второй вызов возвращает НОД(1024, 768) = 256. Преимущество рекурсивного подхода заключается в его простоте и лаконичности. Он требует меньше кода и легче читается. Однако, он может быть менее эффективным, особенно для больших чисел, поскольку рекурсия может привести к большому количеству повторных вычислений. Нерекурсивный подход, напротив, требует больше кода, но он может быть более эффективным, поскольку он избегает повторных вычислений. Он также может быть полезен в случаях, когда рекурсия вызывает проблемы с памятью или переполнением стека.

Оцени полезность:

11   голосов , оценка 4.091 из 5
Похожие ответы