Понимание рекурсии

@Mnemonik39 · Регистрация: 06.12.2015

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

Ребята. Подскажите как можно понять рекурсию. Плотно застрял нна рекурсивных алгоритмах. Никак не могу понять принцип.
Пытался рисовать дерево рекурсивных вызовов, чтобы предугадать работу алгоритма, но увы не получается. Есть какие-то способы вникнуть в неё?

@kolorotur · 06.04.2018, 16:50

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

Плотно застрял нна рекурсивных алгоритмах. Никак не могу понять принцип.

Вам непонятен сам принцип рекурсии или у вас сложности с написанием алгоритмов?

@Wolfdp · 06.04.2018, 16:56

Mnemonik39,
давайте на примере: решаемая задача, (не)ваш код, и какие моменты не понятны. А то у меня чешутся руки скопипастить википедию...

@Mnemonik39 · 06.04.2018, 22:35 **[ТС]**

Добрый день!

Например возникает сложность с пониманием данного кода:

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
using System;
 
namespace RosenbrokeNethod
{
    
    public class Program
    {
        static void MakeSubsets(bool[] subset, int position)
        {
            if (position == subset.Length)
            {
                foreach (var e in subset)
                    Console.Write(e ? 1 : 0);
                Console.WriteLine();
                return;
            }
            subset[position] = false;
            MakeSubsets(subset, position + 1);
            
            subset[position] = true;
            MakeSubsets(subset, position + 1);
        }
 
        public static void Main()
        {
            MakeSubsets(new bool[4], 0);
        }   
    }
}

Я не понимаю как строится дерево рек. вызовов для данного метода, а также не понимаю как происходит стек вызовов.
Когда бегаю отладчиком по коду - то начинаю путаться какой контекст метода вызывается на тот или иной момент

@Wolfdp · 06.04.2018, 23:03

Mnemonik39, не плохо к коду приводить описание, что он должен делать.

по сути нужно акцентировать внимание на двух вещах:
-- как программа дойдет до "нижнего" уровня.
-- что она будет делать по возращению.

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

как строится дерево

i = 0
set [0] true
Method i + 1 (1)
- i = 1
- set [1] true
- Method i + 1 (2)
- - i = 2
- - set [2] true
- - Method i + 1 (3)
- - - i = 3
- - - set [3] true
- - - Method i + 1 (4)
- - - - Print [0] [1] [2] [3]
- - - set [3] false
- - - Method i + 1 (4)
- - - - Print [0] [1] [2] [3]
- - set [2] false
- - Method i + 1 (3)
- - - i = 3
- - - set [3] true
- - - Method i + 1 (4)
- - - - Print [0] [1] [2] [3]
- - - set [3] false
- - - Method i + 1 (4)
- - - - Print [0] [1] [2] [3]

и т.д...

@kolorotur · 07.04.2018, 00:18

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

Я не понимаю как строится дерево рек. вызовов для данного метода

А как строится дерево обычных вызовов — понимаете?

@Mnemonik39 · 07.04.2018, 00:47 **[ТС]**

Код выведет такую таблицу:
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111

Честно говоря - не совсем понятна Ваша схема по вызовам. Учитывая то, что тут в методе он вызывает сам себя - 2 раза.
Меня больше путает то, в какой последовательности он вызывается

@kolorotur · 07.04.2018, 00:53

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

Меня больше путает то, в какой последовательности он вызывается

Допустим, есть такая цепочка вызовов:

C#
1
2
3
4
5
6
7
8
9
10
void Foo(bool[] a)
{
   a[0] = true;
   Bar(a, 1);
}
 
void Bar(bool[] a, int p)
{
   a[p] = false;
}

В примере выше у вас не возникает проблем с отслеживанием цепочки вызовов и того, что происходит с массивом?

@Mnemonik39 · 07.04.2018, 08:48 **[ТС]**

В вашем примере нет - все крайне понятно

