Что значит рекурсивно. Отличия рекурсии в различных языках программирования. Как же решать задачи на рекурсию

От лат recursio (возвращение). В общем случае так называется процесс повторения элементов «самоподобным образом».

Яркий пример рекурсии - матрёшки. Рекурсивное определение: «матрёшка - это разъемная пустотелая деревянная кукла, содержащая внутри матрёшку меньшего размера». Вот такая рекурсия по-русски. И если бы не предел возможностей мастеров, идеальная матрёшка уходила бы в глубь себя до атомарного уровня. А то и глубже. Просто у Левши не нашлось мелкоскопа достаточной силы. Верхний предел теоретически тоже не ограничен, но баобабы подходящего размера на нашей планете не растут. В общем, по техническим причинам рекурсия должна быть конечной.

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

Пример рекурсии

Самый надоевший пример рекурсии в математическом программировании - вычисление факториала. Не будем изменять славным традициям. Для тех, кто еще не проходил: N! (факториал N) - это произведение всех натуральных чисел от единицы до N (факториал нуля равен 1).
Можно тупо перемножать числа от 1 до N в цикле. А можно соорудить функцию factorial(n), которая будет содержать условие и вызов самой себя. Если n равно единице, то функция возвращает значение 1, иначе возвращает значение n, умноженное на factorial(n-1).
Зарисовка на PHP

Function factorial($n) { if ($n == 1) { return 1; } else { return intval($n * factorial($n - 1)); } }

Практические применения рекурсии

«Ну, и зачем это здесь нужно?» - спросит нас нетерпеливый юный читатель - «Чушь научная, занудство, факториалы всякие… А практически к чему эту рекурсию приложить?»
«К подбитому глазу веб-программированию» - без колебаний ответим мы. И тут же это обоснуем.

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

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

Рекурсия в поисковых системах

Да, именно так. Поисковым системам от рекурсии тоже некуда деваться. С тех пор, как был заведен обычай мерить авторитетность сайта (документа) количеством ссылок, поисковики попались в рекурсивную ловушку, и пусть они блуждают в ней вечно (это искреннее доброе пожелание автора). Ссылочный «вес» сайта складывается из маленьких кусочков «веса» от всех тех, которые на него ссылаются. Чтобы вычислить этот вес для A, на которого ссылаются B, C и D, надо обсчитать их вес, который в свою очередь передается всякими другими, вес которых тоже нужно обсчитывать… и так по всей учтенной в поисковике Сети. Совершенно рекурсивная задачка. А вы говорите - сплошная теория. Самая что ни на есть реальная практика.

Рекурсивный PageRank от Google

Свой базовый алгоритм расчета PageRank создатели Google опубликовали давно. И как бы он с тех пор ни менялся, сколько бы его ни дополняли усовершенствованиями, основа остается прежней. Нельзя узнать, какую величину PageRank страница B передает по ссылке странице A, пока мы не сосчитали, какой PageRank получила страница B от всех прочих страниц, которые на нее сослались, а этого нельзя узнать, пока мы не посчитаем PageRank этих страниц… продолжать? Наверное, уже не надо. Это опять Она - Её Величество Рекурсия .

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

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

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

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

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

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

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

начало; search(array, begin, end, element) ; выполняет поиск элемента со значением element в массиве array между индексами begin и end если begin > end результат:= false; элемент не найден иначе если array = 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 = element конец; вернуть true (элемент найден) если array < 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)

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

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

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

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

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

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

Начало; 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] результат := Array1[i] i:= i + 1 иначе (если Array1[i] >= Array2[j]) результат := Array2[j] j:= j + 1 конец; вернуть результат

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

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

\(
\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. утверждение доказано.

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

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

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

\(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)\).

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

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

Алгоритм разбивает исходные данные на 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) — в него помещаются номер команды для возврата и информация о локальных переменных. Стек не является бесконечным, поэтому рекурсивные алгоритмы могут приводить к его переполнению, в любом случае на работу с ним может уходить значительная часть времени.

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

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

Подпрограммы в Паскале могут обращаться сами к себе. Такое обращение называется рекурсией .

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

Пример .

Рассмотрим математическую головоломку из книги Ж. Арсака «Программирование игр и головоломок».

Построим последовательность чисел следующим образом: возьмем целое число i>1. Следующий член последовательности равен i/2, если i четное, и 3 i+1, если i нечетное. Если i=1, то последовательность останавливается.

