Шаг 17.
Понятие рекурсии.
Связь между рекурсией и итерацией

    На этом шаге мы рассмотрим связь между рекурсией и итерацией.

   

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

  1. Рекурсивный вариант.
      function Fr (n: integer): integer;
      begin 
        if n = 1 or n = 2 then Fr:= 1
        else Fr:=Fr(n-l) + Fr(n-2);
      end;
    
  2. Итеративный вариант.
        function Fi (n: integer): integer;
          var i, N1, N2, Result: integer ;
        begin 
          N1:= 1; N2:= 1; {Установка начальных значений}
          Result:= 1; {на тот случай, если n = 1 или 2.} 
          for i:= 3 to n do {Не выполняется, если n < 3.} 
          begin 
            Result:= N1 + N2; {Соответствует основной формуле чисел Фибоначчи.} 
            N2:= N1; {Сдвиг значений на один индекс.} 
            N1:= Result {Сдвиг значений на один индекс.} 
          end;
          Fi:= Result {Установка значения функции.} 
        end;
    

    К сравнительной оценке этих двух алгоритмов можно подходить с двух позиций: использования ресурсов ЭВМ и сложности написания и отладки программы.

  1. Ресурсы. В данном случае под ресурсами понимается время процессора и объем занятой программой (и данными) памяти.

        Рекурсивная программа включает следующие операции, занимающие время процессора: вызов функции, сравнение n с единицей и двойкой, сложение; при каждом вызове происходят сравнения и в части вызовов (если n>2) происходят сложения. Поэтому решающим параметром в оценке времени является количество вызовов функции. Все вызовы можно разбить на уровни следующим образом. На первом уровне находится единственный первый вызов с параметром n. На втором уровне находятся два вызова (с параметрами n-1 и n-2), произведенные при первом вызове. На третьем уровне находятся четыре вызова с параметрами n-2, n-3, n-3, n-4 и т. д. с увеличением количества на каждом уровне в два раза по отношению к предыдущему уровню до тех пор, пока величины n-i не начнут достигать значения 2. Эти вызовы можно изобразить в виде дерева (рисунок 1).

        Здесь для определенности взято n-7. Непросто оценить, сколько вершин (вызовов) в этом дереве, но можно быстро получить неравенства, ограничивающие это количество сверху и снизу. Левая ветвь помечена числами n, n-1, n-2, n-3, ..., 2. Следовательно, количество уровней не превосходит величины n-1. Правая ветвь помечена числами n, n-2, n-4, n-6 = 1. Можно сделать вывод, что количество уровней не меньше n/2. Если дерево имеет k уровней, то в нем 1+2+4+8+...+2k-1=2k вершин или, учитывая неравенство n-1 > k > n/2, получаем 2n-1-1 > число вызовов > 2n/2.


    Рис.1. Дерево вызовов рекурсивной функции вычисления чисел Фибоначчи

        Как верхняя, так и нижняя границы быстро растут с увеличением n. Уже при n=20 требуется не менее 1000 вызовов, хотя, как это ясно видно из дерева, многие вызовы дублируют друг друга - текст функции не предусматривает контроля дублирования. С каждым незавершенным вызовом функции связано хранение в стеке определенных данных (это обсуждалось, когда рассматривался механизм реализации рекурсии). Ввиду того, что проход по дереву производится в глубину, в любой момент времени требуется хранить от n-1 до n/2 групп данных.

        Итеративная программа включает сложения, пересылки (присваивания) и проверки (неявные) цикла на окончание. Занятость процессора в этом случае удобно оценить количеством исполнений тела цикла. Заголовок цикла ясно указывает на то, что тело цикла (одно сложение, три пересылки и команды управления циклом) выполняется n - 2 раза; кроме этого три пересылки (присваивания) в начале и одно в конце. Таким образом, количество операций может быть оценено формулой an+b. Количество использованной памяти - память для четырех переменных.

        Эти расчеты показывают явное преимущество итеративного метода в сравнении с рекурсивным по использованию ресурсов ЭВМ для решения данной задачи.

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

        С этой точки зрения рекурсивный алгоритм предпочтительнее итеративного.

        Анализ пунктов (А) и (Б) дает нам противоречивые советы. В случае таких простых задач как вычисление чисел Фибоначчи вопрос обычно решается в пользу ресурсов компьютера.

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

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

    Пусть x1, x2, x3, ..., xi, ..., xn - последовательность чисел (вещественных или целых, в зависимости от приложения), a<xi<b. Последовательность должна выдерживать статистические тесты, зависящие от того, какими свойствами должны обладать требуемые случайные числа. Например, если хотим иметь равномерно распределенные независимые случайные числа. Тогда сумма всех xi, отнесенная к n, должна приблизительно равняться (a+b)/2, взаимная корреляция значений xi, и хi+1 должна быть близка к нулю, на любые два различных участка одинаковой длины внутри интервала [a,b] должно попадать примерно одинаковое количество чисел xi.

    Существует очень много исследований, посвященных разработке методов программной генерации псевдослучайных чисел (они все-таки не случайные). Обзор некоторых из них приведен в книге Д. Кнута "Искусство программирования для ЭВМ" (Т. 2). Наиболее часто используется метод, предложенный в 1948 г. американским математиком Д. Лемером и названный линейным конгруэнтным методом. Этот метод применяется в большинстве датчиков, встроенных в компиляторы языков программирования. В вычислительном отношении он очень прост:

    xi+1 = (а*xi + с) mod m,

где a, c, m - целые положительные константы (c может быть равно 0).

    Обычно в некоторый момент времени прикладной программе нужно только одно число, поэтому процедура генерации может быть записана так:

    function RANDOM (x: integer): integer; 
    const   
      a = 25173;
      с = 13849;
      m = 65536; 
    begin
      RANDOM:= (a*x +c) mod m;
    end;

    Первый раз функция вызывается с некоторым аргументом х0, например, 12345. Значение хi = RANDOM (x0) нужно запомнить в прикладной программе с тем, чтобы получить следующее число x2 = RANDOM (x1) и так далее. Константы a, c, m, x0, конечно, могут быть выбраны и не такими как в этом примере. Однако теория чисел и модулярная арифметика часто преподносят сюрпризы, поэтому, прежде чем выбрать a, c и m, нужно познакомиться с соответствующей теорией (см. книгу Д. Кнута).

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

    Второй пример рекурсивного и итеративного решений - вычисление биномиальных коэффициентов. Высота бинарного дерева вызовов (количество уровней) равна n, хотя и не все ветви достигают такой длины. Следовательно, общее количество вызовов не превышает величины 2k-1.

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

    Ее можно использовать, не прибегая к вычислению факториалов. Пусть k - максимальное из двух значений: n-m и m, а l - минимальное. Тогда эта формула может быть сокращена:

    Она используется для непосредственного вычисления значения биномиальных коэффициентов:

    function BC(n, m: integer): integer;
    var 
      i, k, 1, p, q: integer;
    begin 
      if n - m >= m then 
        begin 
          k := n - m; 
          l := m;
        end 
      else 
        begin 
          k := m; 
          1 := n - m;
        end;
      P := 1; q := 1;
      for i := k + 1 to n do 
          p := p * i; 
      for i := 2 to 1 do 
          q := q * i; 
      ВС := р div q;
    end;

    В этом варианте не вычисляется ничего дважды, в отличие от рекурсивного, и количество операций линейно зависит от n.

    На следующем шаге мы рассмотрим реализацию механизма рекурсии.




Предыдущий шаг Содержание Следующий шаг