Рекурсия

04.09.00

Возможно для кого-то это будет удивительным, но наиболее известным алгоритмом является сортировка пузырьком (не то, что бы ее все знали, просто название запоминающееся). А самый известный метод построения алгоритмов --- рекурсия. Точно так же, как и в случае сортировки пузырьком, чаще всего применять ее не умеют, но название почему-то знают.

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

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

Во-вторых, если получается сделать алгоритм без применения рекурсии, то, скорее всего, им и надо воспользоваться. Рекурсивные вызовы подпрограмм имеют свойство решать одну и ту же задачу бесчисленное количество раз (во время повторов), что значительно сказывается на времени. Самым ярким примером является традиционное вычисление чисел Фибоначчи рекурсивным и итеративным способами.

Напомню, что числами Фибоначчи называются числа, пренадлежащие следующей последовательности:
F₀ = 0;
F₁ = 1;
F_n = F_n-1 + F_n-2 для n > 1.

В общем-то я сейчас буду озвучивать очень известные вещи, но это только для того, что бы обратить особое внимание на некоторые детали, которые обычно не улавливаются слушателями (наверно, именно из-за того, что многие думают, что они уже "все знают").

Задача заключается в том, что бы найти по заданному n число последовательности Фибоначчи F_n.

Глядя на определение последовательности, приходит на ум использование рекурсии примерно таким образом:

#include <stdio.h>
#include <time.h>

long F(unsigned int n)
{
  return n <= 1 ? n : F(n-1) + F(n-2);
}

int main()
{
  time_t begin, end;
  long res;

  for(int n = 0; n < 40; n++)
  {
    time(&begin);
    res = F(n);
    time(&end);

    printf("%-3i\t%-9li\t%-20.3f\n",n,res,difftime(end,begin));
  }

  return 0;
}

Т.е. функция F(n) возвращает n-ый член последовательности чисел Фибоначчи. В результате я только что получил (на не самой быстрой на сегодняшний день машине, но меня интересует только динамика роста времени вычислений) следующие результаты:

0       0               0.000
1       1               0.000
2       1               0.000
3       2               0.000
4       3               0.000
5       5               0.000
6       8               0.000
7       13              0.000
8       21              0.000
9       34              0.000
10      55              0.000
11      89              0.000
12      144             0.000
13      233             0.000
14      377             0.000
15      610             0.000
16      987             0.000
17      1597            0.000
18      2584            0.000
19      4181            0.000
20      6765            0.000
21      10946           0.000
22      17711           0.000
23      28657           0.000
24      46368           0.000
25      75025           0.000
26      121393          0.000
27      196418          0.000
28      317811          0.000
29      514229          0.000
30      832040          0.000
31      1346269         1.000
32      2178309         0.000
33      3524578         1.000
34      5702887         1.000
35      9227465         2.000
36      14930352        4.000
37      24157817        6.000
38      39088169        9.000
39      63245986        14.000

Как видно, время вычислений на 36-39 шагах растет очень быстро. Разница между 39 и 38 шагом составляет уже 5 (сравните с разницей между 38 и 37 шагом равной 3). Понятно, что если подходить строго, то надо было брать процессорное время, а не разность времени между концом и началом вычислений, но в этот момент не было запущено требовательных к вычислительной мощности процессов. Так что можно говорить с уверенностью о том, что такая реализация рекурсии в данном случае приводит к тому, что растет время вычислений дополнительного шага. Я думаю, понятно почему: время на вычисление 38 числа составляет 9 (округленно), время на вычисление 37 числа составляет 6 (тоже округленно). Следовательно, так как F(39) будет инициировать вычисления F(38) и F(37), то общее время вычислений будет порядка 9+6. Что примерно и получили.

Тут сразу же должно становится видно, что если число F(38) уже рассчитано, то считать F(37) лишний раз уже не надо (потому что оно было посчитано во время расчета 38-числа). То же самое можно сказать и вообще про все числа: не надо повторять вычисления, если они уже проводились.

Следовательно надо хранить где-то уже посчитанные значения (можно ограничиться только двумя последними), например так, как это сделано ниже:

long F(unsigned int n)
{
  long F_1 = 1, F_2 = 0, F_cur;

  if(n <= 1)
    return n;

  for(unsigned int k = 2; k <= n; k++)
    {
      F_cur = F_1 + F_2;
      F_2 = F_1;
      F_1 = F_cur;
    }

  return F_cur;
}

Для такой реализации функции вычисления числа Фибоначчи результаты выполнения программы будет следующим:

0       0               0.000
1       1               0.000
2       1               0.000
3       2               0.000
4       3               0.000
5       5               0.000
6       8               0.000
7       13              0.000
8       21              0.000
9       34              0.000
10      55              0.000
11      89              0.000
12      144             0.000
13      233             0.000
14      377             0.000
15      610             0.000
16      987             0.000
17      1597            0.000
18      2584            0.000
19      4181            0.000
20      6765            0.000
21      10946           0.000
22      17711           0.000
23      28657           0.000
24      46368           0.000
25      75025           0.000
26      121393          0.000
27      196418          0.000
28      317811          0.000
29      514229          0.000
30      832040          0.000
31      1346269         0.000
32      2178309         0.000
33      3524578         0.000
34      5702887         0.000
35      9227465         0.000
36      14930352        0.000
37      24157817        0.000
38      39088169        0.000
39      63245986        0.000

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

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

Таким образом, рекурсию надо использовать очень осторожно; пример с числами Фибоначчи, конечно же, достаточно примитивен и очень распространен, но почему-то такие ошибки встречаются сплошь и рядом. Очень просто заставить рекурсию десять раз вычислять одно и то же...

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

Вообще говоря, стек и рекурсия взаимозаменяемы. То есть, все что можно сделать при помощи рекурсии, можно заменить на "условно бесконечный" ;) цикл с использованием стека и наоборот. Это очень часто используется тогда, когда размер системного стека (того, в который помещается адрес возврата и где выделяется память под локальные переменные) сильно ограничен какими-то аппаратными особенностями; в таких случаях реализуют стек самостоятельно и имитируют вызов подпрограммы путем работы с этим "доморощенным" стеком.

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

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

Резюме

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

Т.е., как обычно: прежде чем что-то делать, надо подумать, обвешать все острые места красными флажками, а после этого делать.

Ссылки по теме