Математически конечность последовательности независимо от начального i не доказана, но на практике последовательность останавливается всегда.

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

Пример программы с использованием рекурсии

Program Arsac;
Var first: word;
Procedure posledov (i: word);
Begin
Writeln (i);
If i=1 then exit;
If odd(i) then posledov(3*i+1) else posledov(i div 2);
End;
Begin
Write (" введите первое значение "); readln (first);
Posledov (first);
Readln ;
End.

Программист разрабатывает программу, сводя исходную задачу к более простым. Среди этих задач может оказаться и первоначальная, но в упрощенной форме. Например, для вычисления F(N) может понадобиться вычислить F(N-1). Иными словами, частью алгоритма вычисления функции будет вычисление этой же функции.

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

N! = (N-1)!* N, если N=0, то N!= 1

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

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

2n= 2 n-1*2, если n=0, то 2 n= 1

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

Заметим, что при косвенном обращении все процедуры в цепочке – рекурсивные.

Все сказанное о процедурах целиком относится и к функциям.

Пример рекурсивной функции вычисления факториала

Function factorial(N: integer) : longint;
Begin
If N= 0 then
Factorial:= 1
Else Factorial:= factorial(N-1) * N
End;

Рекурсия изнутри

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

• в памяти размещаются параметры, передаваемые процедуре (но не параметры-переменные!);
• в другом месте памяти сохраняются значения внутренних переменных вызывающей процедуры;
• запоминается адрес возврата в вызывающую процедуру;
• управление передается вызванной процедуре.

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

Пусть рекурсивная процедура Power(X, N, Y) возводит число X в степень N и возвращает результат Y .

Пример рекурсивной процедуры, возводящей число в степень

Procedure Power (X: real; N: integer; var Y: real);
Begin
If N=0 then
Y:= 1
Else Begin Power(X, N-1,Y);
Y:= Y*X;
End ;
End ;

Проследим за состоянием памяти в процессе выполнения вызова данной процедуры Power(5,3, Y). Стрелка «->» означает вход в процедуру, стрелка «

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

Подведем итог.

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

Напишем программу вычисления функции, заданной следующим образом:

F(1)=1; F(2n)=F(n); F(2n+1)=F(n)+F(n+1)

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

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

• Определение четности или нечетности аргумента. От этого зависит выбор формулы вычислений;
• Выполнение вычислений. Фактически это будет сводиться к определению нового аргумента функции.

Пример рекурсивной программы вычисления функции

Program primer;
Uses crt;
Var
N, a: integer;
Function f(n:integer):integer;
Begin
If n =1 then
f:=1 {условие завершения рекурсии}
Else
Begin
If odd (n){проверка на нечетность числа}
then begin
n:= n div 2;
f:=f(n)+f(n+1)
end
else begin
n:= n div 2;
f:=f(n)
end;
end ;
end ;
clrscr;
write(" Введите число – ");
readln(n);
a:=f(n);
write(" результат – ", a);
end.

Рекурсивная программа построения снежинки

Написать программу, строящую на экране изображение:

Изображение строится по следующему правилу: строится окружность с заданным радиусом r. Затем на диаметрально противоположных точках окружности (x- r и x+ r)строится вновь окружность меньшего радиуса (r=3 r/5). Для каждой меньшей окружности на диаметрально противоположных точках вновь строится окружность меньшего радиуса, и т.д., пока радиус не уменьшится до 10.

program recurs;
uses graph;
var x,y,r,d,m:integer;
var i:integer;
begin
if r circle(x,y,r);
for i:=1 to 1000 do; { просто цикл задержки }
ris(x+r,y,r*3 div 5);
ris(x-r,y,r*3 div 5);
end ;
begin {начало основной программы}
d:=detect;
x:=320;
y:=240;
r:=120;
ris(x,y,r);
readln ;
end.

Как видно из рисунка, здесь опять повторяются одни и те же фрагменты. Построение выполняется так: на окружности заданного радиуса r берется 6 равноотстоящих точек (начиная от угла в 0 0, с шагом?/3), из каждой точки к центру окружности проводятся радиусы. Затем каждая из этих точек выступает центром новой, меньшей окружности с радиусом r=2 r/5. На каждой меньшей окружности вновь берется 6 равноотстоящих точек, из которых строятся радиусы к центру, и т.д., пока радиус не станет меньше или равен 1.

