Использование рекурсивных алгоритмов для решения экономических задач (стр. 1 из 3)
Содержание
1. Теория рекурсивных алгоритмов. 3
1.1. Понятие рекурсии и её виды.. 3
1.2. Общие принципы программной реализации рекурсии.9
2. Программная реализация рекурсии. 17
2.1. Примеры решения задач с помощью рекурсии. 17
2.2. Решение экономической задачи с использованием рекурсивного алгоритма20
Список использованных источников. 23
Введение
В настоящее время область практического применения рекурсии весьма широка. Она включает, в частности, сложные задачи численного анализа, алгоритмы трансляции, а также различные операции над списками, являющиеся необходимым аппаратом разработки современных автоматизированных систем управления. Поэтому аппарат рекурсии предусматривается практически во всех языках программирования, появляющихся после АЛГОЛа.
Полезность, важность и необходимость рекурсии, как одного из концептуальных методов решения практических задач подчеркивалась многими мэтрами информатики. Одни из них, это два лауреата премии Тьюринга: американский специалист по системному программированию Д.Кнут и английский теоретик информатики Ч.Хоар.
1. Теория рекурсивных алгоритмов
1.1. Понятие рекурсии и её виды
Рекурсия – метод определения класса объектов или методов предварительным заданием одного или нескольких (обычно простых) его базовых случаев или методов, а затем заданием на их основе правила построения определяемого класса, ссылающегося прямо или косвенно на эти базовые случаи.
Другими словами, рекурсия – способ общего определения объекта или действия через себя, с использованием ранее заданных частных определений. Рекурсия используется, когда можно выделить самоподобие задачи.
Рекурсивный алгоритм (процедура, функция):
-алгоритм называется рекурсивным, если в его определении содержится прямой или косвенный вызов этого же алгоритма;
-рекурсивная функция – одно из математических уточнений интуитивного понятия вычислимой функции.
Адаптивный рекурсивный алгоритм – алгоритм, который благодаря рекурсивности учитывает те или иные индивидуальные характеристики решаемой задачи из области своего определения.
Базис рекурсии – это предложение, определяющее некую начальную ситуацию или ситуацию в момент прекращения. Как правило, в этом предложении записывается некий простейший случай, при котором ответ получается сразу, даже без использования рекурсии.
Шаг рекурсии – это правило, в теле которого обязательно содержится, в качестве подцели, вызов определяемого предиката.
Подпрограмма – все, что находится внутри рекурсивной функции.
Основное правило рекурсии: до рекурсивного вызова должна стоять проверка на возврат из рекурсии. Существуют следующие виды рекурсии:
-прямая рекурсия – непосредственный вызов алгоритма (функции, процедуры, метода) из текста самого метода.
В данном случае функция 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);
returnNULL;
}
Результат работы программы представлен на рисунке 1.1.
Рис. 1.1. Прямая рекурсия
-косвенная рекурсия.
При косвенной рекурсии имеется циклическая последовательность вызовов нескольких алгоритмов.
В данном случае функция 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);
returnNULL;
}
Результат работы программы представлен на рисунке 1.2.
Рис. 1.2. Косвенная рекурсия
-линейная рекурсия – если исполнение подпрограммы приводит только к одному вызову этой же самой подпрограммы, то такая рекурсия называется линейной.
 |
Рис. 1.3. Линейная рекурсия
#include <iostream>
using namespace std;
void function(int a);
void function (int a)
{
if (a > 0)
function(a – 1);
}
int main ( )
{
function(3);
returnNULL;
}
-ветвящаяся рекурсия – если каждый экземпляр подпрограммы может вызвать себя несколько раз, то рекурсия называется нелинейной или "ветвящейся".
 |  |
Рис. 1.4. Ветвящаяся рекурсия
#include <iostream>
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;
returnNULL;
}
-бесконечная рекурсия(на самом деле это условное обозначение так как при переполнении памяти компьютера программа выдаст ошибку и/или завершит ее в аварийном режиме).
Одна из самых больших опасностей рекурсии – бесконечный вызов функцией самой себя.
Например:
voidfunction ()
{ function(); }
Другойпример:
int Function (unsigned int n)
// Unsignedint – тип, содержащий неотрицательные значения
{ if (n > 0)
{
Function(n++); return n;
}
elsereturn 0;
}
Результат работы программы представлен на рисунке 1.5.
Рис. 1.5. Сообщение о переполнении стека
При использовании подобных алгоритмов появляется ошибка, предупреждающая о переполнении стека. Причиной такой проблемы чаще всего является отсутствие базиса, либо других точек останова, так же неправильно заданные точки прерывания рекурсии.
1.2. Общие принципы программной реализации рекурсии.
В программировании рекурсия – вызов функции (процедуры) из неё же самой, непосредственно (простая рекурсия) или через другие функции (сложная рекурсия), например, функция A вызывает функцию B, а функция B – функцию A. Количество вложенных вызовов функции или процедуры называется глубиной рекурсии.
Мощь рекурсивного определения объекта в том, что такое конечное определение способно описывать бесконечно большое число объектов. С помощью рекурсивной программы же возможно описать бесконечное вычисление, причём без явных повторений частей программы.