eolymp

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

   Когда мы начинаем познавать азы программирования, как правило первой написанной нами является программа, печатающая строку «Hello, world!». Потом знакомятся с переменными, операторами, функциями. И как правило, первыми, с которыми начинает знакомиться новичок, являются условный оператор и оператор цикла.  Сразу же появляется желание написать какую-нибудь простую функцию: факториал числа, возведение в степень или вычисление биномиального коэффициента. При этом в большинстве случаев начинающий программист реализует итеративный вариант функций. Однако мало кто знает, что любую итеративную функцию можно реализовать и рекурсивно.

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

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

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

   Теорема. Произвольный алгоритм, реализованный в рекурсивной форме, может быть переписан в итерационной форме и наоборот.

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

   I) условие продолжения рекурсии (шаг рекурсии);

   II) условие окончания рекурсии.

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

   Итеративный вариант функций будем реализовывать при помощи оператора цикла for.

   1. Факториал числа. Факториалом целого неотрицательного числа n называется произведение всех натуральных чисел от 1 до n и обозначается n!. Если f(n) = n!, то имеет место рекуррентное соотношение:

medv_rec_02

   Первое равенство описывает шаг рекурсии – метод вычисления f(n) через f(n – 1). Второе равенство указывает, когда при вычислении функции следует остановиться. Если его не задать, то функция будет работать бесконечно долго.

   Например, значение f(3) можно вычислить следующим образом:

f(3) = 3 · f(2) = 3 · 2 · f(1) = 3 · 2 · 1 · f(0) = 3 · 2 · 1 · 1 = 6

   Очевидно, что при вычислении f(n) следует совершить n рекурсивных вызовов.

рекурсивная реализация

циклическая реализация

int f(int n)

{

  if (!n) return 1;

  return n * f(n - 1);

}

 

int f(int n)

{

  int i, res = 1;

  for (i = 1; i <= n; i++) res = res * i;

  return res;

}

   Идея циклической реализации состоит в непосредственном вычислении факториала числа при помощи оператора цикла:

f(n) = 1 · 2 · 3 · … · n

   2. Степень числа за линейное время. Вычисление степени числа f(a, n) = an с линейной  (O(n)) временной оценкой можно определить при помощи следующего рекуррентного соотношения:

medv_rec_03

рекурсивная реализация

циклическая реализация

int f(int a, int n)

{

  if (!n) return 1;

  return a * f(a, n - 1);

}

 

int f(int a, int n)

{

  int i, res = 1;

  for (i = 0; i < n; i++) res = res * a;

  return res;

}

   В итерационном варианте достаточно вычислить произведение a · a · … · a (n множителей a).

   3. Степень числа за логарифмическое время. Вычисление степени числа f(a, n) = an с временной оценкой O(log2n) определим следующим образом:

medv_rec_04

   Например, возведение в десятую степень можно реализовать так:

medv_rec_05

   Поскольку возведение в квадрат эквивалентно одному умножению, то для вычисления a10 достаточно совершить 4 умножения.

рекурсивная реализация

циклическая реализация

int f(int a, int n)

{

  if (!n) return 1;

  if (n & 1) return a * f(a * a, n / 2);

  return f(a * a, n / 2);

}

 

int f(int a, int n)

{

  int  res = 1;

  while (n > 0)

  {

    if (n & 1) res *= a;

    n >>= 1; a *= a;

  }

  return res;

}

   4. Сумма цифр числа. Сумму цифр натурального числа n можно найти при помощи функции f(n), определенной следующим образом:

medv_rec_06

   Условие продолжения рекурсии: сумма цифр числа равна последней цифре плюс сумма цифр числа без последней цифры (числа, деленного нацело на 10).

   Условие окончания рекурсии: Если число равно 0, то сумма его цифр равна 0.

   Например, сумма цифр числа 234 будет вычисляться следующим образом:

f(234) = 4 + f(23) = 4 + 3 + f(2) = 4 + 3 + 2 + f(0) = 4 + 3 + 2 + 0 = 9

рекурсивная реализация

циклическая реализация

int f(int n)

{

  if (!n) return 0;

  return n % 10 + f(n / 10);

}

 

int f(int n)

{

  int res = 0;

  for (; n>0; n = n / 10) res = res + n % 10;

  return res;

}

   5. Число единиц. Количество единиц в двоичном представлении числа n можно вычислить при помощи функции f(n), определенной следующим образом (& - операция побитового 'И'):

medv_rec_07

   В результате операции n = n & (n – 1) уничтожается последняя единица в двоичном представлении числа n:

               n = a1a2…ak-1ak10…0

         n – 1 = a1a2…ak-1ak01…1

n & (n – 1) = a1a2…ak-1 000…0

   Рекурсивный вызов функции f будет совершаться столько раз, сколько единиц в двоичном представлении числа n.

рекурсивная реализация

циклическая реализация

int f(int n)

{

  if (!n) return 0;

  return 1 + f(n & (n - 1));

}

 

int f(int n)

{

  int res = 0;

  for (; n > 0; n = n & (n - 1)) res++;

  return res;

}

   6. Биномиальный коэффициент. Значение биномиального коэффициента равно