program sneg;
uses graph, crt;
var
x,y,r,d,m:integer;
procedure ris(x,y,r:integer);
var
x1,y1,t:integer;
begin
if r for t:=0 to 6 do
begin
x1:=x+trunc(r*cos(t*pi/3));
y1:=y+trunc(r*sin(t*pi/3));
line(x,y,x1,y1);
ris(x1,y1,r*2 div 5);
delay(500);
end;
end;
begin
d:=detect;
initgraph(d,m,"e:\bp\bgi");
x:=320;
y:=240;
r:=80;
ris(x,y,r);
readln;
end.

Пример «Кривой Дракона».

Рассмотрим пример решения еще одной классической задачи: «Кривая Дракона».

Изображение кривой Дракона выглядит так:

Очень красиво, не правда ли. Разберемся, как же эта кривая получается.

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

Кривая дракона впервые была описана в популярной литературе в журнале Scientific American в 1967 году. Заметка о ней появилась в колонке “Математические игры”, которую вел Мартин Гарднер. Первоначально использовалось полное название кривой – «дракон Хартера - Хейтуэя», которое ей дал основатель компьютерной фрактальной геометрии Бенуа Мандельброт, именем которого названо знаменитое множество. В дальнейшем стали говорить просто о кривой дракона. Выше мы описали один из алгоритмов построения кривой. На наш взгляд, он несколько запутан (хотя и достаточно прост в реализации). Приведем описание алгоритма построение кривой, близкое к тому, которое использовалось Мартином Гарднером.

Рассмотрим горизонтальный отрезок как кривую дракона нулевого порядка. Разделим отрезок пополам и построим на нем прямой угол, как показано на рис . а).

Получим кривую дракона первого порядка. На сторонах прямого угла снова построим прямые углы (рис . б).

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

program dragon;
uses graph;
var k,d,m:integer;
procedure ris(x1,y1,x2,y2,k:integer);
var xn,yn:integer;
begin
if k>0 then
begin
xn:=(x1+x2) div 2 +(y2-y1) div 2;
yn:=(y1+y2) div 2 -(x2-x1) div 2;
ris(x1,y1,xn,yn,k-1);
ris(x2,y2,xn,yn,k-1);
end
else begin line(x1,y1,x2,y2); end;
end;
begin
readln (k);{задаем порядок кривой}
d:=detect;
initgraph(d,m,"e:\bp\bgi");
ris(200,300,500,300,k);
readln;
end.

В осточноукраинский национальный университет имени Владимира Даля

Рекурсия

Информатика и компьютерная техника

© Велигура А.В., кафедра экономической кибернетики, 2004

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

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

Что такое рекурсия?

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

Function Factorial(num As Long) As Long

Factorial = num * Factorial(num - 1)

В случае косвенной рекурсии (indirectrecursion) рекурсивная процедура вызывает другую процедуру, которая, в свою очередь, вызывает первую:

Private Sub Ping(num As Integer)

Private Sub Pong(num As Integer)

Рекурсия полезна при решении задач, которые естественным образом разбиваются на несколько подзадач, каждая из которых является более простым случаем исходной задачи. Можно представить дерево в виде «ствола», на котором находятся два дерева меньших размеров. Тогда можно написать рекурсивную процедуру для рисования деревьев:

Private Sub DrawTree()

Нарисовать "ствол"

Нарисовать дерево меньшего размера, повернутое на -45 градусов

Нарисовать дерево меньшего размера, повернутое на 45 градусов

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

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

1. Опасности рекурсии

   1. Бесконечная рекурсия

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

Private Function BadFactorial(num As Integer) As Integer

BadFactorial = num * BadFactorial (num - 1)

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

Private Function BadFactorial2(num As Double) As Double

BadFactorial2 = 1

BadFactorial2 = num * BadFactorial2(num-1)

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

Private Function BadFib(num As Double) As Double

BadFib = BadPib(num - 1) + BadFib (num - 2)

И последняя проблема, связанная с бесконечной рекурсией, заключается в том, что «бесконечная» на самом деле означает «до тех пор, пока не будет исчерпано стековое пространство». Даже корректно написанные рекурсивные процедуры будут иногда приводить к переполнению стека и аварийному завершению работы. Следующая функция, которая вычисляет сумму N + (N - 1) + … + 2 +1, приводит к исчерпанию стекового пространства при больших значенияхN. Наибольшее возможное значениеN, при котором программа еще будет работать, зависит от конфигурации вашего компьютера.

