Объясните, как работает рекурсия в коде, по нахождению НОД

@Jagario · Регистрация: 08.07.2017

Студворк — интернет-сервис помощи студентам

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int nod(int x, int y)
{
   if(x == 0)
      return y;
   else if(y == 0)
      return x;
   else if(x == y)
      return x;
   else if(x == 1 || y == 1)
      return 1;
   else if(x % 2 == 0 && y % 2 == 0)
      return 2 * nod(x / 2, y / 2) //1 рекурсия
   else if(x % 2 == 0 && y % 2 != 0)
      return nod(x / 2, y); //2 рекурсия
   else if(x % 2 != 0 && y % 2 == 0)
      return nod(x, y / 2); //3 рекурсия
   else if(x % 2 != 0 && y % 2 != 0)
      return nod(y, abs(y - x)); //4 рекурсия
}

Можете подробнее разжевать по какому принципу работают эти 4 рекурсии?
Ну то есть, я не пойму где они останавливаются, и как начинаются.
Допустим вызываем первую (x = 18; y = 48): 2 * nod (18/2;48/2) - > 2 * nod (9/2;24/2) -> 2 * nod (и тут кстати не понятно 5 или 4/2;12/2) - > 2 * nod (2/2; 6/2) -> 2 * nod (1;3) И что дальше? По условию else if(x == 1 || y == 1) мы возвращаем 1. Но я не пойму в хили у. И продолжается ли рекурсия дальше, делим ли мы 3 на два, или х и у нас становятся 1? Или 1 возвращается только у х, а рекурсия продолжается, пока y не достигнет 0 или 1? Короче, ничего не понятно.

Nishen · 02.08.2017, 12:54

Мы возвращаем единицу не в x, и не в y. Мы возвращаем результат в то место, откуда был произведен вызов функции.
Нет, не продолжается, когда достигается условие

C++
1
if(x == 1 || y == 1)

происходит передача значения в точку вызова и будет происходить столько раз, сколько раз происходил рекурсивный вызов.

@Azazel-San · 02.08.2017, 12:56

Сообщение от Jagario

Но я не пойму в хили у

в условии же написано что как только x или y буду равны 0

Сообщение от Jagario

И продолжается ли рекурсия дальше

если условие выполнилось - нет, и мы переходим к следующей итерации или же на выход из ф-и

Сообщение от Jagario

делим ли мы 3 на два

ну смотрите по условию , все же написано, если число делится нацело, тогда делим

C++
1
2
3
4
5
6
7
8
9
10
11
12
//пример
 recursion(int n) 
    {
        // условие выхода
        // Базовый случай
        // когда остановиться повторять рекурсию ?
        if (n == 1) {
            return 1;
        }
        // Шаг рекурсии / рекурсивное условие
        return recursion(n - 1) * n;
    }

Новые блоги и статьи Все статьи Все блоги /
My Business CRM MaGz GoLd 16.04.2026 Всем привет, недавно возникла потребность создать CRM, для личных нужд. Собственно программа предоставляет из себя базу данных клиентов, в которой можно фиксировать звонки, стадии сделки, а также. . .	Знаешь почему 90% людей редко бывают счастливыми? kumehtar 14.04.2026 Потому что они ждут. Ждут выходных, ждут отпуска, ждут удачного момента. . . а удачный момент так и не приходит.	Фиксация колонок в отчете СКД Maks 14.04.2026 Фиксация колонок в СКД отчета типа Таблица. Задача: зафиксировать три левых колонки в отчете. Процедура ПриКомпоновкеРезультата(ДокументРезультат, ДанныеРасшифровки, СтандартнаяОбработка) / / . . .	Настройки VS Code Loafer 13.04.2026 { "cmake. configureOnOpen": false, "diffEditor. ignoreTrimWhitespace": true, "editor. guides. bracketPairs": "active", "extensions. ignoreRecommendations": true, . . .
Оптимизация кода на разграничение прав доступа к элементам формы Maks 13.04.2026 Алгоритм из решения ниже реализован на нетиповом документе, разработанного в конфигурации КА2. Задачи, как таковой, поставлено не было, проделанное ниже исключительно моя инициатива. Было так:. . .	Контроль заполнения и очистка дат в зависимости от значения перечислений Maks 12.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: реализовать контроль корректности заполнения дат назначения. . .	Архитектура слоя интернета для сервера-слоя. Hrethgir 11.04.2026 В продолжение https:/ / www. cyberforum. ru/ blogs/ 223907/ 10860. html Знаешь что я подумал? Раз мы все источники пишем в голове ветки, то ничего не мешает добавить в голову такой источник, который сам. . .	Подстановка значения реквизита справочника в табличную часть документа Maks 10.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача №1: при указании работ (справочник РаботыПоРемонтуСпецтехники),. . .