Программирование рекурсивных алгоритмов на языке С++
Подпрограммы
[править]Подпрограмма - поименованная или иным образом идентифицированная часть компьютерной программы, содержащая описание определённого набора действий. Подпрограмма может быть многократно вызвана из разных частей программы.
Назначение подпрограмм
[править]Подпрограммы изначально появились как средство оптимизации программ по объёму занимаемой памяти — они позволили не повторять в программе идентичные блоки кода, а описывать их однократно и вызывать по мере необходимости. К настоящему времени данная функция подпрограмм стала вспомогательной, главное их назначение — структуризация программы с целью удобства её понимания и сопровождения
Выделение набора действий в подпрограмму и вызов её по мере необходимости позволяет логически выделить целостную подзадачу, имеющую типовое решение. Такое действие имеет ещё одно (помимо экономии памяти) преимущество перед повторением однотипных действий: любое изменение (исправление ошибки, оптимизация, расширение функциональности), сделанное в подпрограмме, автоматически отражается на всех её вызовах, в то время как при дублировании каждое изменение необходимо вносить в каждое вхождение изменяемого кода.
Даже в тех случаях, когда в подпрограмму выделяется однократно производимый набор действий, это оправдано, так как позволяет сократить размеры целостных блоков кода, составляющих программу, то есть сделать программу более понятной и обозримой.
В простейшем случае (в ассемблерах) подпрограмма представляет собой последовательность команд (операторов), отдельную от основной части программы и имеющую в конце специальную команду выхода из подпрограммы. Обычно подпрограмма имеет имя, по которому её можно вызвать, хотя ряд языков программирования допускает использование и неименованных подпрограмм. В языках высокого уровня описание подпрограммы обычно состоит по меньшей мере из двух частей: заголовка и тела. Заголовок подпрограммы описывает её имя и, возможно, параметры, то есть содержит информацию, необходимую для вызова подпрограммы. Тело — набор операторов, который будет выполнен всякий раз, когда подпрограмма будет вызвана.
Вызов подпрограммы выполняется с помощью команды вызова, включающей в себя имя подпрограммы. В большинстве современных языков программирования команда вызова представляет собой просто имя вызываемой подпрограммы, за которым могут следовать фактические параметры.
Виды подпрограмм.
[править]В языках программирования высокого уровня используется два типа подпрограмм: процедуры и функции.
Процедура — это любая подпрограмма, которая не является функцией.
Функция — это подпрограмма специального вида, которая, кроме получения параметров, выполнения действий и передачи результатов работы через параметры имеет ещё одну возможность — она может возвращать результат. Вызов функции является, с точки зрения языка программирования, выражением, он может использоваться в других выражениях или в качестве правой части присваивания.
Подпрограммы, входящие в состав классов в объектных языках программирования, обычно называются методами. Этим термином называют любые подпрограммы-члены класса, как функции, так и процедуры; когда требуется уточнение, говорят о методах-процедурах или методах-функциях.
Оформление подпрограмм в С++
[править]В языке С++ подпрограммы реализованы в виде функций. Функция принимает параметры и возвращает единственное скалярное значение. Как известно, программа на С++ состоит из одной или нескольких функций. Функция должна быть описана перед своим использованием.
Описание функции состоит из заголовка и тела функции.
Заголовок_функции
{
тело_функции
}
Заголовок функции имеет вид: 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;
}
Глоссарий
[править]Бесконечная рекурсия (на самом деле это условное обозначение так как при переполнении памяти компьютера программа выдаст ошибку и/или завершит ее в аварийном режиме).
Вызов подпрограммы выполняется с помощью команды вызова, включающей в себя имя подпрограммы. В большинстве современных языков программирования команда вызова представляет собой просто имя вызываемой подпрограммы, за которым могут следовать фактические параметры.
Косвенная рекурсия - При косвенной рекурсии имеется циклическая последовательность вызовов нескольких алгоритмов.
Подпрограмма - поименованная или иным образом идентифицированная часть компьютерной программы, содержащая описание определённого набора действий. Подпрограмма может быть многократно вызвана из разных частей программы.
Процедура — это любая подпрограмма, которая не является функцией.
Прямая рекурсия - непосредственный вызов алгоритма (функции, процедуры, метода) из текста самого метода.
Рекурсивная ветвь - алгоритм, который благодаря рекурсивности учитывает те или иные индивидуальные характеристики решаемой задачи из области своего определения.
Рекурсия - метод определения класса объектов или методов предварительным заданием одного или нескольких (обычно простых) его базовых случаев или методов, а затем заданием на их основе правила построения определяемого класса, ссылающегося прямо или косвенно на эти базовые случаи.
Тело подпрограммы — набор операторов, который будет выполнен всякий раз, когда подпрограмма будет вызвана.
Терминальная ветвь рекурсии - это предложение, определяющее некую начальную ситуацию или ситуацию в момент прекращения. Как правило, в этом предложении записывается некий простейший случай, при котором ответ получается сразу, даже без использования рекурсии.
Функция — это подпрограмма специального вида, которая, кроме получения параметров, выполнения действий и передачи результатов работы через параметры имеет ещё одну возможность — она может возвращать результат. Вызов функции является, с точки зрения языка программирования, выражением, он может использоваться в других выражениях или в качестве правой части присваивания.
Шаг рекурсии - это правило, в теле которого обязательно содержится, в качестве подцели, вызов определяемого предиката.