Private Function BigAdd(N As Double) As Double

If N <= 1 Then

BigAdd=N + BigAdd(N - 1)

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

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

Данные

Struct element_of_list { element_of_list * next; /* ссылка на следующий элемент того же типа */ int data; /* некие данные */ } ;

Рекурсивная структура данных зачастую обуславливает применение рекурсии для обработки этих данных.

В физике

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

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

В лингвистике

Способность языка порождать вложенные предложения и конструкции. Базовое предложение «кошка съела мышь » может быть за счёт рекурсии расширено как Ваня догадался, что кошка съела мышь , далее как Катя знает, что Ваня догадался, что кошка съела мышь и так далее. Рекурсия считается одной из лингвистических универсалий , то есть свойственна любому естественному языку. Однако, в последнее время активно обсуждается возможное отсутствие рекурсии в одном из языков Амазонии - пираха, которое отмечает лингвист Дэниэл Эверетт (англ. ) .

В культуре

Большая часть шуток о рекурсии касается бесконечной рекурсии, в которой нет условия выхода, например, известно высказывание: «чтобы понять рекурсию, нужно сначала понять рекурсию» .

Весьма популярна шутка о рекурсии, напоминающая словарную статью:

Несколько рассказов Станислава Лема посвящены (возможным) казусам при бесконечной рекурсии:

• рассказ про Йона Тихого «Путешествие четырнадцатое» из «Звёздных дневников Ийона Тихого », в котором герой последовательно переходит от статьи о сепульках к статье о сепуляции, оттуда к статье о сепулькариях, в которой снова стоит отсылка к статье «сепульки»:

Нашёл следующие краткие сведения:
«СЕПУЛЬКИ - важный элемент цивилизации ардритов (см.) с планеты Энтеропия (см.). См. СЕПУЛЬКАРИИ».
Я последовал этому совету и прочёл:
«СЕПУЛЬКАРИИ - устройства для сепуления (см.)».
Я поискал «Сепуление»; там значилось:
«СЕПУЛЕНИЕ - занятие ардритов (см.) с планеты Энтеропия (см.). См. СЕПУЛЬКИ».

Лем С. «Звёздные дневники Ийона Тихого. Путешествие четырнадцатое.»

• Рассказ из «Кибериады» о разумной машине, которая обладала достаточным умом и ленью, чтобы для решения поставленной задачи построить себе подобную, и поручить решение ей (итогом стала бесконечная рекурсия, когда каждая новая машина строила себе подобную и передавала задание ей).
• Рекурсивные акронимы : GNU (GNU Not Unix), PHP (PHP: Hypertext Preprocessor) и т. д.

См. также

• Возвратная последовательность

Примечания

Wikimedia Foundation . 2010 .

• Видеопамять
• Электромагнитное излучение

Смотреть что такое "Рекурсия" в других словарях:

рекурсия - возвращение, повторение Словарь русских синонимов. рекурсия сущ., кол во синонимов: 1 … Словарь синонимов

рекурсия - — [] рекурсия В общем смысле вычисление функции по определенному алгоритму. Примерами таких алгоритмов являются рекуррентные формулы, выводящие вычисление заданного члена… … Справочник технического переводчика

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

Рекурсия - Терапевтический паттерн, когда берётся некоторое условие или критерий, сформулированный в исходном утверждении, и применяется к самому утверждению. Например: У меня нет времени. Сколько времени вам пришлось потратить, чтобы убедиться, что у вас… … Большая психологическая энциклопедия

РЕКУРСИЯ - способ определения функций, являющийся объектом изучения в теории алгоритмов и других разделах математич. логики. Этот способ давно применяется в арифметике для определения числовых последовательностей (прогрессии, чисел Фибоначчи и пр.).… … Математическая энциклопедия

рекурсия - (фон.) (лат. recursio возвращение). Одна из трех фаз артикуляции звуков, отступ. Перевод органов речи в спокойное состояние или приступ к артикуляции следующего звука. В слове отдых рекурсия (отступ) при артикулировании [т] может наложиться на… … Словарь лингвистических терминов Т.В. Жеребило