@kolorotur · 07.04.2018, 11:20

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

все крайне понятно

Отлично!
Значит вы понимаете что происходит при вызове функции/метода: выделяется память под локальные переменные и формальные параметры, в память под параметры записываются значения передаваемых аргументов, выполнение переходит в тело метода, по его окончании локальные удаляются и управление переходит обратно в точку вызова предыдущего метода.

Давайте перепишем ваш пример под аналогичный моему — без рекурсии:

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
using System;
 
namespace RosenbrokeNethod
{
 
    public class Program
    {
        static void MakeSubsets1(bool[] subset, int position)
        {
            if (position == subset.Length)
            {
                foreach (var e in subset)
                    Console.Write(e ? 1 : 0);
                Console.WriteLine();
                return;
            }
            subset[position] = false;
            MakeSubsets2(subset, position + 1);
 
            subset[position] = true;
            MakeSubsets2(subset, position + 1);
        }
 
        static void MakeSubsets2(bool[] subset, int position)
        {
            if (position == subset.Length)
            {
                foreach (var e in subset)
                    Console.Write(e ? 1 : 0);
                Console.WriteLine();
                return;
            }
            subset[position] = false;
            MakeSubsets3(subset, position + 1);
 
            subset[position] = true;
            MakeSubsets3(subset, position + 1);
        }
 
        static void MakeSubsets3(bool[] subset, int position)
        {
            if (position == subset.Length)
            {
                foreach (var e in subset)
                    Console.Write(e ? 1 : 0);
                Console.WriteLine();
                return;
            }
            subset[position] = false;
            MakeSubsets4(subset, position + 1);
 
            subset[position] = true;
            MakeSubsets4(subset, position + 1);
        }
 
        static void MakeSubsets4(bool[] subset, int position)
        {
            if (position == subset.Length)
            {
                foreach (var e in subset)
                    Console.Write(e ? 1 : 0);
                Console.WriteLine();
                return;
            }
            subset[position] = false;
            MakeSubsets5(subset, position + 1);
 
            subset[position] = true;
            MakeSubsets5(subset, position + 1);
        }
 
        static void MakeSubsets5(bool[] subset, int position)
        {
            if (position == subset.Length)
            {
                foreach (var e in subset)
                    Console.Write(e ? 1 : 0);
                Console.WriteLine();
                return;
            }
        }
 
        public static void Main()
        {
            MakeSubsets1(new bool[4], 0);
        }
    }
}

Работа данного примера не вызывает сложностей в понимании происходящего?
Там обычная цепочка вызовов, без рекурсии.

@Mnemonik39 · 07.04.2018, 23:13 **[ТС]**

Да, спасибо за конструктивный подход. Тут тоже пока все понятно. Просто иногда запутывает это хитросплетение вызовов методов. Продолжайте)

@kolorotur · 08.04.2018, 00:23

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

Тут тоже пока все понятно.

У вышеприведенной конструкции есть два недостатка:
1. Из-за ограниченного количества методов алгоритм применим к массивам размером не более 4.
2. Пять раз повторяется один и тот же код.

Первую проблему можно решить, если оставить только два метода, которые будут вызывать друг друга, но не будут вызывать себя сами. То есть (прямой) рекурсии нет:

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
using System;
 
namespace RosenbrokeNethod
{
 
    public class Program
    {
        static void MakeSubsets1(bool[] subset, int position)
        {
            if (position == subset.Length)
            {
                foreach (var e in subset)
                    Console.Write(e ? 1 : 0);
                Console.WriteLine();
                return;
            }
            subset[position] = false;
            MakeSubsets2(subset, position + 1);
 
            subset[position] = true;
            MakeSubsets2(subset, position + 1);
        }
 
