ОРГАНИЗАЦИЯ ВЫЗОВОВ РЕКУРСИВНЫХ ФУНКЦИЙ В СОВРЕМЕННОМ ПРОГРАММНОМ ОБЕСПЕЧЕНИИ И ПРОБЛЕМЫ ПРОИЗВОДИТЕЛЬНОСТИ РЕКУРСИВНЫХ АЛГОРИТМОВ Шарипов М.И.

Уфимский государственный нефтяной технический университет


Номер: 5-1
Год: 2016
Страницы: 122-126
Журнал: Актуальные проблемы гуманитарных и естественных наук

Ключевые слова

рекурсивный алгоритм, вызов функции, производительность, программное обеспечение, recursive algorithm, function call, performance, software

Просмотр статьи

⛔️ (обновите страницу, если статья не отобразилась)

Аннотация к статье

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

Текст научной статьи

В большинстве разработанных для ОС MS Windows приложениях [1] для аппаратной платформе современных компьютеров на базе процессоров Intel [2], вызов функций (процедур) осуществляется путем передачи параметров через специальную область памяти, называемую стеком. Также в стеке размещаются локальные переменные функции. Ниже на рис. 1 приводится схема последовательности действий, выполняемых при вызове функции. Как видим, до и после непосредственного выполнения кода функции осуществляется ряд дополнительных действий, включающих взаимодействие со стеком (которые сводятся к чтению / записи ОЗУ), и передаче управления. Таким образом, вызов функций (процедуры) всегда сопровождается дополнительными затратами процессорного времени и оперативной памяти. В такой ситуации чрезмерное дробление программного кода на множество функций с одной стороны повышает структурированность и читабельность программного кода, но с другой стороны существенно отражается на производительности и ресурсоемкости программного обеспечения на современной аппаратной платформе. Рис. 1. Схема последовательности действий при вызове функции. Еще сложнее обстоит ситуация с рекурсивными функциями и процедурами, которые многократно вызывают сами себя. Вызов рекурсивной функции приводит к цепочке вложенных вызовов функции (рис. 2), сопровождающихся кумулятивно накапливающимися дополнительными затратами стековой памяти и процессорного времени. Рис. 2. Последовательность вложенных вызовов рекурсивной функции. В то же время многие вычислительные и комбинаторные задачи имеют как элегантное и наглядное решение в виде рекурсивных алгоритмов, так и более трудные для понимания, но более быстрые, итеративные алгоритмы. Рассмотрим для примера простейшую задачу вычисления факториала целого числа. С одной стороны факториал может быть вычислен итеративным способом . С другой стороны факториал может быть вычислен рекурсивным способом: . На рис. 3 представлены схемы итеративного и рекурсивного алгоритмов вычисления факториала. Рис. 3. Схема итеративного (слева) и рекурсивного (справа) алгоритма. Рекурсивный алгоритм выглядит компактнее и проще на первый взгляд, однако, детальный анализ вычислительных процессов (рис. 14) при выполнении алгоритмов на современном процессоре показывает, что на рекурсивный алгоритм тратится множество дополнительных действий для организации вложенных вызовов рекурсивной функции и возврата из них. Соответственно, итеративный алгоритм более предпочтителен с точки зрения вычислительной производительности. Аналогично, алгоритм комбинаторного перебора точек в булевом пространстве имеет эффективное итеративное решение [3]. Соответственно, итеративный алгоритм комбинаторного перебора, в свою очередь, существенно ускоряет решения задач дискретной оптимизации [4], к которым сводятся многие современные проблемы принятия решений, а также задач логистики [5]. В рамках научных исследований автором были разработаны модель итеративного комбинаторного перебора в рамках решения задач псевдобулевой оптимизации и проведено экспериментальное исследование по оценке ускорения на примере задач распределения ресурсов [6, 7]. Результаты исследований показало ускорение решения задач до 3,3 раза при использовании итеративного алгоритма для комбинаторного перебора по сравнению с рекурсивным алгоритмом.

Научные конференции

 

(c) Архив публикаций научного журнала. Полное или частичное копирование материалов сайта возможно только с письменного разрешения администрации, а также с указанием прямой активной ссылки на источник.