Рекурсия в программировании. Анализ алгоритмов

Рекурсия – это свойство объекта подражать самому себе. Объект является рекурсивным если его части выглядят также как весь объект. Рекурсия очень широко применяется в математике и программировании:

  • структуры данных:
    • граф (в частности деревья и списки) можно рассматривать как совокупность отдельного узла и подграфа (меньшего графа);
    • строка состоит из первого символа и подстроки (меньшей строки);
  • шаблоны проектирования, например декоратор[1]. Объект декоратора может включать в себя другие объекты, также являющиеся декораторами. Детально рекурсивные шаблоны изучил Мак-Колм Смит, выделив в своей книге общий шаблон проектирования – Recursion [2];
  • рекурсивные функции (алгоритмы) выполняют вызов самих себя.

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

Примеры рекурсивных  алгоритмов

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

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

Поиск элемента массива

начало; search(array, begin, end, element)
      ; выполняет поиск элемента со значением element в массиве array между индексами begin и end
если begin > end
  результат := false; элемент не найден
иначе если array[begin] = element
  результат := true; элемент найден
иначе
  результат := search(array, begin+1, end, element)
конец; вернуть результат

Алгоритм делит исходный массив на две части – первый элемент и массив из остальных элементов. Выделяется два простых случая, когда разделение не требуется – обработаны все элементы или первый элемент является искомым.

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

Двоичный поиск в массиве

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

начало; binary_search(array, begin, end, element)
      ; выполняет поиск элемента со значением element
      ; в массиве упорядоченном по возрастанию массиве array
      ; между индексами begin и end
если begin > end
  конец; вернуть false - элемент не найден
mid := (end + begin) div 2; вычисление индекса элемента посередине рассматриваемой части массива
если array[mid] = element
  конец; вернуть true (элемент найден)
если array[mid] < element
  результат := binary_search(array, mid+1, end, element)
иначе
  результат := binary_search(array, begin, mid, element)
конец; вернуть результат

Вычисление чисел Фибоначчи

Числа Фибоначчи определяются рекуррентным выражением, т.е. таким, что вычисление элемента которого выражается из предыдущих элементов: \(F_0 = 0, F_1 = 1, F_n = F_{n-1} + F_{n-2}, n > 2\).

начало; fibonacci(number)
если number = 0
  конец; вернуть 0
если number = 1
  конец; вернуть 1
fib_1 := fibonacci(number-1)
fib_2 := fibonacci(number-2)
результат := fib_1 + fib_2
конец; вернуть результат

Быстрая сортировка (quick sort)

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

рис. 1 блок-схема алгоритма быстрой сортировки

Блок-схема алгоритма быстрой сортировки

Сортировка слиянием (merge sort)

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

merge-sort_flowchart

Блок схема сортировки слиянием

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

начало; merge(Array1, Size1, Array2, Size2)
     ; исходные массивы упорядочены
     ; в результат формируется упорядоченный массив длины Size1+Size2
i := 0, j := 0
вечный_цикл
  если i >= Size1
    дописать элементы от j до Size2 массива Array2 в конец результата
    выход из цикла
  если j >= Size2
    дописать элементы от i до Size1 массива Array1 в конец результата
    выход из цикла
  если Array1[i] < Array2[j]
    результат[i+j] := Array1[i]
    i := i + 1
  иначе (если Array1[i] >= Array2[j])
    результат[i+j] := Array2[j]
    j := j + 1
конец; вернуть результат

 Анализ рекурсивных алгоритмов

При анализе сложности циклических алгоритмов рассчитывается трудоемкость итераций и их количество в наихудшем, наилучшем и среднем случаях [4]. Однако не получится применить такой подход к рекурсивной функции, т.к. в результате будет получено рекуррентное соотношение. Например, для функции поиска элемента в массиве:

\(
\begin{equation*}
T^{search}_n = \begin{cases}
\mathcal{O}(1) \quad &\text{$n = 0$} \\
\mathcal{O}(1) + \mathcal{O}(T^{search}_{n-1}) \quad &\text{$n > 0$}
\end{cases}
\end{equation*}
\)

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

Метод подстановки (итераций)

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

\(
T^{search}_n = \mathcal{O}(1) + \mathcal{O}(T^{search}_{n-1}) =
2\times\mathcal{O}(1) + \mathcal{O}(T^{search}_{n-2}) =
3\times\mathcal{O}(1) + \mathcal{O}(T^{search}_{n-3})
\)

Можно предположить, что \(T^{search}_n = T^{search}_{n-k} + k\times\mathcal{O}(1)\), но тогда  \(T^{search}_n = T^{search}_{0} + n\times\mathcal{O}(1) = \mathcal{O}(n)\).

Мы вывели формулу, однако первый шаг содержит предположение, т.е. не имеется доказательства соответствия формулы рекуррентному выражению – получить доказательство позволяет метод математической индукции.

Метод математической индукции

Позволяет доказать истинность некоторого утверждения (\(P_n\)), состоит из двух шагов:

  1. доказательство утверждения для одного или нескольких частных случаев \(P_0, P_1, …\);
  2. из истинности \(P_n\) (индуктивная гипотеза) и частных случаев выводится доказательство \(P_{n+1}\).