        static void MakeSubsets2(bool[] subset, int position)
        {
            if (position == subset.Length)
            {
                foreach (var e in subset)
                    Console.Write(e ? 1 : 0);
                Console.WriteLine();
                return;
            }
            subset[position] = false;
            MakeSubsets1(subset, position + 1);
 
            subset[position] = true;
            MakeSubsets1(subset, position + 1);
        }
 
        public static void Main()
        {
            MakeSubsets1(new bool[4], 0);
        }
    }
}

Опять никакой рекурсии, производятся обычные вызовы метода, но не устранена вторая проблема: повторение кода — у нас два метода, котрые делают одно и то же.
Почему бы в этом случае не пойти чуть дальше и не убрать дублирующий метод — зачем он нужен, если уже есть один метод, который делает то же самое?

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
using System;
 
namespace RosenbrokeNethod
{
 
    public class Program
    {
        static void MakeSubsets1(bool[] subset, int position)
        {
            if (position == subset.Length)
            {
                foreach (var e in subset)
                    Console.Write(e ? 1 : 0);
                Console.WriteLine();
                return;
            }
            subset[position] = false;
            MakeSubsets1(subset, position + 1);
 
            subset[position] = true;
            MakeSubsets1(subset, position + 1);
        }
 
        public static void Main()
        {
            MakeSubsets1(new bool[4], 0);
        }
    }
}

Вот и получилась великая и ужасная рекурсия.
В общем, не позволяйте себя запутать фразам вроде "метод вызывает сам себя".
Это обычный вызов метода, который работает точно так же, как вызов абсолютно любого другого метода — с теми же механизмами перехода и возвращением в место вызова после окончания.
Просто на каждом вызове выполняются одни и те же действия, а раз они одни и те же, то зачем плодить триллион раз методы с одним и тем же кодом?

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве 8Observer8 02.02.2026 Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .	Философия технологии iceja 01.02.2026 На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .	SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf 8Observer8 01.02.2026 Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .	SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли 8Observer8 30.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .
SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm 8Observer8 30.01.2026 Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .	SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 29.01.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .	Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT bedvit 28.01.2026 Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .	SDL3 для Android: Загрузка PNG с альфа-каналом с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 28.01.2026 Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .

Понимание рекурсии

Решение

Решение

@Mnemonik39 24 / 6 / 3 Регистрация: 06.12.2015 Сообщений: 319

	Понимание рекурсии 06.04.2018, 13:22. Показов 2333. Ответов 11 Метки нет (Все метки) Ребята. Подскажите как можно понять рекурсию. Плотно застрял нна рекурсивных алгоритмах. Никак не могу понять принцип. Пытался рисовать дерево рекурсивных вызовов, чтобы предугадать работу алгоритма, но увы не получается. Есть какие-то способы вникнуть в неё? 0

@Wolfdp 3790 / 1767 / 371 Регистрация: 15.06.2012 Сообщений: 6,543 Записей в блоге: 3
	06.04.2018, 16:56
	Mnemonik39, давайте на примере: решаемая задача, (не)ваш код, и какие моменты не понятны. А то у меня чешутся руки скопипастить википедию... 0

@Mnemonik39 24 / 6 / 3 Регистрация: 06.12.2015 Сообщений: 319
	07.04.2018, 00:47 [ТС]
	Код выведет такую таблицу: 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111 Честно говоря - не совсем понятна Ваша схема по вызовам. Учитывая то, что тут в методе он вызывает сам себя - 2 раза. Меня больше путает то, в какой последовательности он вызывается 0

@Mnemonik39 24 / 6 / 3 Регистрация: 06.12.2015 Сообщений: 319
	07.04.2018, 08:48 [ТС]
	В вашем примере нет - все крайне понятно 0

@Mnemonik39 24 / 6 / 3 Регистрация: 06.12.2015 Сообщений: 319
	07.04.2018, 23:13 [ТС]
	Да, спасибо за конструктивный подход. Тут тоже пока все понятно. Просто иногда запутывает это хитросплетение вызовов методов. Продолжайте) 0