В этой статье мы разберём к чему может привести необдуманное использование рекурсии, а также способ её преобразования к итерации.
Задача
Итак, нам дана следующая матрица
Наша задача — вычислить максимальное количество стоящих рядом элементов с одинаковыми значениями. То есть, программа должна в данном случае выдать число 4. Для решения нам вполне хватит консольного приложения на 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 |
using System; namespace RecurseToIteration { class Program { // Размеры матрицы const int m_height = 3; const int m_width = 4; // Общие данные, с которыми работают рекурсивные методы static bool[,] visitMatrix; static int[,] valueMatrix; static int targetValue; static void Main(string[] args) { // Начальная матрица valueMatrix = new int[m_height, m_width] { {0, 1, 1, 1}, {0, 1, 3, 3}, {2, 2, 3, 1} }; // Создадим матрицу, чтобы знать какие ячейки уже были посещены visitMatrix = new bool[m_height, m_width]; int maxCount = 0; for (int i = 0; i < m_height; i++) { for (int j = 0; j < m_width; j++) { // Пройдемся по всем ячейкам матрицы и запустим рекурсии // для ячеек, которые еще не были обработаны if (visitMatrix[i, j] == false) { // Вынесем искомое значение в статическое поле, // чтобы не передавать много аргументов в рекурсивный метод targetValue = valueMatrix[i, j]; // Обновим найденный максимум, если полученное значение больше int nextCount = RecurseMethod(i, j); maxCount = nextCount > maxCount? nextCount : maxCount; } } } Console.WriteLine($"Max: {maxCount}"); Console.ReadKey(); } static int RecurseMethod(int h, int w) { // Условия выхода из рекурсии: // 1. Неверные границы // 2. Ячейка уже была посещена // 3. Значение в ячейке не равно искомому if (h < 0 || w < 0 || h >= m_height || w >= m_width || visitMatrix[h, w] || valueMatrix[h, w] != targetValue) { return 0; } // Запомним, что ячейка была посещена и зададим начальную сумму равной 1 visitMatrix[h, w] = true; int sum = 1; // Рекурсивно продолжим обход всех клеток, попутно увеличивая сумму sum += RecurseMethod(h + 1, w); sum += RecurseMethod(h - 1, w); sum += RecurseMethod(h, w + 1); sum += RecurseMethod(h, w - 1); return sum; } } } |
Результат работы программы:
Проблема
И вроде бы всё хорошо, ломаться тут нечему. Давайте увеличим размер матрицы до 100 на 100 и уберем первоначальную инициализацию. То есть у нас будет матрица 100×100, заполненная нулями. По логике программа должна выдать число 10000.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
// Размеры матрицы const int m_height = 100; const int m_width = 100; ... // Начальная матрица valueMatrix = new int[m_height, m_width]; /*{ {0, 1, 1, 1}, {0, 1, 3, 3}, {2, 2, 3, 1} };*/ |
Что же мы получаем на выходе:
Переполнение стека. Так как у нас вся матрица заполнена нулями, то для получения необходимого результата нам нужно 10000 вложенных вызовов нашей рекурсивной функции. Необходимая память для разворота такой рекурсии превышает ограничение в 1 Мб для стека вызовов.
Решение
Решением будет создать свой импровизированный стек и имитировать вызовы функций вручную, подражая тому, что делает компилятор. Ко всему прочему, необходимо создать вспомогательный класс, экземпляры которого будут хранить в себе аргументы, необходимые для работы, а также итоговый для каждого вызова результат.
Ещё стоит отметить, что мы имеем дело не с обычной хвостовой рекурсией. В нашем случае функция вызывает себя 4 раза, прибавляя к сумме каждый полученный результат. В качестве решения необходимо разбить нашу функцию на блоки, каждый из которых пронумерован, а также ввести переменную, помогающую определить с какого блока продолжится выполнение при извлечении очередного элемента из стека. Назовём её state.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
static int RecurseMethod(int h, int w) { // state = 0 if (h < 0 || w < 0 || h >= m_height || w >= m_width || visitMatrix[h, w] || valueMatrix[h, w] != targetValue) { return 0; } visitMatrix[h, w] = true; int sum = 1; sum += RecurseMethod(h + 1, w); // state 1 sum += RecurseMethod(h - 1, w); // state 2 sum += RecurseMethod(h, w + 1); // state 3 sum += RecurseMethod(h, w - 1); // state 4 return sum; // state 5 } |
А вот структура, помещаемая в стек. В ней хранятся наши координаты, итоговая сумма, а также номер блока с которого продолжится выполнение.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
class Entry { public int height; public int width; public int sum = 0; public int state = 0; public Entry(int height, int width) { this.height = height; this.width = width; } } |
Итеративный вариант решения с комментариями
|
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 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 |
using System; using System.Collections.Generic; using System.Linq; namespace RecurseToIteration { class Program { // Размеры матрицы const int m_height = 100; const int m_width = 100; // Необходимые данные для работы метода static bool[,] visitMatrix; static int[,] valueMatrix; static int targetValue; static void Main(string[] args) { // Начальная матрица valueMatrix = new int[m_height, m_width]; // Создадим матрицу, чтобы знать какие ячейки уже были посещены visitMatrix = new bool[m_height, m_width]; int maxCount = 0; for (int i = 0; i < m_height; i++) { for (int j = 0; j < m_width; j++) { // Пройдемся по всем ячейкам матрицы и запустим нашу функцию // для ячеек, которые еще не были обработаны if (visitMatrix[i, j] == false) { // Вынесем искомое значение в статическое поле targetValue = valueMatrix[i, j]; // Обновим найденный максимум, если полученное значение больше int nextCount = IterationMethod(i, j); maxCount = nextCount > maxCount? nextCount : maxCount; } } } Console.WriteLine($"Max: {maxCount}"); Console.ReadKey(); } class Entry { public int height; public int width; public int sum = 0; public int state = 0; public Entry(int height, int width) { this.height = height; this.width = width; } } static int IterationMethod(int h, int w) { // Инициализируем стек в явном виде и занесём туда первый элемент Stack<Entry> stack = new Stack<Entry>(); stack.Push(new Entry(h, w)); while (true) { // Извлекаем последний элемент стека и перезапишем // координаты во избежание громоздкости кода Entry entry = stack.Pop(); h = entry.height; w = entry.width; // Аналог блока кода из рекурсивной реализации, // выполняемого до запуска 4-х вложенных рекурсий if (entry.state == 0) { // Так же как и в рекурсивном методе проверим условие выхода if (h < 0 || w < 0 || h >= m_height || w >= m_width || visitMatrix[h, w] || valueMatrix[h, w] != targetValue) { // Аналог return 0, т.к. сумма у предыдущего элемента не меняется continue; } visitMatrix[h, w] = true; entry.sum = 1; } // Переходим к следующему состоянию entry.state += 1; // Вычислим координаты следующей ячейки в зависимости от текущего состояния if (entry.state == 1) h++; // RecurseMethod(h + 1, w); else if (entry.state == 2) h--; // RecurseMethod(h - 1, w); else if (entry.state == 3) w++; // RecurseMethod(h, w + 1); else if (entry.state == 4) w--; // RecurseMethod(h, w - 1); else { // Если все клетки вокруг уже обработаны, то обработаем конечный return if (stack.Count > 0) { // Если стек не пустой, то "вернем результат", // добавив полученную сумму к предыдущему элементу stack.Last().sum += entry.sum; continue; } else // Иначе мы вернулись к первому элементу и имеем готовый результат return entry.sum; } Entry newEntry = new Entry(h, w); // Координаты определены. Помещаем обратно в стек // текущий элемент и только что созданный stack.Push(entry); stack.Push(newEntry); } } } } |
Теперь результат какой и должен быть.
А вот результат для матрицы 300×300
Спасибо за внимание!
