Методические аспекты преподавания основ рекурсии

Таким образом, в общем  случае при вызове процедурой A процедуры B происходит следующее:

1. В вершину стека помещается фрагмент нужного размера. В него входят следующие данные:
1. указатели фактических параметров вызова процедуры В;
2. пустые ячейки для локальных переменных, определенных в процедуре В;
3. адрес возврата, т.е. адрес команды в процедуре A, которую следует выполнить после того, как процедура B закончит свою работу.

Если B – функция, то во фрагмент стека для B помещается указатель  ячейки во фрагменте стека для A, в которую надлежит поместить  значение этой функции (адрес значения).

2. Управление передается первому оператору процедуры B.
3. При завершении работы процедуры B управление передается процедуре A с помощью следующей последовательности шагов:
1. адрес возврата извлекается из вершины стека;
2. если B – функция, то ее значение запоминается в ячейке, предписанной указателем на адрес значения;
3. фрагмент стека процедуры B извлекается из стека, в вершину ставится фрагмент процедуры A;
4. выполнение процедуры A возобновляется с команды, указанной в адресе возврата.

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

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

Рекурсия использует стек в скрытом от программиста виде, но все рекурсивные процедуры могут быть реализованы и без рекурсии, но с явным использованием стека.[2]

1.2. Методы рекурсивного программирования

Процесс программной  реализации рекурсивных алгоритмов обладает, по сравнению с итерационными алгоритмами, специфическими особенностями, а именно – необходимостью организации специальной структуры данных и обслуживания рекурсивных вызовов. При этом, организация «правильной» структуры данных лежит на плечах программиста, в то время как механизм обслуживания рекурсивных вызовов обеспечивается языком программирования, точнее, компилятором этого языка, и поддерживается машинными командами компьютера.[3]

Особенности разработки структур данных.

Поскольку рекурсивный алгоритм задает во времени последовательность обращений к одному и тому же фрагменту программного кода, то применяемая структура данных должна обеспечить сохранность тех ячеек и массивов, которые будут задействованы алгоритмом после возврата из рекурсивного вызова. В рамках возможностей современных языков процедурного (императивного) программирования могут быть использованы разнообразные варианты, из которых мы остановимся на трех основных.[3]

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

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

Динамическая структура  данных. Третий подход к созданию необходимой структуры для программной реализации рекурсивного алгоритма состоит в том, что пользователь средствами языка программирования обращается к операционной системе для выделения необходимого в данный момент ресурса памяти. Этот подход, обладая определенной гибкостью, требует от пользователя аккуратного обращения с динамически выделяемой памятью, своевременного ее освобождения и организации правильной передачи аргументов при рекурсивных вызовах и правильного возвращения полученных результатов при рекурсивных возвратах. Отметим еще одну особенность этого подхода — в зависимости от текущего состояния фрагментации области динамической памяти, обслуживаемой средствами операционной системы, временные затраты на динамическое выделение памяти могут существенно влиять на общее время выполнения программной реализации. Очевидно, что в этом случае также затруднено теоретическое прогнозирование временных характеристик программ.

Рассмотрение механизма организации  рекурсивных вызовов мы начнем с модели программного стека.[2] Будем предполагать, что операционная система поддерживает специальную область оперативной памяти — программный стек, используя специальный регистр или ячейку памяти — указатель стека, хранящий адрес некоторой ячейки (слова) в этой области. Две специальные команды — «записать в стек» и «читать из стека» организуют работу с этой областью так, что логически мы считаем, что имеем дело со стеком как классической структурой, хотя указанные операции и изменяют адрес указателя стека. Например, команда «записать в стек» уменьшает текущий адрес и записывает по этому адресу содержимое своего операнда. Такой подход гарантирует, что любая операция со стеком не приводит к перезаписи со сдвигом его содержимого, и позволяет считать, что трудоемкость выполнения указанных команд не зависит от объема хранимой информации.

Применительно к рекурсивным  алгоритмам такими «универсальными» и достаточно распространенными методами являются метод рекуррентных соотношений, метод декомпозиции и метод динамического программирования[3]. Однако в каждом конкретном случае их применение не является автоматическим. Мы недаром поставили слово «универсальный» в кавычки — для каждого метода существуют некоторые границы его применимости, и чем более «универсально» сформулирован сам метод, тем интеллектуально сложнее разработка реального алгоритма на его основе.

Метод рекуррентных соотношений

