Преобразование рекурсии в итерацию

Задача

Итак, нам дана следующая матрица
Пример матрицы значений

Наша задача — вычислить максимальное количество стоящих рядом элементов с одинаковыми значениями. То есть, программа должна в данном случае выдать число 4. Для решения нам вполне хватит консольного приложения на C#.

Рекурсивный вариант решения с комментариями

Результат работы программы:

Результат

Проблема

И вроде бы всё хорошо, ломаться тут нечему. Давайте увеличим размер матрицы до 100 на 100 и уберем первоначальную инициализацию. То есть у нас будет матрица 100×100, заполненная нулями. По логике программа должна выдать число 10000.

Что же мы получаем на выходе:
Преобразование рекурсии в итерацию

Переполнение стека. Так как у нас вся матрица заполнена нулями, то для получения необходимого результата нам нужно 10000 вложенных вызовов нашей рекурсивной функции. Необходимая память для разворота такой рекурсии превышает ограничение в 1 Мб для стека вызовов.

Решение

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

Ещё стоит отметить, что мы имеем дело не с обычной хвостовой рекурсией. В нашем случае функция вызывает себя 4 раза, прибавляя к сумме каждый полученный результат. В качестве решения необходимо разбить нашу функцию на блоки, каждый из которых пронумерован, а также ввести переменную, помогающую определить с какого блока продолжится выполнение при извлечении очередного элемента из стека. Назовём её state.

А вот структура, помещаемая в стек. В ней хранятся наши координаты, итоговая сумма, а также номер блока с которого продолжится выполнение.

Итеративный вариант решения с комментариями

Теперь результат какой и должен быть.
Преобразование рекурсии в итерацию

А вот результат для матрицы 300×300
Преобразование рекурсии в итерацию

Спасибо за внимание!

Понравилась статья? Поделиться с друзьями:
Добавить комментарий

;-) :| :x :twisted: :smile: :shock: :sad: :roll: :razz: :oops: :o :mrgreen: :lol: :idea: :grin: :evil: :cry: :cool: :arrow: :???: :?: :!: