Программирование рекурсивных алгоритмов на языке С++

Подпрограммы

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

Назначение подпрограмм

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

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

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

В простейшем случае (в ассемблерах) подпрограмма представляет собой последовательность команд (операторов), отдельную от основной части программы и имеющую в конце специальную команду выхода из подпрограммы. Обычно подпрограмма имеет имя, по которому её можно вызвать, хотя ряд языков программирования допускает использование и неименованных подпрограмм. В языках высокого уровня описание подпрограммы обычно состоит по меньшей мере из двух частей: заголовка и тела. Заголовок подпрограммы описывает её имя и, возможно, параметры, то есть содержит информацию, необходимую для вызова подпрограммы. Тело — набор операторов, который будет выполнен всякий раз, когда подпрограмма будет вызвана.
Вызов подпрограммы выполняется с помощью команды вызова, включающей в себя имя подпрограммы. В большинстве современных языков программирования команда вызова представляет собой просто имя вызываемой подпрограммы, за которым могут следовать фактические параметры.

Виды подпрограмм.

В языках программирования высокого уровня используется два типа подпрограмм: процедуры и функции.

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

Оформление подпрограмм в С++

В языке С++ подпрограммы реализованы в виде функций. Функция принимает параметры и возвращает единственное скалярное значение. Как известно, программа на С++ состоит из одной или нескольких функций. Функция должна быть описана перед своим использованием.
Описание функции состоит из заголовка и тела функции.

Заголовок_функции
{
тело_функции
}
Заголовок функции имеет вид: type имя_функции ([список параметров])

type – тип возвращаемого функцией значения; Тип функции показывает, какое значение возвращает функция: целое, вещественное, строковое и так далее. Если тип функции не указан, то подразумевается, что функция возвращает целое значение типа int.
список параметров – список параметров (аргументов) содержит перечень типов и имен величин, разделенных запятыми, и заключенных в скобки. Если функция не имеет параметров, то скобки все равно необходимы, хотя в них ничего не указывается, то есть в скобках в этом случае будет пустое место. Например:

fun1(int a, int b, float d);

В случае, если вызываемые функции определены до функции main,структура программы будет такой.

Тип_результата f1(Список_переменных)
{
Операторы
}
Тип_результата f2(Список_переменных)
{
Операторы
}
...
Тип_результата fn(Список_переменных)
{
Операторы
}
int main(Список_переменных)
{
Операторы основной функции, среди которых могут операторы вызова функций f1, f2, ..., fn
}

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

Рекурсия и ее виды

Рекурсия - метод определения класса объектов или методов предварительным заданием одного или нескольких (обычно простых) его базовых случаев или методов, а затем заданием на их основе правила построения определяемого класса, ссылающегося прямо или косвенно на эти базовые случаи.
Другими словами, рекурсия - способ общего определения объекта или действия через себя, с использованием ранее заданных частных определений. Рекурсия используется, когда можно выделить само подобие задачи.

Рекурсивный алгоритм (процедура, функция):

• алгоритм называется рекурсивным, если в его определении содержится прямой или косвенный вызов этого же алгоритма;
  
• рекурсивная функция - одно из математических уточнений интуитивного понятия вычислимой функции.
  

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

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

Шаг рекурсии - это правило, в теле которого обязательно содержится, в качестве подцели, вызов определяемого предиката.
Основное правило рекурсии: до рекурсивного вызова должна стоять проверка на возврат из рекурсии.

Виды рекурсии

Существуют следующие виды рекурсии:

Прямая рекурсия

Прямая рекурсия - непосредственный вызов алгоритма (функции, процедуры, метода) из текста самого метода.

В данном случае функция r1( ) вызывает саму себя.

#include <iostream>
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( ), которая вызывает r3( ).
Функция r3( ) в свою очередь снова вызывает r1( ).

#include <iostream>
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;
}

Бесконечная рекурсия

Бесконечная рекурсия (на самом деле это условное обозначение так как при переполнении памяти компьютера программа выдаст ошибку и/или завершит ее в   аварийном режиме).

Одна из самых больших опасностей рекурсии - бесконечный вызов функцией самой себя.
Например:

void function (){
function(); }

Другой пример:

int Function (unsigned int n){
// Unsigned int - тип, содержащий неотрицательные значения
if (n > 0)
{
Function(n++);
return n;
}
else return 0;
}

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

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

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