medv_rec_08

и определяется рекуррентным соотношением:

medv_rec_09

int c(int k, int n)

{

  if (n == k) return 1;

  if (k == 0) return 1;

  return c(k - 1, n - 1) + c(k, n - 1);

}

  Учитывая, что

medv_rec_10

значение биномиального коэффициента можно вычислить при помощи цикла. При этом все операции деления будут целочисленными. Если k > n – k, то следует воспользоваться соотношением

medv_rec_11

во избежании Time Limit при вычислении, например, значения

medv_rec_12

int Cnk(int k, int n)

{

  long long res = 1;

  if (k > n - k) k = n - k;

  for (int i = 1; i <= k; i++)

    res = res * (n - i + 1) / i;

  return (int)res;

}

   7. Рекурсивная функция. Для заданного натурального n вычислим значение функции f(n), заданной рекуррентными соотношениями:

f(2 · n) = f(n),

f(2 · n + 1) = f(n) + f(n + 1),

f(0) = 0, f(1) = 1

Непосредственная реализация функции f(n) имеет вид:

int f(int n)

{

  if (n <= 1) return n;

  if (n % 2) return f(n / 2) + f(n / 2 + 1);

  return f(n / 2);

}

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

g(n, i, j) = i · f(n) + j · f(n + 1),

   для которой имеют место равенства:

g(2·n, i, j) = g(n, i + j, j),

g(2·n + 1, i, j) = g(n, i, i +  j),

g(0, i, j) = i · f(0) + j · f(1) = j

Используя приведенные соотношения, можно вычислить значение f(n) = g(n, 1, 0) с временной оценкой O(log n).

int g(int n, int i, int j)

{

  if (!n) return j;

  if (n % 2) return g(n / 2, i, i + j);

  return g(n / 2, i + j, j);

}

int f(int n)

{

  return g(n, 1, 0);

}

   8. Функция Аккермана. Функция Аккермана A(m, n) определяется рекурсивно следующим образом:

A(0, n) = n + 1,

A(m, 0) = A(m – 1, 1),

A(m, n) = A(m – 1, A(m, n – 1))

   Рекурсивная реализация функции Аккермана имеет вид:

int a(int m, int n)

{

  if (!m) return n + 1;

  if (!n) return a(m - 1, 1);

  return a(m - 1, a(m, n - 1));

}

   Для малых значений m функцию Аккермана можно выразить явно:

A(0, n) = n + 1

A(1, n) = 2 + (n + 3) – 3 = n + 2

A(2, n) = 2 · (n + 3) – 3 = 2 · n + 3

A(3, n) = 2n + 3 – 3

   9. Отбор в разведку [ACM, 1999]. Из n солдат, выстроенных в шеренгу, требуется отобрать нескольких в разведку. Для совершения этого выполняется следующая операция: если солдат в шеренге больше чем 3, то удаляются все солдаты, стоящие на четных позициях, или все солдаты, стоящие на нечетных позициях. Эта процедура повторяется до тех пор, пока в шеренге останется 3 или менее солдат. Их и отсылают в разведку. Вычислить количество способов, которыми таким образом могут быть сформированы группы разведчиков ровно из трех человек.

   Вход. Количество солдат в шеренге n ( 0 < n ≤ 107).

   Выход. Количество способов, которыми можно отобрать солдат в разведку описанным выше способом.

Пример входа

Пример выхода

10
2
4
0

   Решение. Обозначим через f(n) количество способов, которыми можно сформировать группы разведчиков из n человек в шеренге. Поскольку нас интересуют только группы по три разведчика, то f(1) = 0, f(2) = 0, f(3) = 1. То есть из трех человек можно сформировать только одну группу, из одного или двух – ни одной.

   Если n четное, то применяя определенную в задаче операцию удаления солдат в шеренге, мы получим в качестве оставшихся либо n / 2 солдат, стоящих на четных позициях, либо n / 2 солдат, стоящих на нечетных позициях. То есть f(n) = 2 · f(n / 2) при четном n.

   Если n нечетное, то после удаления останется либо n / 2 солдат стоявших на четных позициях, либо n / 2 + 1 солдат, стоявших на нечетных позициях. Общее количество способов при нечетном n равно  

f(n) = f(n / 2) + f(n / 2 + 1).

   Таким образом, получена рекуррентная формула для вычисления значения f(n):

f(n) = 2 · f(n / 2), если n четное

f(n) = f(n / 2) + f(n / 2 + 1), если n нечетное

f(1) = 0, f(2) = 0, f(3) = 1

   Реализация функции f имеет вид:

int f(int n)

{

  if (n <= 2) return 0;

  if (n == 3) return 1;

  if (n % 2) return f(n / 2) + f(n / 2 + 1);

  return 2 * f(n / 2);

}

СПИСОК ЛИТЕРАТУРЫ

   1. "Алгоритмы построение и анализ", Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К., – Москва, Санкт-Петербург, Киев, 2005 – 1292 с. 

   2. "Практика и теория программирования", Книга 2. Винокуров Н.А., Ворожцов А.В., – М: Физматкнига, 2008 - 288 с.