Курсовая работа по программированию на тему Рекурсивное программирование

Рекурсия применима не только для определения алгоритмов, но и для определения структур данных. В реальной жизни многие явления схематически можно изобразить в виде структурной системы, части которой связаны отношениями включения и подчинения. Такие системы называются иерархическими, их части – узлами, связи между ними – связями или ссылками.
Примеры иерархических структур: Вселенная (Метагалактика – галактика – звездное скопление – звезда – планетная система); государство (республика – область – район – населенный пункт); завод (службы управления и обеспечения – цеха – участки); родословная (ее схематическое изображение – генеалогическое дерево); армейское соединение (дивизия – полк – батальон – рота – взвод – отделение).
В дискретной математике иерархическим структурам сопоставляются модельные математические понятия списка, дерева, графа.
Список может служить моделью очереди к врачу в поликлинике; дерево – моделью родословной (генеалогическое дерево) или, например, моделью очередности встреч спортсменов по олимпийской системе; граф – моделью станций и путей сообщения метрополитена и т.д.
Элемент списка (узел,звено) состоит как минимум из двух частей:
 одна – содержательная (например, фамилия больного);
 вторая – связующая (каждый должен помнить, за кем занял очередь).
Рекурсия позволяет определять подобные иерархические структуры.
• Рекурсивное определение списка:
а) Список – это либо пустая структура;
б) либо – элемент списка, указывающий на список из последующих элементов;
• Рекурсивное определение дерева:
а) дерево – это либо пустая структура;
б) либо – узел, связанный с конечным числом деревьев.
В обоих определениях налицо рекурсивность: понятие списка определяется через понятие списка; понятие дерева — через понятие дерева.
Если, например, сопоставить себе корень генеалогического дерева, то две дуги из корня приведут к матери и отцу, по две дуги от каждого из родителей приведут к бабушкам и дедушкам и так далее.
Во всех языках программирования есть понятие процедуры, которое сопоставляет алгоритму имя так, что, описав алгоритм один раз, получаем возможность многократно вызывать его по имени.
Аналогично: во многих языках программирования можно из имеющихся элементарных базовых типов строить более сложные структуры данных (массивы, структуры, динамические структуры; см. следующую тему “Немного о массивах, структурах и указателях”).
Рекурсивный алгоритм реализует какое-либо рекурсивное определение посредством разбиения решаемой задачи на подзадачи меньшей размерности, выполняемые с помощью одного и того же алгоритма. Процесс разбиения завершается при достижении простейших возможных решаемых задач минимальной размерности, которые называются условиями завершения. Таким образом, рекурсивное определение алгоритма включает две части:
 условия завершения (одно или несколько), которые могут быть вычислены для определенных параметров. Условия завершения соответствуют базисной части рекурсивного определения;
 шаг рекурсии, в котором текущие значения некоторых переменных в алгоритме могут быть определены с использованием их предыдущих значений.
В конечном итоге шаг рекурсии должен приводить к выполнению условий завершения.
Рекурсивные алгоритмы реализуются через рекурсивные методы (функции). Рекурсивным называется метод, который в процессе выполнения явно или неявно вызывает сам себя.
Рекурсивный алгоритм (процедура, функция):
 Если его определение содержит прямые или косвенные обращения к одному и тому же алгоритму, алгоритм называется рекурсией;
 Рекурсивная функция - одно из математических улучшений интуитивной концепции вычислимой функции.
Адаптивный рекурсивный алгоритм - алгоритм, который благодаря рекурсии учитывает определенные индивидуальные особенности, которые решают проблемы из определенной области.
Рекурсивная база - это предложение, которое определяет некоторые начальные условия или условия во время завершения. Обычно в этом предложении пишите простой случай, и вы можете получить немедленный ответ, даже если вы не используете рекурсию.
Рекурсивный шаг - это правило, тело которого должно содержать вызов определенного предиката в качестве дочерней цели.
Подпрограмма - это одна из вещей в рекурсивной функции.
Основное правило рекурсии: перед рекурсивным вызовом должна быть проверка, возвращаемая из рекурсии.
Существуют следующие типы рекурсии:
 Прямая рекурсия - напрямую вызывать алгоритм (функцию, процедуру, метод) из текста самого метода;
 Косвенная рекурсия - существует несколько циклических последовательностей вызовов алгоритма;
 Линейная рекурсия - если подпрограмма выполняется только один раз для той же самой подпрограммы, то эта рекурсия называется линейной;
 Ветвь рекурсии - если каждый экземпляр подпрограммы может вызывать себя несколько раз, рекурсия называется нелинейной или «ветвью»;
 Бесконечная рекурсия (на самом деле это соглашение, потому что, когда память компьютера заполнена, программа выдаст ошибку и / или завершит работу в аварийном режиме).
