XXI век именуют веком компьютеров и информации. Из-за стремительного развития технических, научных и технологических исследований появился шанс хранить огромные объёмы данных и преобразовывать их с немыслимой скоростью. Создавая сложные информационные системы, проектировщики столкнулись с нетривиальными задачами, которые требовали формирования новых концепций программирования.
Чтобы решить эти проблемы, особенно учитывая человеческий фактор, появляется потребность в обеспечении понятности алгоритма, «читабельности» исходного кода программы, и как следствие относительной лёгкости и модифицируемости сопровождения итогового программного продукта. Зачастую это можно получить посредством включения в реализацию приложения рекурсивных подпрограмм, механизмы применения которых предоставляются почти всеми современными средами разработки и компиляторами.
Сегодня сфера практического использования рекурсии довольно велика. Она состоит из алгоритмов трансляции, сложных задач численного анализа, в том числе разных операций над списками, которые необходимы аппарату разработки современных автоматизированных систем управления. В связи с этим аппарат рекурсии предусматривается почти во всех языках программирования, которые появляются после АЛГОЛа.
Важность, полезность и потребность рекурсии, как одного из концептуальных методов решения практических задач определялась многими знатоками информатики. Примером могут быть два лауреата премии Тьюринга: английский теоретик информатики Ч.Хоар и американский специалист по системному программированию Д.Кнут.
Значимость рекурсии состоит в том, что она является одним из самых мощных, в том числе самым общих методов научного познания. Она эффективно используется в большом количестве теоретических и прикладных естественнонаучных дисциплинах, и стала их неотъемлемой частью.
1. Теория рекурсивных алгоритмов
1.1 Рекурсия и её виды
Рекурсией является метод определения класса методов или объектов предварительным заданием нескольких или одного его базового метода или случая, а после заданием на их базе правила построения определяемого класса, который ссылается косвенно или прямо на данные базовые случаи.
Иначе говоря, рекурсией называется способ общего определения действия или объекта через себя, с применением изначально заданных частных определений. Рекурсия применяется, когда можно определить само подобие задачи.
Рекурсивная функция, алгоритм, процедура.
Алгоритм считается рекурсивным, если в его определении содержится косвенный или прямой вызов этого же алгоритма;
Рекурсивная функция – это одно из математических уточнений интуитивного понятия вычислимой функции.
Адаптивный рекурсивный алгоритм – алгоритм, который с помощью рекурсивности учитывает различные индивидуальные особенности решаемой задачи из сферы своего определения.
Базис рекурсии – это предложение, которое определяет какую-то ситуацию в момент прекращения или начальную ситуацию. Обычно, в данном предложении записывается какой-то простейший случай, где сразу получается ответ без применения рекурсии.
Шагом рекурсии считается правило, в теле которого всегда содержится вызов определяемого предиката, в качестве подцели.
Подпрограмма – это все, что находится внутри рекурсивной функции.
Главное правило рекурсии: до рекурсивного вызова необходимо поставить проверку на возврат из рекурсии. Есть некоторые виды рекурсии:
- Прямая рекурсия – непосредственный вызов функции, алгоритма, метода, процедуры из текста самого метода.
В этом случае функция r1( ) вызывает саму себя.
#include
using namespace std;
void r1 (int a);
void r2 (int a);
void r3 (int a);
void r1(int a)
{
cout << "function r1" << endl;
if (a < 6)
r1(a+1);
}
int main ( )
{
r1 (0);
return null;
}
- Косвенная рекурсия, содержит циклическую последовательность, вызовов нескольких алгоритмов.
В этом случае функция r1( ) вызывает функцию r2( ), а r2( ) вызывает функцию r3( ). И заново функция r3( ) снова вызывает r1( ).
#include
using namespace std;
void r1 (int a);
void r2 (int a);
void r3 (int a);
void r1(int a)
{
cout << "function r1" << endl;
if (a < 6)
r2(a+1);
}
void r2(int a)
{
cout << "function r2" << endl;
if (a < 6)
r3(a+1);
}
void r3(int a)
{
cout << "function r3" << endl;
if (a < 6)
r1(a+1);
}
int main ( )
{
r1 (0);
return null;
}
Результат работы программы видим на рисунке 2.
Рис. 2. Косвенная рекурсия
- Линейной рекурсией называется исполнение подпрограммы, которое приводит лишь к одному вызову той же самой подпрограммы.
Рис. 3. Линейная рекурсия
#include
using namespace std;
void function(int a);
void function (int a)
{
if (a > 0)
function(a – 1);
}
int main ( )
{
function(3);
return NULL;
}
- Ветвящаяся или нелинейная рекурсия заключается в том, что все экземпляры подпрограммы могут вызвать себя несколько раз.
Рис. 4. Ветвящаяся рекурсия
#include
using namespace std;
int function(int a);
int function (int a)
{
if (a > 3)
a = function (a – 1) * function(a – 2);
return a;
}
int main ()
{
cout << function(6) << endl;
return null;
}
- Бесконечная рекурсия. Одна из самых больших опасностей рекурсии – бесконечный вызов функцией самой себя.
Например:
void function ()
{ function(); }
Другой пример:
int Function (unsigned int n)
// Unsigned int – тип, который содержит положительные значения
{ if (n > 0)
{
Function(n++); return n;
}
else return 0;
}
Результат работы программы видим на рисунке 5.
Рис. 5. Сообщение о переполнении стека
Применяя данные алгоритмы появляется ошибка, которая предупреждает о переполнении стека. Причина здесь в основном - отсутствие базиса, или иных точек останова, в том числе неправильно заданные точки прерывания рекурсии.
1.2 Базовые принципы программной реализации рекурсии
Рекурсия в программировании – это вызов процедуры, функции из неё же самой, непосредственно простой рекурсии или через иные функции сложной рекурсии, допустим, функция A вызывает функцию B, а функция B – функцию A. Количество процедур или вложенных вызовов функции называется глубиной рекурсии.
Суть и сила рекурсивного определения объекта состоит в том, что данное итоговое определение может описывать бесконечно большое число объектов. Благодаря рекурсивной программе же можно описать бесконечное вычисление, причём без очевидных повторений частей программы.
Осуществление рекурсивных вызовов функций в практически применяемых средах и языках программирования, обычно, основывается на механизм стека вызовов – локальные переменные и адрес возврата функции записываются в стек, с помощью чего все следующие рекурсивные вызовы данной функции пользуются своим набором локальных переменных и благодаря этому работают верно. Оборотная сторона данного простого по структуре механизма - рекурсивные вызовы не бесплатны – на каждый рекурсивный вызов необходимо какое-то количество оперативной памяти компьютера, и при слишком большой глубине рекурсии может наступить переполнение стека вызовов. Поэтому обычно рекомендуется избегать рекурсивные программы, которые могут привести к чрезмерно большой глубине рекурсии.
Существует особый тип рекурсии, который называется «хвостовой рекурсией». Компиляторы и интерпретаторы функциональных языков программирования, которые поддерживают оптимизацию кода (исполняемого и/или исходного), автоматически формируют хвостовую рекурсию в итерацию, с помощью чего обеспечивают выполнение алгоритмов с хвостовой рекурсией в ограниченном объёме памяти. Данные рекурсивные вычисления, в том числе если они бесконечны формально, допустим, когда благодаря рекурсии формируется работа командного интерпретатора, который принимает команды пользователя, никогда не приводят к исчерпанию памяти.
Стоит отметить одну особенность, что характерна для рекурсивных программ, аналогичной той, что применяют для генерации чисел Фибоначчи. Все уровни рекурсии в функции fibonacci удваивают количество вызовов, так что объем рекурсивных вызовов, который должен быть выполнен для вычисления n – го числа Фибоначчи, оказывается порядка 2N.
Количество вычислений быстро нарастает с ростом n. Вычисление только 20-го числа Фибоначчи заняло бы почти 2N или практически миллион вызовов, вычисление 30-го числа Фибоначчи заняло бы почти 3N или практически миллиард вызовов и т.п. Это называется экспоненциальной сложностью.
Таким образом, стоит избегать рекурсивных программ, аналогичных программе для вычисления чисел Фибоначчи, которые приводят к экспоненциальному нарастанию количества вызовов.
Все задачи, что можно решить рекурсивно, можно решить в том числе не рекурсивно, а итеративно. Как правило, итеративному подходу предпочитают рекурсивный, если он лучше отражает задачу и ее итоги, иначе говоря легче отлаживается и более нагляден. Иное основание для предпочтения рекурсивного решения заключается в не очевидном итеративном решении.
Рекурсивные алгоритмы в программировании сформированы в механизме рекурсивных подпрограмм. Рекурсивная подпрограмма та, что косвенно или прямо, через иные подпрограммы, обращается к себе, иногда с другими фактическими параметрами. В нынешних системах программирования правильная работа подпрограмм, особенно рекурсивных, обеспечивается благодаря стеку.
Стеком называется связная структура данных, которая построена по принципу «первый пришёл – первый вышел» (FIFO, Fiгst In – Fiгst Out). Иначе говоря, снова добавляемые объекты помещаются в вершину стека, начало, и выбираются они аналогично, только из вершины.
Стек довольно удобен структурой данных для большинства задач вычислительной техники. Самой банальной из данных задач является обеспечение вложенных вызовов процедур. Предположим, существует процедура A, которая вызывает процедуру B, а та вызывает процедуру C. Когда выполнение процедуры A дойдет до вызова B, процедура A приостанавливается и управление передается на входную точку процедуры B. Когда B доходит до вызова C, B приостанавливается и управление передается на процедуру C. Когда заканчивается выполнение процедуры C, управление вернется в B, причем в точку, следующую за вызовом C.
При завершении B управление должно возвращаться в A, в точку, которая следуюет за вызовом B. Рациональную последовательность возвратов не сложно обеспечить, если при всех вызовах процедуры записывать адрес возврата в стек. Поэтому, когда процедура A вызывает процедуру B, в стек заносится адрес возврата в A; когда B вызывает C, в стек заносится адрес возврата в B. Когда C заканчивается, адрес возврата выбирается из вершины стека – а это адрес возврата в B. Когда заканчивается B, в вершине стека находится адрес возврата в A, и возврат из B произойдет в A.
Механизм вызова процедуры или функции в языке высокого уровня значительно зависит от операционной системы и архитектуры компьютера. В пределах IBM PC совместимых компьютеров, в микропроцессорах семейства Intel, как и в большом количестве современных процессорных архитектур, поддерживается аппаратный стек.
Аппаратный стек находится в ОЗУ, указатель стека содержится в паре особых регистров SS:SP, что доступны для программиста. Аппаратный стек увеличивается в сторону уменьшения адресов, указатель его направляет первый свободный элемент. Схематично данный механизм можно увидеть на рисунке 6.
Рис. 6. Механизм вызова функции в аппаратном стеке
Языки python, C++, C, PASCAL применяют стек для размещения в нем локальных переменных процедур и других программных блоков. Стек разделен на фрагменты, которые являются блоками последовательных ячеек. Все вызовы подпрограммы применяет фрагмент стека, длина которого находится в зависимости от вызывающей подпрограммы. При все активизаций процедур память для ее локальных переменных определяется в стеке; после завершения процедуры данная память освобождается. Так как при вызовах процедур должна строго соблюдаться вложенность, то в вершине стека должна находится память, которая содержит локальные переменные активной в тот момент процедуры.
Поэтому, в общем случае при вызове процедурой A процедуры B происходит следующее:
В вершине стека размещается фрагмент необходимого размера. В него включается следующая информация:
- указатели реальных параметров вызова процедуры В;
- пустые ячейки для локальных переменных, которые были определены в процедуре В;
- адрес возврата, иными словами адрес команды в процедуре A, которую необходимо выполнить следом за окончанием работы процедуры B.
В случае если B – функция, то во фрагмент стека для B размещается указатель ячейки во фрагменте стека для A, в которую стоит положить адрес значения, значение данной функции.
Управление передается первому оператору процедуры B.
Завершая работу процедуры B управление передается процедуре A посредством следующей последовательности шагов:
- адрес возврата извлекается из вершины стека;
- в случае если B – функция, то ее значение записывается в ячейке, которой предписан указатель на адрес значения;
- фрагмент стека процедуры B извлекается из стека, в вершину определяется фрагмент процедуры A;
- выполнение процедуры A возобновляется с команды, которая определена в адресе возврата.
Вызывая подпрограмму самой себя, иначе говоря в рекурсивном случае, выполняется аналогичная последовательность действий.
Данный прием делает возможным легкую реализацию рекурсивных процедур. Когда процедура вызывает сама себя, то для всех ее локальных переменных определяется новая память в стеке, и вложенный вызов функционирует с собственным представлением локальных переменных. Когда вложенный вызов завершается, занимаемая его переменными часть памяти в стеке освобождается и актуальным становится представление локальных переменных прошлого уровня.
Рекурсия применяет стек в скрытом виде от программиста, однако все рекурсивные процедуры могут реализовываться и без рекурсии, а с очевидным применением стека.
Пример для функции вычисления факториала может являться дерево рекурсии при вычислении 5! (рисунок 7).