Докажем корректность предположения, сделанного при оценки трудоемкости функции поиска (\(T^{search}_n = (n+1)\times\mathcal{O}(1)\)):

  1. \(T^{search}_{1} = 2\times\mathcal{O}(1)\) верно из условия (можно подставить в исходную рекуррентную формулу);
  2. допустим истинность \(T^{search}_n = (n+1)\times\mathcal{O}(1)\);
  3. требуется доказать, что \(T^{search}_{n+1} = ((n+1)+1)\times\mathcal{O}(1) = (n+2)\times\mathcal{O}(1)\);
    1. подставим \(n+1\) в рекуррентное соотношение: \(T^{search}_{n+1} = \mathcal{O}(1) + T^{search}_n\);
    2. в правой части выражения возможно произвести замену на основании индуктивной гипотезы: \(T^{search}_{n+1} = \mathcal{O}(1) + (n+1)\times\mathcal{O}(1) = (n+2)\times\mathcal{O}(1)\);
    3. утверждение доказано.

Часто, такое доказательство – достаточно трудоемкий процесс, но еще сложнее выявить закономерность используя метод подстановки. В связи с этим применяется, так называемый, общий метод [5].

Общий (основной) метод решения рекуррентных соотношений

Общий метод не является универсальным, например с его помощью невозможно провести оценку сложности приведенного выше алгоритма вычисления чисел Фибоначчи. Однако, он применим для всех случаев использования подхода “разделяй и властвуй” [3]:

\(T_n = a\cdot T(\frac{n}{b})+f_n; a, b = const, a \geq 1, b > 1, f_n > 0, \forall n\).

Уравнения такого вида получаются если исходная задача разделяется на a подзадач, каждая из которых обрабатывает \(\frac{n}{b}\) элементов. \(f_n\) – трудоемкость операций разбиения задачи на части и комбинирование решений. Помимо вида соотношения, общий метод накладывает ограничения на функцию \(f_n\), выделяя три случая:

  1. \(\exists \varepsilon > 0 : f_n = \mathcal{O}(n^{\log_b a – \varepsilon}) \Rightarrow T_n = \Theta(n^{\log_b a})\);
  2. \(f_n = \Theta(n^{\log_b a}) \Rightarrow T_n = \Theta(n^{\log_b a} \cdot \log n)\);
  3. \(\exists \varepsilon > 0, c < 1 : f_n = \Omega(n^{\log_b a + \varepsilon}), f_{\frac{n}{b}} \leq c \cdot f_n \Rightarrow T_n = \Theta(f_n)\).

Правильность утверждений для каждого случая доказана формально [6]. Задача анализа рекурсивного алгоритма теперь  сводится к определению случая основной теоремы, которому соответствует рекуррентное соотношение.

Анализ алгоритма бинарного поиска

Алгоритм разбивает исходные данные на 2 части (b = 2), но обрабатывает лишь одну из них (a = 1), \(f_n = 1\). \(n^{\log_b a} = n^{\log_2 1} = n^0 = 1\). Функция разделения задачи и компоновки результата растет с той же скоростью, что и \(n^{\log_b a}\), значит необходимо использовать второй случай теоремы:

\(T^{binarySearch}_n = \Theta(n^{\log_b a} \cdot \log n) = \Theta(1 \cdot \log n) = \Theta(\log n)\).

Анализ алгоритма поиска

Рекурсивная функция разбивает исходную задачу на одну подзадачу (a = 1), данные делятся на одну часть (b = 1). Мы не можем использовать основную теорему для анализа этого алгоритма, т.к. не выполняется условие \( b > 1\).

Для проведения анализа может использоваться метод подстановки или следующие рассуждения: каждый рекурсивный вызов уменьшает размерность входных данных на единицу, значит всего их будет n штук, каждый из которых имеет сложность \( \mathcal{O}(1)\). Тогда \(T^{search}_n = n \cdot \mathcal{O}(1) = \mathcal{O}(n)\).

Анализ алгоритма сортировки слиянием

Исходные данные разделяются на две части, обе из которых обрабатываются: \(a = 2, b = 2, n^{\log_b a} = n\).

При обработке списка, разделение может потребовать выполнения \(\Theta(n)\) операций, а для массива – выполняется за постоянное время (\(\Theta(1)\)). Однако, на соединение результатов в любом случае будет затрачено \(\Theta(n)\), поэтому \(f_n = n\).

Используется второй случай теоремы: \(T^{mergeSort}_n = \Theta(n^{\log_b a} \cdot \log n) = \Theta(n \cdot \log n)\).

Анализ трудоемкости быстрой сортировки

В лучшем случае исходный массив разделяется на две части, каждая из которых содержит половину исходных данных. Разделение потребует выполнения n операций. Трудоемкость компоновки результата зависит от используемых структур данных – для массива \(\mathcal{O}(n)\), для связного списка \(\mathcal{O}(1)\). \(a = 2, b = 2, f_n = b\), значит сложность алгоритма будет такой же как у сортировки слиянием: \(T^{quickSort}_n = \mathcal{O}(n \cdot \log n)\).