Идея метода рекуррентных соотношений чрезвычайно проста — мы, используя некоторые рассуждения, получаем рекуррентное соотношение, обеспечивающее решение нашей задачи, и на основе этого рекуррентного соотношения разрабатываем рекурсивный алгоритм. Отметим, что фраза «используя некоторые рассуждения» совершенно не определяет конкретный метод получения рекуррентного соотношения для определенной задачи. Мы можем лишь уточнить, что эти рассуждения должны отражать наше рекурсивное понимание структуры задачи, т.е. следовать схеме понижения аргумента или размерности. Решение для некоторой размерности задачи или для некоторого аргумента функции должно быть сформулировано на основе ее сведения к задачам меньшей размерности или функциям с меньшим значением аргумента. Условие останова рекурсии позволяет решить задачу при некоторых малых размерностях или вычислить функцию при начальных значениях аргумента.

Метод декомпозиции

Чтобы перенести сотню кирпичей с одного места на другое, мы, скорее всего, будем переносить за один раз несколько кирпичей, а не всю сотню сразу. Таким образом, вместо того, чтобы решать задачу сразу, мы несколько раз решаем более простую задачу с понижением размерности — собственно говоря, эта идея и лежит в основе метода декомпозиции. Другое название этого метода — метод «разделяй и властвуй». Общая схема метода может быть описана как последовательность следующих шагов.

Шаг разделения задачи. На этом шаге выбирается способ разделения задачи на некоторое  количество подзадач меньшей размерности.

Шаг решения полученных подзадач. Это рекурсивный шаг — мы рассматриваем каждую подзадачу как задачу определенной размерности., и разделяем ее на собственные подзадачи, выполняя снова шаг 1 (рекурсия) до тех пор, пока не получим такую размерность, при которой решение может быть найдено непосредственно.

Шаг останова рекурсии. На этом шаге выполняется  непосредственное решение полученных подзадач для малых размерностей.

Шаг объединения решений. На этом шаге полученные решения подзадач меньшей  размерности при возврате в точку рекурсивного вызова объединяются в решение задачи текущей размерности.

Эти основные шаги метода декомпозиции требуют некоторых комментариев. Во-первых, идея метода ничего не говорит  о том, как эти шаги должны быть реализованы в конкретной задаче. Адаптация метода к конкретной задаче требует, как правило, серьезных размышлений. Во-вторых, условием применения метода является свойство аддитивности решений, полученных для подзадач меньшей размерности. Строго говоря, нам необходимо доказать, что, объединяя решения, мы получим правильный ответ, в особенности это касается задач оптимизации в постановке поиска глобального оптимума. Классическим примером является задача коммивояжера  — простое объединение двух оптимальных путей для графов половинной размерности вообще не является решением исходной задачи. В-третьих, для одной и той же задачи могут быть предложены различные идеи ее разделения, и здесь необходимо оценить, к каким сложностям приводит каждая из этих идей на этапе объединения решений, который, как правило, является наиболее сложным.

Основное преимущество метода декомпозиции состоит в том, что он позволяет  получить алгоритмы с хорошими асимптотическими оценками трудоемкости.

Метод динамического программирования

Метод динамического программирования был предложен и обоснован Р. Беллманом в начале 1960-х годов [3]. Первоначально метод создавался в целях существенного сокращения перебора для решения целого ряда задач экономического характера, формулируемых в терминах задач целочисленного программирования. Однако Р. Беллман и Р. Дрейфус в [3] показали, что он применим к достаточно широкому кругу задач, в том числе к задачам вариационного исчисления, поиску нулей функций и т. д. В общем виде метод ориентирован на поиск оптимума целевой функции или функционала в некоторой ограниченной области многомерного пространства. Предложенный Р. Беллманом метод не является универсальным, и условия его применения требуют, чтобы целевой функционал представлял собой аддитивную функцию.

Нисходящее  динамическое программирование (top – down dynamic pгogгamming). Оно позволяет выполнять рекурсивные функции при том же количестве итераций, что и восходящее динамическое программирование. Технология требует введения в рекурсивную программу неких средств, обеспечивающих сохранение каждого вычисленного значения и проверку сохраненных значений во избежание их повторного вычисления.[2]

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

Преимущества  рекурсии заключаются в следующих аспектах:

• часто это наиболее легкий метод написания алгоритма для задач, которые можно решить с помощью рекурсии (число фибоначчи, факториал);
• рекурсивно реализованные алгоритмы, при правильных на то основаниях, имеют лаконичную запись и менее трудоёмки при последующей отладке и модификации, они сокращают временные затраты на разработку, отладку и модификацию программных средств;
• целый ряд структур данных и многие объекты современных языков программирования рекурсивны по самой своей сути (фрактальные объекты, иерархия классов в объектно – ориентированном программировании, древовидные регулярные структуры данных) и программы для работы с такими структурами выглядят намного более естественно в рекурсивной реализации;
• рекурсия делает код более читабельным (позволяет читать код с любого места, не просматривая его весь, отслеживая все изменения переменной), что облегчает отладку;
• рекурсия защищает от ошибок типа: «действия выполнены в неверном порядке», «использована неинициализированная переменная» и других аналогичных.

Недостатки  рекурсии заключаются в следующем:

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