Рекурсивные процедуры и функции

Как процедура, так и функция - это часть программного кода, оформленная в виде подпрограммы, которую можно выполнять по ходу выполнения основной программы произвольное количество раз. Основное их отличие состоит в том, что функция должна в своем определении иметь описание ее результата (точнее, его типа), а также должна содержать операцию присваивания результату какого-то значения. В основной программе вызов функции напоминает математическую функцию и выглядит как R=F(a, b,...), где R - переменная, которой будет присвоен результат вычисления функции, F - имя функции, a, b ,... - список аргументов, он может отсутствовать, но скобки все равно должны быть. Кроме этого, в большинстве языков программирования в теле функции запрещено изменять значения аргументов. Типичный пример - библиотечная функция y=sin(x).

В процедуре определение результата, как такового, отсутствует, поэтому ее вызов выглядит как P(a,b,...), где P - название процедуры, a,b,... - список аргументов, который может отсутствовать вместе со скобками. В процедурах разрешается изменять значения своих аргументов, т.е. они могут быть как входными, так и выходными.

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

Пример рекурсивной функции: Вычислить сумму чисел в интервале, заданном вводимыми числами. Использовать рекурсивную функцию.

Решение. Условием окончания рекурсии станет ситуация, когда верх-няя граница на единицу больше нижней границы, то есть интервал задан двумя соседними целыми числами.

#include <iostream>
using namespace std;
int sum(int y, int x);
int main()
{
int a, b;
cout<< "Enter 1-st number: " <<endl;
cin>> a;
cout<< "Enter 2-st number: " <<endl;
cin>> b;
cout<< sum(b, a) <<endl;
return 0;
}
int sum(int y, int x)
{
int s = 0;
if ((y - 1) == x)
s = y + x;
else
s = y + sum(y - 1, x);
return s;
}

Пример рекурсивной процедуры: Составить рекурсивную процедуру нахождения n–го числа Фибоначи.

Решение:

#include <iostream>
voidfibonacci( unsigned long int&mber, int count, unsigned long intprev = 0 ) {
if ( count > 1 ) {
number += prev;
fibonacci( number, count - 1, number - prev );
}
}
int main() {
unsigned long int fib = 1;
fibonacci( fib, 10 );
std::cout<< fib <<std::endl;
return 0;
}

Глоссарий

Бесконечная рекурсия (на самом деле это условное обозначение так как при переполнении памяти компьютера программа выдаст ошибку и/или завершит ее в аварийном режиме).
Вызов подпрограммы выполняется с помощью команды вызова, включающей в себя имя подпрограммы. В большинстве современных языков программирования команда вызова представляет собой просто имя вызываемой подпрограммы, за которым могут следовать фактические параметры.
Косвенная рекурсия - При косвенной рекурсии имеется циклическая последовательность вызовов нескольких алгоритмов.
Подпрограмма - поименованная или иным образом идентифицированная часть компьютерной программы, содержащая описание определённого набора действий. Подпрограмма может быть многократно вызвана из разных частей программы.
Процедура — это любая подпрограмма, которая не является функцией.
Прямая рекурсия - непосредственный вызов алгоритма (функции, процедуры, метода) из текста самого метода.
Рекурсивная ветвь - алгоритм, который благодаря рекурсивности учитывает те или иные индивидуальные характеристики решаемой задачи из области своего определения.
Рекурсия - метод определения класса объектов или методов предварительным заданием одного или нескольких (обычно простых) его базовых случаев или методов, а затем заданием на их основе правила построения определяемого класса, ссылающегося прямо или косвенно на эти базовые случаи.
Тело подпрограммы — набор операторов, который будет выполнен всякий раз, когда подпрограмма будет вызвана.
Терминальная ветвь рекурсии - это предложение, определяющее некую начальную ситуацию или ситуацию в момент прекращения. Как правило, в этом предложении записывается некий простейший случай, при котором ответ получается сразу, даже без использования рекурсии.
Функция — это подпрограмма специального вида, которая, кроме получения параметров, выполнения действий и передачи результатов работы через параметры имеет ещё одну возможность — она может возвращать результат. Вызов функции является, с точки зрения языка программирования, выражением, он может использоваться в других выражениях или в качестве правой части присваивания.
Шаг рекурсии - это правило, в теле которого обязательно содержится, в качестве подцели, вызов определяемого предиката.