Однако, в худшем случае в качестве опорного будет постоянно выбираться минимальный или максимальный элемент массива. Тогда \(b = 1\), а значит, мы опять не можем использовать основную теорему. Однако, мы знаем, что в этом случае будет выполнено n рекурсивных вызовов, каждый из которых выполняет разделение массива на части (\(\mathcal{O}(n)\)) – значит сложность алгоритма \(T^{quickSort}_n = \mathcal{O}(n^2)\).

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

Хвостовая рекурсия и цикл

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

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

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

В ряде случаев рекурсивную функцию достаточно легко заменить циклом, например, рассмотренные выше алгоритмы поиска и бинарного поиска [4]. В некоторых случаях требуется более творческий подход, но чаще всего такая замена оказывается возможной. Кроме того, существует особый вид рекурсии, когда рекурсивный вызов является последней операцией, выполняемой функцией. Очевидно, что в таком случае вызывающая функция не будет каким-либо образом изменять результат, а значит ей нет смысла возвращать управление. Такая рекурсия называется хвостовой – компиляторы автоматически заменяют ее циклом.

Зачастую сделать рекурсию хвостовой помогает метод накапливающего параметра [7], который заключается в добавлении функции дополнительного аргумента-аккумулятора, в котором накапливается результат. Функция выполняет вычисления с аккумулятором до рекурсивного вызова. Хорошим примером использования такой техники служит функция вычисления факториала:
\(fact_n = n \cdot fact(n-1) \\
fact_3 = 3 \cdot fact_2 = 3 \cdot (2 \cdot fact_1) = 3\cdot (2 \cdot (1 \cdot fact_0)) = 6 \\
fact_n = factTail_{n, 1} \\
\\
factTail_{n, accumulator} = factTail(n-1, accumulator \cdot n)\\
factTail_{3, 1} = factTail_{2, 3} = factTail_{1, 6} = factTail_{0, 6} = 6
\)

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

начало; fibonacci(number)
вернуть fibonacci(number, 1, 1, 0)
конец

начало; fibonacci(number, iterator, fib1, fib2)
  если iterator == number вернуть fib1
  вернуть fibonacci(number, iterator + 1, fib1 + fib2, fib1)
конец

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

Литература

  1. Многопоточный сервер Qt. Пул потоков. Паттерн Decorator[Электронный ресурс] – режим доступа: https://pro-prof.com/archives/1390. Дата обращения: 21.02.2015.
  2. Джейсон Мак-Колм Смит Элементарные шаблоны проектирования : Пер. с англ. — М. : ООО “И.Д. Вильямс”, 2013. — 304 с.
  3. Скиена С. Алгоритмы. Руководство по разработке.-2-е изд.: пер. с англ.-СПб.:БХВ-Петербург, 2011.-720с.: ил.
  4. Васильев В. С. Анализ сложности алгоритмов. Примеры [Электронный ресурс] – режим доступа: https://pro-prof.com/archives/1660. Дата обращения: 21.02.2015.
  5.  А.Ахо, Дж.Хопкрофт, Дж.Ульман, Структуры данных и алгоритмы, М., Вильямс, 2007.
  6. Миллер, Р. Последовательные и параллельные алгоритмы: Общий подход / Р. Миллер, Л. Боксер ; пер. с англ. — М. : БИНОМ. Лаборатория знаний, 2006. — 406 с.
  7. Сергиевский Г.М. Функциональное и логическое программирование : учеб. пособие для студентов высш. учеб. заведений / Г.М. Сергиевский, Н.Г. Волченков. — М.: Издательский центр «Академия», 2010.- 320с.

4 thoughts on “Рекурсия в программировании. Анализ алгоритмов

  1. Александр

    Скажите, а вы не встречали языка в котором рекурсивная функция могла бы вызывать себя не зная своего имени?

    Reply
    1. admin Post author

      Нет, не встречал. Я не думаю что такой язык существует, по крайней мере, вы описываете бесполезную “особенность”. Зачем это?

      Т.е. в любом случае произойдет вызов функции. Если вызов не хвостовой – то управление надо будет точно также вернуть назад.

      Такая “фича” не упростит ни восприятие кода, ни его оптимизацию.

      Reply
    2. admin Post author

      Кстати, по оптимизации… Во многих языках оптимизация хвостовой рекурсии – это частный случай оптимизации хвостового вызова (tail call elimination). В не зависимости от того является хвостовой вызов рекурсивным или нет – возвращать управление в вызывающую функцию не требуется (в последней части статьи описаны причины).

      Tail call elimination срабатывает гораздо чаще, например, вы пишите функцию решения квадратных уравнений и в ней есть такой фрагмент:

      если дискриминант > 0
        вернуть результат вызова two_roots(a, b, c);
      если дискриминант = 0
        вернуть результат вызова single_roots(a, b, c);
      

      .
      Тут оба вызова вспомогательных функций являются хвостовыми.

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

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

      Мне просто не понятны всякие синтаксические излишества.

      Reply

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

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

Вы не робот? *