2. Рекурсия.

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

В языке С++ существует еще одна уникальная возможность вызова подпрограммой самой себя. Такие процедуры и функции называются рекурсивными. Различают прямую рекурсию, когда подпрограммы обращаются к своему имени в «недрах» себя, и косвенную, когда ссылка на нее идет через цепочку других процедур и функций. В данной работе мы познакомимся с некоторыми простейшими рекурсивными алгоритмами.

С понятием рекурсия тесно связано понятие рекуррентное соотношение (оба слова имеют общий корень от латинского recurro – возвращаться, бежать назад). Запишем в общем виде рекуррентное соотношение порядка к:

f(n) = G (n, f (n - 1),f (n - 2), … f (n - k)), (1)

где G – некоторая функция к + 1 аргумента.

Если известны начальные значения f(1), f(2), …f(k), то выражение (1) позволяет однозначно определить f(n). Выбрав другие начальные условия, получим тем же способом другую функцию от n, удовлетворяющую (1). Каждая такая функция является решением данного рекуррентного соотношения.

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

Принцип работы рекурсивных подпрограмм подобен работе стека. Прямой ход рекурсии – операция засылки информации в стек (операция Push): Обратный ход рекурсии – последовательное извлечение данных из стека (операция Pop):

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

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