Использование рекурсивных алгоритмов для решения экономических задач

Содержание

Введение

 

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

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

    В настоящее время область практического  применения рекурсии весьма широка. Она включает, в частности, сложные задачи численного анализа, алгоритмы трансляции, а также различные операции над списками, являющиеся необходимым аппаратом разработки современных автоматизированных систем управления. Поэтому аппарат рекурсии предусматривается практически во всех языках программирования, появляющихся после АЛГОЛа.

    Полезность, важность и необходимость рекурсии, как одного из концептуальных методов решения практических задач подчеркивалась многими мэтрами информатики. Одни из них, это два лауреата премии Тьюринга: американский специалист по системному программированию Д.Кнут и английский теоретик информатики Ч.Хоар.

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

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);

return NULL;

}  

Результат работы программы представлен на рисунке 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);

return NULL;

}

Результат работы программы представлен на рисунке 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);

      return NULL;

}

• ветвящаяся рекурсия – если каждый экземпляр подпрограммы может вызвать себя несколько раз, то рекурсия называется нелинейной или "ветвящейся".

    

Рис. 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;

      return NULL;

}  

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

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

Например:  

 

 void function ()

            { function(); } 

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

int Function (unsigned int n)

// Unsigned int – тип, содержащий неотрицательные значения

{ if (n > 0)

   {

    Function(n++); return n;

   } 

    else return 0;

} 
 
 

Результат работы программы представлен на рисунке 1.5.

Рис. 1.5. Сообщение о переполнении стека

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

 

     1.2. Общие принципы программной реализации рекурсии.

    В программировании рекурсия – вызов функции (процедуры) из неё же самой, непосредственно (простая рекурсия) или через другие функции (сложная рекурсия), например, функция A вызывает функцию B, а функция B – функцию A. Количество вложенных вызовов функции или процедуры называется глубиной рекурсии.

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

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

    Имеется специальный тип рекурсии, называемый «хвостовой рекурсией». Интерпретаторы и компиляторы функциональных языков программирования, поддерживающие оптимизацию кода (исходного и/или исполняемого), автоматически преобразуют хвостовую рекурсию к итерации, благодаря чему обеспечивают выполнение алгоритмов с хвостовой рекурсией в ограниченном объёме памяти. Такие рекурсивные вычисления, даже если они формально бесконечны (например, когда с помощью рекурсии организуется работа командного интерпретатора, принимающего команды пользователя), никогда не приводят к исчерпанию памяти.

    Нужно учитывать одну особенность, характерную для рекурсивных программ, подобных той, которую используют для генерации чисел Фибоначчи. Каждый уровень рекурсии в функции fibonacci удваивает количество вызовов, так что количество рекурсивных вызовов, которое должно быть выполнено для вычисления n – го числа Фибоначчи, оказывается порядка 2N.

    Объем вычислений резко нарастает с  увеличением n. Вычисление только 20 – го числа Фибоначчи потребовало бы порядка 2N или около миллиона вызовов, вычисление 30 – го числа Фибоначчи потребовало бы порядка 3N или около миллиарда вызовов и так далее. В методах вычислений это называется экспоненциальной сложностью.