Необходимо рассмотреть особенность рекурсивной программы, например, функции, используемые для генерации чисел Фибоначчи. Каждый рекурсивный уровень в функции Фибоначчи удваивает количество вызовов, поэтому количество рекурсивных вызовов, которые должны вычислить n-е число Фибоначчи, равно 2n.
Поэтому, если возможно, следует избегать рекурсивных программ, таких как программы, которые вычисляют числа Фибоначчи, что привело бы к экспоненциальному увеличению числа вызовов. Любая проблема, которая может быть решена рекурсивно, также может быть решена итеративно (а не рекурсивно). Рекурсивный алгоритм в программировании реализован в механизме так называемого рекурсивного процесса. Рекурсия - это подпрограмма, на которую прямо или косвенно ссылаются другие подпрограммы, и на которую можно ссылаться вместе с другими фактическими параметрами. В современных системах программирования стек обеспечивает правильную работу подпрограмм, особенно рекурсивных подпрограмм.
Аппаратный стек находится в ОЗУ, а указатель стека содержится в специальной паре регистров SS: SP для программиста. Аппаратный стек расширяется в направлении убывающего адреса с указателем на первый свободный элемент.
PASCAL, C и C ++ используют стек для размещения локальных переменных процесса и других программных блоков. Стек делится на сегменты, которые представляют собой блоки смежных ячеек. Каждый вызов подпрограммы использует фрагмент стека, длина которого зависит от вызывающей подпрограммы. Каждый раз, когда процесс активируется, стек выделяет память для своих локальных переменных, а когда процесс завершается, память освобождается. Поскольку вызовы процедур всегда строго вложены, в верхней части стека всегда есть память, содержащая локальные переменные для текущего активного процесса.
Поэтому, как правило, когда процедура A вызывает процедуру B, происходит следующее:
1. Фрагмент нужного размера размещается сверху стопки. Включает в себя следующие данные:
а) фактические параметры, указывающие на вызов процедуры;
б) пустая ячейка локальной переменной, определенной в процессе Б;
C) Обратный адрес, адрес команды, выполняемой в программе A, выполняется после того, как программа B завершила свою работу.
Если B является функцией, фрагмент стека b содержит указатель на ячейку в фрагменте стека a, в которую следует поместить значение функции (адрес значения).
2. Управление первым оператором, переданным в программу B.
3. После завершения шага B переведите управление на шаг A, используя следующую последовательность шагов:
а) получить адрес возврата с вершины стека;
b) Если B - функция, ее значение сохраняется в ячейке, указанной указателем на адрес значения;
C) извлечь фрагмент стека процесса b из стека и поместить фрагмент процесса a поверх стека; 45
d) Программа a возобновляется командой, указанной в адресе возврата.
Та же последовательность операций выполняется, когда подпрограмма вызывает себя, то есть в случае рекурсии.
Такой подход позволяет легко реализовать рекурсивный процесс. Когда процедура вызывает себя, новая память в стеке выделяется для всех ее локальных переменных, а вложенные вызовы представляются их собственными локальными переменными. Когда вложенный вызов завершается, он освобождает пространство памяти, занимаемое его переменными в стеке, и представление предыдущего уровня локальных переменных становится актуальным.

1.2 Основные принципы построения рекурсивных алгоритмов

Эффективное построение рекурсивных алгоритмов требует соблюдения определенных принципов и приемов, обеспечивающих как точность результата, так и эффективность выполнения.
1. Определение базовой ситуации (Base Case). Каждый рекурсивный алгоритм обязан иметь четкий базовый случай, предотвращающий бесконечную рекурсию. Определение базового случая должно основываться на анализе задачи и понимании самой природы проблемы.
Базовым случаем называется ситуация, при которой задача решается напрямую, без дальнейшего рекурсивного вызова. Именно эта проверка предотвращает бесконечную рекурсию и останавливает цепочку вложенных вызовов.
Пример: вычисление факториала числа ????. Базовый случай — ????????????????????????????????????(0) или ????????????????????????????????????(1), результатом которых является 1.
2. Уменьшение размеров задачи
Важно убедиться, что каждое последующее рекурсивное обращение уменьшает размер рассматриваемой задачи, продвигая ее ближе к базовому случаю. Нарушение этого принципа приводит к вечной рекурсии.

Пример: бинарный поиск в отсортированном массиве:
def binary_search(arr, low, high, x):
if high >= low:
mid = (high + low) // 2
if arr[mid] == x:
return mid
elif arr[mid] > x:
return binary_search(arr, low, mid - 1, x)
else:
return binary_search(arr, mid + 1, high, x)
else:
return -1
Здесь рекурсивные вызовы постоянно снижают диапазон поиска, приближая задачу к решению.
3. Разделение задачи на более мелкие части
Разбиение большой задачи на мелкие, аналогичные подзадачи — классический прием рекурсии. Решение каждой подзадачи затем объединяется для формирования общего результата.
Пример: при вычислении факториала для числа ????, следующий рекурсивный вызов производится для (????−1). Таким образом, размер задачи уменьшается на единицу.
3. Самостоятельный вызов самой себя (Self-call)
Процедура должна вызывать саму себя, передавая упрощённую версию исходной задачи. Эта способность позволяет решить общую задачу путём многократного разделения на меньшие проблемы.
Пример: формула факториала рекурсивно выражается как ????????????????????????????????????(????)=????⋅????????????????????????????????????(????−1).