Язык программирования С++

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

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

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

Классический пример рекурсивной функции – вычисление факториала.

Ограничения: для отрицательного аргумента факториал не существует, результат принимает  нулевое значение. Для нулевого значения результат равен единице ( 0! = 1).

Функция вычисления факториала:

long fact(int k)

     { if (k<0) return 0;

        if (k==0) return 1;

        return k*fact(k-1);  //рекурсивный вызов функции

     }

При вычислении функции с k=3 произойдет повторное обращение к функции fact(2). Это обращение потребует вычисления fact(1). При вычислений fact(0) будет получен результат = 1. Затем цепочка вычислений раскрутится в обратном порядке:  
fact(1) = 1*fact(0) = 1;

fact(2) = 2*fact(1) = 2;

fact(3) = 3*fact(2) = 6;

Выполнение рекурсивной функции происходит в два этапа:

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

II этап: обратный ход – восстанавливается цепочка вычислений, сохраненных в стеке, и выдается результат рекурсивных вызовов.

Принципы рекурсивных функций

1. Рекурсивная функция разрабатывается как обобщенный шаг процесса, который вызывается в произвольных начальных условиях и приводит к следующему шагу в некоторых новых условиях.
2. Начальные условия очередного шага должны быть формальными параметрами функции.
3. Начальные условия следующего шага должны быть сформированы в виде фактических параметров рекурсивного вызова.
4. Локальными переменными функции должны быть объявлены все переменные, которые имеют отношение к протеканию текущего шага процесса и к его состоянию.
5. В рекурсивной функции обязательна проверка условий завершения рекурсии, при которых следующий шаг процесса не выполняется.

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

Рекуррентные формулы имеют вид: a_i = a_i-1 +2;  
                                                              a_i = 2a_i-1.

При написании рекурсивных функций необходимо запомнить одно очень важное правило. В первую очередь следует оформлять выход из рекурсии! Использование рекурсивных функций – красивый прием с точки зрения программистской эстетики. Однако этот путь не всегда рациональный. Как правило, рекуррентный алгоритм с большими или меньшими усилиями можно превратить в обычный циклический процесс. Например, фрагмент программы, вычисляющей факториал, может выглядеть следующим образом:

int factor(int x)   

      { int f=1;
         for (int i=2; i<=x; i++)

         f*=i;

         return f;

      }

Рекурсия или итерация ?

Сравним эти два подхода в программировании.

1. Рекурсия и итерация основаны на управляющих структурах: рекурсия использует структуру выбора, оператор итерация – структуру повтора.
2. Используют повторение операций. Рекурсия реализует повторение посредством повторных вызовов функции; итерация использует повторение явным образом, через оператор
3. Рекурсия и итерация включают проверку условия окончания повторений. В рекурсиях проверка условия до тех пор, пока не будет достигнут конечный результат; в итерациях выполняется изменение счетчика до тех пор, пока он не примет значение, при котором перестанет выполняться условие продолжение цикла.

Недостатки рекурсии:

1. Рекурсивный механизм вызовов функции приводит к затратам процессорного времени.
2. Каждый рекурсивный вызов приводит к созданию новой копии функции – для этого требуется дополнительная память.

Замечания:

1. Рекурсию предпочитают итерации, если рекурсия естественно отражает задачу и её результаты, т.е когда рекурсивный подход нагляден.
2. Если требуется повысить эффективность программы, то следует избегать использования рекурсий.

Пример с рекурсивной функцией (Решение задачи можно посмотреть, скачав файл "Задача-14"):

Вычислить сумму элементов арифметической прогрессии.

#include<iostream.h>
#include<conio.h>
#include<stdlib.h>
long int arif(long int n)
  {if ((n==0)||(n==1)) return 1;
  else return arif(n-1)+2;
  }

main()
{int k; int s=0, t;
 cout<<"Vvedite kolichestvo elementov progressti"<<'\n';
 cin>>k;
 for(int i=1;i<=k;i++)
     { t=arif(i);
       cout<<"a("<<i<<")="<<t<<'\t';
       s+=t;
      }
 cout<<'\n';
 cout<<"s="<<s<<'\n';
 return 0;
 }