Рекурсия

Алгоритмизация / Рекурсия

 

Рекурсия — состоит в определении, описании, изображении какого-либо объекта или процесса внутри самого этого объекта или процесса. Это ситуация, когда объект является частью самого себя.

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

1
2
3
4
5
6
7
8
9
10
11
12
#include <iostream>
using namespace std;
void func(int num)
{
  if (num > 0) func(num - 1);
  cout << num << " ";
}
int main() 
{
  func(3);
  cin.get(); return 0;
}

Рекурсия

Процедура func() вызывается с параметром 3. В ней содержится вызов процедуры func() с параметром 2. Предыдущий вызов еще не завершился, поэтому создается еще одна процедура и до окончания ее работы func(3) свою работу приостанавливает. Процесс вызова заканчивается, когда параметр равен 0. В этот момент одновременно выполняются 4 экземпляра процедуры.

Количество одновременно выполняемых процедур называют глубиной рекурсии.

Последняя вызванная процедура func(0) выведет число 0 и закончит свою работу. После этого управление возвращается к процедуре, которая ее вызвала: func(1) и выводится число 1. И так далее пока не завершатся все процедуры.
Рекурсия
Важным и обязательным моментом в формировании рекурсивной процедуры является базис рекурсии.Базис рекурсии определяет условие выхода из рекурсии. Как правило, в качестве базиса записывается некий простейший случай, при котором ответ получается сразу, без использования рекурсии.
Существует такое понятие как шаг рекурсии или рекурсивный вызов. В случае, когда рекурсивная функция вызывается для решения сложной задачи (не базового случая) выполняется некоторое количество рекурсивных вызовов или шагов, с целью сведения задачи к более простой. И так до тех пор пока не получим базовое решение.

Сложная рекурсия

Возможна чуть более сложная схема: функция A вызывает функцию B, а та в свою очередь вызывает A. Это называется сложной рекурсией. При этом оказывается, что описываемая первой процедура должна вызывать еще не описанную. Чтобы это было возможно, требуется использовать описание функции B до ее использования.
Пример: вычислить значение выражения
Сложная рекурсия: пример

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
using namespace std;
int pow(intint); // описание сигнатуры
double calc(int x, int n)
{
  return (double)pow(x, n) / n; // вызов функции pow
}
int pow(int x, int n)
{
  if (n == 1) return x;
  return x*calc(x, n - 1); // вызов функции calc
}
int main()
{
  int n, x;
  cout << "n = "; cin >> n;
  cout << "x = "; cin >> x;
  double a = calc(x, n); // вызов рекурсивной функции
  cout << a;
  cin.get(); cin.get();
  return 0;
}

Результат выполнения
Рекурсия: результат выполнения

Префиксная и постфиксная форма записи

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

Префиксная форма Постфиксная форма
Сначала - рекурсивный вызов, потом - действия Сначала - действия, потом - рекурсивный вызов
 
1
2
3
4
5
 
...
void func(int num)
{
  if (num > 0) func(num - 1);
  cout << num << " ";
}
...
 
1
2
3
4
5
 
...
void func(int num)
{
  cout << num << " ";
  if (num > 0) func(num - 1);
}
...
Префиксная форма Постфиксная форма

Рекуррентные соотношения

Во многих случаях в основе рекурсии лежат рекуррентные соотношения.
Рекуррентное соотношение — это соотношение вида
Рекуррентное соотношение
выражающее каждый член последовательности an через p предыдущих членов.
Вычисление требуемого элемента последовательности будет состоять в повторяющемся обновлении значений этой последовательности.

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

Рекурсия или итерирование

Итерация — организация обработки данных, при которой действия повторяются многократно, не приводя при этом к вызовам самих себя (в отличие от рекурсии).
Рассмотрим вычисление факториала в виде итерационной и рекурсивной процедуры.

Итерационная процедура Рекурсивная процедура
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
using namespace std;
int fact(int num)
{
  int rez = 1;
  for (int i = 1; i <= num; i++)
  rez *= i;
  return rez;
}
int main()
{
  cout << fact(3);
  cin.get();
  return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
using namespace std;
int fact(int num)
{
  if(num==1) return 1;
  return num*fact(num - 1);
}
int main()
{
  cout << fact(3);
  cin.get();
  return 0;
}

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

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

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

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


Назад: Алгоритмизация

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *