25. Понятие рекурсии. Глубина рекурсии. Механизм реализации рекурсий в языках программирования.
Под рекурсивным понимают способ описания понятий процессов функции через самих себя. Рекурсивное решение предполагает разбиение(разложение) на совокупность подзадач, таким образом, что любые 2 подзадачи либо не пересекались, либо одна из них является подзадачей другой. Среди этих подзадач должна быть хотя бы одна подзадача, которая определяет тривиальный случай –случай, когда задача решается непосредственно, — хотя бы одна подзадача определяет непосредственное решение, и должна быть хотя бы одна подзадача, которая определяет общий случай решения задачи. При этом общий случай решения задачи является способом сведения общей задачи к решению одной или нескольких простых (тривиальных) задач. Общий способ решения задач – это, как правило, способ, при котором происходит снижение размерности задачи. Процесс, сведения общей задачи к простой, называют разворачиванием рекурсий. После того, как рекурсия развернута, т.е. сведена к простой задаче, которая может быть решена непосредственно, выполняется процесс сворачивания рекурсии. На этом этапе происходит обобщение простого решения и переход, таким образом, к решению сложной задачи. Глубина рекурсии – количество шагов для сведения общей задачи к частной. Используя рекурсивное решение задачи идет оценка глубины рекурсии. Поэтому, прибегать к рекурсивному решению задачи необходимо, когда сама природа задачи является рекурсивной. Это проявляется если:
1. обрабатываемые данные имеют рекурсивную природу
2. нет для задачи итеративного способа решения – в этом случае применяют метод полного или частичного перебора возможных вариантов решения задачи.
Для реализации рекурсии в я.п. предлагается механизм, состоящий в возможности обращения подпрограммы к самой себе. Когда происходит очередной вызов подпрограммы, создаются новые экземпляры (поколения) формальных параметров и внутренних (локальных) переменных. При этом определено правило доступности экземпляров переменных – на некотором уровне рекурсии или же вызове подпрограмм доступны только те экземпляры переменных, которые соответствуют этому вызову. Для реализации правила доступности переменных используется стековая память – область памяти с определенным правилом обращения к элементам. Это правило состоит в следующем – в стеке доступен тот элемент, который был помещен в него последним. Непосредственная рекурсия – когда подпрограмма вызывает сама себя. Косвенная рекурсия – существует функция А, которая вызывает функцию В, которая, в свою очередь, вызывает функцию А. В стековой памяти хранятся не только значения подпрограмм, но и для каждого уровня рекурсии хранится текущее состояние подпрограмм. Для того, чтобы избежать при рекурсивном решении повторных вычислений одних и тех же величин необходимо передавать результаты промежуточных вычислений с одного уровня рекурсии на другой. Нет общего правила выполнения для каждой задачи, в каждой задаче это решается непосредственно для этой задачи, но с использованием дополнительных переменных. Реализация решения может проходить в одной из трех форм описания рекурсивного решения:
1. говорит о том, что реализация решения осуществляется на этапе рекурсивного разворачивания (спуска)
2. задача решается на этапе сворачивания рекурсий
Вызов подпрограммы; s>
3. когда часть задачи решается на этапе разворачивания, а часть – на этапе сворачивания
Рекурсия
Рекурсия — это жемчужина теории алгоритмов, и это первое, с чем знакомят школьников (сразу после процедур ввода и вывода данных, элементарных арифметических операций, оператора цикла и условного оператора).
Простота рекурсии обманчива. Метод рекурсии таит в себе много опасностей и сложностей, и в то же время готовит много приятных сюрпризов.
Давно известен такой математический приём, как разбиение задачи на простые шаги, каждый из которых тоже можно разложить на более мелкие шаги и так далее, пока не доберёмся до самых элементарных «шажочков».
Представим, что нужно пройти 1000 шагов. Для решения делаем один шаг, остаётся 999: задача упростилась. Сделав такое упрощение 999 раз, дойдём до самой элементарной задачи — шагнуть один раз. Конечно, этот пример слишком прост. Далее мы рассмотрим более сложные примеры, освещающие явление рекурсии как с хорошей так, и с плохой стороны.
Вы, наверное, уже заметили сходство понятий рекурсии и математической индукции. У рекурсии, как и у математической индукции, есть база — аргументы, для которых значения функции определены (элементарные задачи), и шаг рекурсии — способ сведения задачи к более простым.
Содержание
Числа Фибоначчи [ править ]
Современные языки программирования дают возможность программировать рекурсивные определения без особых усилий, но в таких определениях таятся опасности.
Проблемы рекурсии и как их решать [ править ]
Есть способ решить проблему повторных вычислений. Он очевиден — нужно запоминать найденные значения, чтобы не вычислять их каждый раз заново. Конечно, для этого придётся активно использовать память.
Например, рекурсивный алгоритм вычисления чисел Фибоначчи легко дополнить тремя «строчками»:
- создать глобальный массив F D <\displaystyle FD>, состоящий из нулей;
- после вычисления числа Фибоначчи F ( n ) <\displaystyle F(n)>поместить его значение в F D [ n ] <\displaystyle FD[n]>;
- в начале рекурсивной процедуры сделать проверку на то, что F D [ n ] = 0 <\displaystyle FD[n]=0>и, если F D [ n ] ≠ 0 <\displaystyle FD[n]\neq 0>, то вернуть F D [ n ] <\displaystyle FD[n]>в качестве результата, а иначе приступить к рекурсивному вычислению F ( n ) <\displaystyle F(n)>.
Такая рекурсия с запоминанием называется динамическим программированием сверху.
Рекурсию с запоминанием для вычисления чисел Фибоначчи мы привели просто для демонстрации идеи. Для чисел Фибоначчи есть простой «человеческий алгоритм», не использующий рекурсивные вызовы и запоминание всех вычисленных значений. Достаточно помнить два последних числа Фибоначчи, чтобы вычислить следующее. Затем предпредыдущее можно «забыть» и перейти к вычислению следующего:
- a = b = 1 <\displaystyle a=b=1>;
- если n > 2 <\displaystyle n>2>, то сделать n − 2 <\displaystyle n-2>раз: c = a + b <\displaystyle c=a+b>; a = b <\displaystyle a=b>; b = c <\displaystyle b=c>;
- вернуть ответ b <\displaystyle b>;
Особенно просто и наглядно функцию вычисления чисел Фибоначчи можно задать на языке Mathematica (см. http://www.wolfram.com):
Простое рекурсивное определение: F(n_) := F(n-1) + F(n-2); F(1) = F(2) = 1;
Рекурсивное определение с запоминанием: F[n_] := (F[n] = F[n-1] + F[n-2]); F[1] = F[2] = 1;
Задача 1 [ править ]
Задача 2 [ править ]
Задача 3 [ править ]
Задача 4 [ править ]
Задача о золотой горе [ править ]
На международной олимпиаде по информатике в 1994 году в первый день среди прочих задач была дана следующая задача.
Формулировка задачи: На рисунке показан пример треугольника из чисел. Написать программу, вычисляющую наибольшую сумму чисел, через которые проходит путь, начинающийся на вершине и заканчивающийся где-то на основании.
- Каждый шаг может идти диагонально вниз направо или диагонально вниз налево.
- Количество строк в треугольнике > 1 <\displaystyle >1>, но < 100 <\displaystyle <100>.
- Числа в треугольнике все целые от 0 до 99 включительно.
В примере, описанном выше, это путь 7, 3, 8, 7, 5, дающий максимальную сумму 30.
Входные данные Информация о количестве строк в треугольнике это первое число в файле INPUT.TXT , далее записана информация о треугольнике построчно. Выходные данные Наибольшая сумма, записанная как целое число в файл OUTPUT.TXT . Для нашего примера это будет число 30.
В примере, описанном выше, это путь 7, 3, 8, 7, 5, дающий максимальную сумму 30.
Пример входных данных:
Эту задачу можно встретить и под названием «Золотая гора» — нужно спуститься с горы и собрать как можно больше золота.
На рисунке обозначены две горки (треугольники): одна с вершиной в числе 3, другая с вершиной в числе 8. Эти горки пересекаются, и их пересечение тоже горка с вершиной в числе 1. Можно заметить, что при вычислении самого лучшего пути по рекурсивному алгоритму горка с вершиной в числе 1 будет использоваться дважды. Для горок с вершинами в нижних строчках повторных вызовов будет ещё больше. Это и есть причина медленности работы алгоритма.
Решить эту задачу за разумное время помогает динамическое программирование. Суть динамического программирования хорошо описана в книге Р. Беллмана [1] . Есть и более современные учебники [2] , [3] , в них можно найти много интересных алгоритмов, основанных на динамическом программировании.
Задача 5 [ править ]
Эта задача показывает, что придумать рекурсивный алгоритм часто намного проще, чем не рекурсивный. Также несложно добавить к рекурсии запоминание вычисленных значений. Но нередко существует более быстрый алгоритм, основанный на динамическом программировании, который использует меньше памяти, нежели рекурсия с запоминанием, и делает в два раза меньше операций обращения к памяти.
Задача «Сделай палиндром» [ править ]
Палиндром — это последовательность символов, которая слева-направо и справа-налево пишется одинаково. Например «АБА» или «АББ ББА». Дана последовательность символов. Какое минимальное количество символов нужно удалить из неё, чтобы получить палиндром?
Длина последовательности не больше 20 символов. Ограничение на время работы программы: 5 секунд.
Пример: Вход: ТИТ ЕЛЕ ЛЕТИТ . Выход: 2
Эта задача давалась на районной олимпиаде школьников Удмуртской республики в 1998 году. Рассмотрим её решение, основанное на рекурсии.
Если строка имеет вид h α t <\displaystyle
Базой рекурсии являются строки из одного символа и пустая строка — все они палиндромы по определению, и для них S = 0 <\displaystyle S=0>. Шаг рекурсии состоит из двух частей:
Алгоритм Евклида [ править ]
Даны два натуральных числа. Найти самое большое натуральное число, которое делит оба без остатка. Такое число называется наибольший общий делитель (НОД) (GCD — Greatest Common Divisor).
Пример: Вход: 18, 600 Выход: 6
Есть очень простой алгоритм: давайте перебирать все числа от минимального из заданных до 1 и проверять, делит ли очередное число оба заданных. Первое такое число и будет НОД. У этого алгоритма есть существенный недостаток — маленькая скорость работы. Например для чисел 1 000 000 001 <\displaystyle 1\,000\,000\,001>и 1 000 000 000 <\displaystyle 1\,000\,000\,000>придётся выполнить 1 000 000 000 <\displaystyle 1\,000\,000\,000>проверок. Более эффективно эту задачу решает алгоритм Евклида, основанный на двух простых свойствах GCD ( a , b ) <\displaystyle \operatorname
- G C D ( a , K a ) = a <\displaystyle GCD(a,Ka)=a>, где K <\displaystyle K>— натуральное число;
- Если a < b <\displaystyle a<b>, то G C D ( a , b ) = G C D ( a , b − a ) <\displaystyle GCD(a,b)=GCD(a,b-a)>.
Рассмотрим второе свойство. При замене одного из чисел на его разность с первым, наибольший общий делитель остаётся прежним.
Задача 6 [ править ]
Задача 7 [ править ]
При построении рекурсивной функции важно ответить на следующие вопросы:
- Что будет базой рекурсии?
- Что будет шагом рекурсии?
- Почему выполнение шагов рекурсии всегда приведёт к базе?
- Какова будет глубина рекурсии при данном значении аргументов? Глубина рекурсии — это глубина дерева рекурсивных вызовов, то есть длина максимального пути по стрелочкам из вершины до одного из элементарных (базовых) значений функции.
- Как растёт размер дерева рекурсивных вызовов при увеличении входных данных? Будут ли повторяющиеся вызовы в этом дереве и имеет ли смысл делать рекурсию с запоминанием?
Одно из важных достоинств рекурсивных алгоритмов заключается в том, что они просты и наглядны. Но рекурсия не всегда является эффективным (самым быстрым) решением. Рекурсия использует мало памяти, но работать может довольно долго, как в примере с числами Фибоначчи.
Задача 8 [ править ]
Есть несколько алгоритмов Евклида, основанных на различных рекуррентных соотношениях для НОД:
- GCD ( a , b ) = GCD ( b , a mod b ) <\displaystyle \operatorname
(a,b)=\operatorname (b,a\ \operatorname \ b)> ; - GCD ( a , b ) = GCD ( b , min ( | a mod b | , b − | a mod b | ) ; <\displaystyle \operatorname
(a,b)=\operatorname (b,\min(|a\ \operatorname \ b|,\;b-|a\ \operatorname \ b|);> - GCD ( a , b ) = < GCD ( a , b 2 k ) , a is odd, and b = b ′ ⋅ 2 k , 2 k ⋅ GCD ( a 2 k , b 2 k ) , a and b are even, and a = a ′ ⋅ 2 k , b = b ′ ⋅ 2 k , GCD ( b , a − b ) , a and b are odd, and a > b . <\displaystyle \operatorname
(a,b)=<\begin \operatorname \left(a,\;<\frac <2^ >>\right),&a<\mbox< is odd, and >>b=b’\cdot 2^ ,\\2^ \cdot \operatorname \left(<\frac <2^ >>,\;<\frac <2^ >>\right),&a<\mbox< and >>b<\mbox< are even, and >>a=a’\cdot 2^ ,\;b=b’\cdot 2^ ,\\\operatorname (b,\;a-b),&a<\mbox< and >>b<\mbox< are odd, and >>a>b.\end >>
Задачи для самостоятельного решения [ править ]
Существуют и другие задачи, решаемые рекурсией и динамическим программированием. Вот самые известные: обход конём шахматной доски, задача о восьми ферзях, триангуляция, поиск пути в лабиринте, вычисление арифметического выражения и многое другое.
Ниже предлагается несколько простых задач, для знакомства с идеей рекурсии.
Задача 9 [ править ]
- f ( a , n ) = a ⋅ f ( a , n − 1 )
- f ( a , n ) = < f 2 ( a , n / 2 ) , if n is even, a ⋅ f ( a , n − 1 ) , if n is odd. <\displaystyle f(a,n)=<\begin
f^<2>(a,n/2),&<\mbox< if >>n<\mbox< is even,>>\\a\cdot f(a,n-1),&<\mbox< if >>n<\mbox< is odd.>>\end >>
Задача 10 [ править ]
Задача 11 [ править ]
Число правильных скобочных структур длины 6 равно 5: ()()() , (())() , ()(()) , ((())) , (()()) .
Эта строчка содержит рекурсивное определение объекта s : «объект типа s может быть получен из объекта типа s с помощью окружения его открывающейся и закрывающейся круглой скобки, или с помощью приписывания двух объектов типа s друг к другу, либо это просто пустое слово». Вертикальная черта в нотации EBNF означает союз «или». С помощью одинарных кавычек выделяют символы или строки символов, пробелы играют роль разделителей.
Задача 12 [ править ]
Задача 13 [ править ]
Задача коммивояжёра [ править ]
Рекурсия с запоминанием работает не всегда. Рассмотрим пример задачи, для которой есть долго работающий рекурсивный алгоритм, который нельзя существенно ускорить с помощью запоминания вычисленных значений.
Коммивояжёр (франц. commis voyageur), разъездной представитель торговой фирмы, предлагающий покупателям товары по имеющимся у него образцам, каталогам и тому подобное.
Наш коммивояжёр ездит по городам с целью сбыта товаров разного рода. Он всегда начинает и заканчивает свой путь в одном и том же городе. На проживание во всех городах коммерсант тратит одинаковую сумму денег. Поэтому существенна только сумма на проезд из города в город. Есть список городов и стоимость проезда между некоторыми парами городов.
Задача коммивояжёра — побывать во всех городах (не менее одного раза) и при этом потратить как можно меньше денег на проезд и вернуться обратно.
Формулировка задачи
- внутри города проезд ничего не стоит;
- проезд между двумя городами напрямую стоит одинаково в оба конца;
- стоимость — целое число от 1 до 10000;
- городов не более 100.
Стоимости проезда между парами городов записаны в следующем формате:
Результат записывается в следующем формате:
Город задаётся названием без пробела. Длина названия города не более 30 символов. Программа должна реагировать на клавишу ESC. Если ESC была нажата, то в течении 10 секунд программа должна записать результат и закончить работу.
Снежинка Коха [ править ]
Снежинка Коха — это фрактальное множество точек на плоскости, которое похоже на снежинку.
Здесь приведена программа на языке PostScript. Этот код интерпрерируется программой GSView, которую можно взять на сайте http://www.ghostscript.com.
Снежинка рисуется рекурсивным образом. Сначала она выглядит как треугольник. Затем на сторонах этого треугольника рисуются треугольные выступы. Получается шеcтиконечная звезда. На сторонах этой звезды снова рисуются треугольные выступы (см. синюю фигуру). Процесс наращивания треугольных выступов можно продолжить до бесконечности и получить в пределе вполне корректно определённое множество точек на плоскости.
Программа «Снежинка Коха»
Заключение [ править ]
Рекурсивный метод решения задач является чуть ли не базовым методом решения алгоритмических задач. Рекурсия, дополненная идеями динамического программирования, жадными алгоритмами и идеей отсечения, превращается в тяжёлую артиллерию программистов. Но не следует забывать, что краткость записи рекурсивных функций не всегда означает высокую скорость их вычисления. И есть ряд задач, в которых рекурсия просто вредна (такова, например, задача вычисления кратчайшего пути в графе).
Рекурсия на PHP
В этой статье расскажу вам о рекурсии и о том как грамотно работать с ней на языке PHP.
PHP расшифровывается как PHP: Hypertext Preprocessor. Это смущает многих людей, потому что первое слово аббревиатуры это аббревиатура. Этот тип аббревиатуры называется рекурсивной аббревиатурой.
Перевод Google из официальной документации по PHP
Понятие рекурсии
Для начала разберёмся с понятием рекурсии. В общем смысле рекурсия это отображение чего-либо внутри самого себя. Рекурсивные алгоритмы используют рекурсивные функции, обладающие данным свойством.
Существует два варианта реализации рекурсивных функций: простой и сложный. В простом случае рекурсивная функция вызывает саму себя. В сложном — функция вызывает другую функцию, которая вызывает исходную функцию, с которой всё начиналось.
Рассмотрим пример из жизни. Если взять два больших зеркала и поставить их друг напротив друга, то можно увидеть бесконечный коридор из изображений зеркал. Каждое зеркало несёт в себе функцию отражения пространства расположенного перед ним. Поэтому здесь мы имеем пример сложной рекурсии (функция вызывает другую функцию, которая вызывает исходную).
Другим примером можно взять всем хорошо известное детское стихотворение:
У попа была собака, он её любил,
Она съела кусок мяса, поп её убил,
В землю закопал,
И надпись написал о том, что:
У попа была собака, он её любил,
Она съела кусок мяса, поп её убил,
В землю закопал,
И надпись написал о том, что:
…
Эта докучная сказка представляет собой пример простой рекурсии (здесь функция вызывает саму себя).
Глубина рекурсии
В связи с понятием рекурсии возникает понятие глубины рекурсии, то есть степени вложенности её отображений. Русская матрёшка, как правило, имеет 3-х и более вложенных в неё матрёшек. То есть глубина рекурсии в данном случае равна количеству вложенных матрёшек. Глубина рекурсии может быть равна бесконечности, в этом случае говорят о бесконечной рекурсии.
Два примера выше иллюстрируют именно этот случай. Правда в реальном мире, в отличие от мира математических абстракций, всегда есть какие-либо ограничения. Нельзя например бесконечно пересказывать одно и то же стихотворение, так как мы ограничены во времени.
Для нас важно, что ограничениям подвержен и сам компьютер. Память компьютера, производительность — не бесконечны. Поэтому применяя рекурсию, нужно понимать её опасности и подводные камни.
Опасности и подводные камни рекурсии
Рассмотрим простой пример.
Здесь функция foo() должна вызывать самое себя до бесконечности. В реальных условиях запуск программы приведёт к Segmentation fault, так как произойдёт переполнение стека вызова в силу ограничений на выделенную под него память. Понимая это следует избегать таких конструкций при разработке.
То же самое касается и примера со сложной рекурсией.
В PHP две функции не могут вызывать друг друга бесконечно, так как это неизбежно
приведёт к падению программы.
Теперь вернёмся к понятию глубины рекурсии. И рассмотрим следующий пример.
Здесь рекурсивный вызов должен завершиться по достижении степени вложенности n.
На практике при запуске этой программы для больших значений n произойдёт та же самая ошибка переполнения стека. Это так же следует учитывать при обработке больших списков и других структур данных, в которых глубина рекурсии зависит от их размера.
Рекурсивные алгоритмы на PHP
Теперь мы можем приступить к исследованию алгоритмов основанных на рекурсии.
Существует множество таких алгоритмов:
- Нахождение факториала
- Вычисление последовательности Фибоначчи
- Поиск максимального элемента в массиве
- Вычисление перестановок Ханойских башен
- Рассчёт вариантов размена суммы монетами
- Рекурсивный обход дерева
- и т.д.
Рассмотрим некоторые из них.
Вычисление последовательности Фибоначчи
Следует сделать лирическое отступление, которое касается истории открытия данной последовательности…
В 1202 году Леонардо Пизанский, известный как Фибоначчи, решая задачу о размножении кроликов, пришёл к открытию рекуррентного соотношения: 
Эта последовательность обладает одним замечательным свойством, а именно: 
Число Фи, представляет собой золотую пропорцию, которая часто встречается в природе, выражая собой закон гармонии и красоты…
Вернёмся к нашему алгоритму. Знание рекуррентного соотношения позволяет нам с лёгкостью реализовать этот алгоритм на PHP:
С точки зрения программирования нам интересно знать насколько быстро он выполняется по сравнению с его реализацией на основе итераций, например этой:
Если сделать тест выполнения с замером времени с помощью функции microtime , то обнаружится, что итеративная версия алгоритма выполняется гораздо быстрее, нежели его рекурсивный аналог. Почему это происходит?
Дело в том, что реализация рекурсивного алгоритма “в лоб” обладает одним существенным недостатком. А именно при такой реализации вызов функции для одного и того же аргумента производится многократно. Чтобы это увидеть, нужно внимательно рассмотреть само рекуррентное соотношение.
Повторные вызовы функции с одинаковыми аргументами занимает дополнительное время. Чтобы избежать этого, используют подход восходящего динамического программирования, который состоит в том, что задача разбивается на подзадачи и каждая подзадача решается только один раз. В нашем примере это можно реализовать в виде :
Таким образом вызов функций над одним и тем же аргументом производится лишь однажды, в случае повторных вызовов производится обращение к памяти к уже вычисленным значениям. Такой алгоритм выполняется гораздо быстрее, чем его простая реализация. Но всё же при этом он значительно уступает итеративной версии. Вы спросите в чём же дело?
Оказывается, что при рекурсивном вызове функций создаются копии её аргументов в стеке и следовательно дополнительные затраты на время выполнения операций копирования.
Чтобы обойти это, может быть использована парадигма Объектно-Ориентированного Программирования (ООП). К примеру мы можем создать массив внутри объекта, который будет иметь рекурсивный метод, внутри которого будет доступ к этому массиву так, что не потребуется передавать этот массив в качестве параметра для каждого вызова этого метода:
Время выполнения этой программы уже приближается к времени выполнения программы основанной на итерациях. Но всё же для достаточно больших значений n мы будем иметь отставание рекурсивной версии от его итеративного эквивалента, которое может быть значительным в практическом плане. Тогда же в чём смысл рекурсии спросите вы?
Основы программирования — второй семестр 08-09; Михалкович С.С.; III часть
Рекурсией называется определение объекта через такой же объект.
В данном примере рекурсивной частью определения является «<Список> ',' <Число>«.
Замечание 1. Рекурсивное определение, будучи конечным, определяет бесконечное множество объектов.
Заметим также, что <Список> можно определить и по-другому:
Определение (1) называют леворекурсивным, а (2) — праворекурсивным.
Замечание 2. В рекурсивном определении обязательно (. ) должна присутствовать нерекурсивная часть.
Рекурсивное определение может быть косвенным:
по одной из ветвей рекурсивного определения упоминается объект, в определении которого, в свою очередь, по одной из ветвей определяется исходный объект.
В данном примере имеется как прямое, так и косвенное рекурсивное определение.
В программировании под рекурсией понимается:
- вызов из подпрограммы самой себя (прямая рекурсия)
- вызов из подпрограммы другой подпрограммы, которая вызывает исходную (косвенная рекурсия)
При косвенной рекурсии обязательно использование опережающего объявления с помощью ключевого слова forward:
Простые примеры использования рекурсии
При вызове этой процедуры произойдет рекурсивное зацикливание, т.к. рекурсивный вызов производится безусловно.
Вывод. Чтобы рекурсивного зацикливания не произошло, рекурсивный вызов должен происходить не безусловно, а по какому-то условию, которое всякий раз меняется и при каком-то рекурсивном вызове становится ложным (так называемое условие продолжения рекурсии).
Исправим нашу процедуру в соответствии со сделанным выводом:
При вызове p(0) будет выведено:
Графически, рекурсивные вызовы можно изобразить так: 
Процесс последовательных рекурсивных вызовов подпрограммы из самой себя называется рекурсивным спуском.
Процесс возврата из рекурсивных вызовов называется рекурсивным возвратом.
В данном примере числа выводятся на рекурсивном спуске (т.е. в прямом порядке).
Однако, чтобы действия выполнялись в обратном порядке, их нужно вызывать на рекурсивном возврате.
Пример 2. Вывести
Максимальная глубина рекурсивных вызовов называется глубиной рекурсии.
Текущая глубина называется текущим уровнем рекурсии.
Замечание. Чем больше глубина рекурсии, тем больше накладные расходы по памяти.
Графические изображения рекурсивных вызовов
Одно графическое изображение у нас уже было. Вспомним его:
Рассмотрим более детально вызов p(0) процедуры
- Программный стек — это непрерывная область памяти, выделяемая программе, в частности, для размещения в ней вызываемых подпрограмм.
- При каждом вызове подпрограммы на стек кладется её запись активации (ЗА), а при возврате — снимается со стека.
Т.о. на стеке фактически хранятся все значения переменной i.
Замечание 1. Поскольку при каждом рекурсивном вызове на стек помещается ЗА, то при большой глубине рекурсии программный стек может переполниться , и программа завершится с ошибкой.
Это произойдет тем быстрее, чем больше суммарный объем формальных параметров и локальных переменных.
Поэтому следующий код — очень плохой.
Замечание 2. Накладные расходы на помещение на стек ЗА, снятие ЗА со стека, а также присваивание значений формальным параметрам на стеке достаточно велики.
Поэтому если имеется простое нерекурсивное решение (итерационное), то следует использовать именно его.
Замечание 3. Любую рекурсию можно заменить итерацией.
Примеры использования рекурсии
Пример 1. Найти n! = n(n - 1)(n - 2). 2*1
Очевидно, определить n! можем следующим образом:
Тогда решение имеет вид:
Однако, заметим, что возвращаемое значение не определено для n < 0.
Как минимум, можно заменить условие n = 0 на n <= 0, но, в таком случае, мы получим неверный результат, т.к. факториал вообще не определен для отрицательных чисел.
Очевидно, необходимо с помощью утверждения проверить корректность входного параметра (Assert(n >= 0)). Но его использование при каждом рекурсивном вызове накладно. Поэтому можно «обернуть» рекурсивную подпрограмму, например, так:
Глубина рекурсии этого алгоритма равна n.
Пример 2. Найти <math>a^n</math>. Дадим рекурсивное определение:
Глубина рекурсии равна:
- <math>\log_2 n</math> — в лучшем случае
- <math>2\log_2 n</math> — в худшем
Пример 3. Нахождение минимального элемента в массиве. Определить этот элемент можем как минимальный(один элемент, минимальный из массива без этого элемента), т.е. рекурсивное определение следующее:
<math>minElem(A, n) = \begin
\\ min(\; minElem(A, \; n — 1),\; A[n — 1]\;), & n > 1\end
Глубина рекурсии равна n - 1.
Ясно, что это не очень хороший результат.
Можно значительно уменьшить глубину, если искать минимальный среди примерно равных частей массива. Т.е. нужно поделить массив пополам, найти в каждой половине минимальные элементы и сравнить их. Поиск в половине осуществляется подобным же образом, и деление производится до тех пор, пока в подмассиве не останется один элемент.
Можно еще немного оптимизировать этот алгоритм — если в подмассиве два элемента, достаточно вернуть минимальный из них.
Теперь знания количества элементов недостаточно: необходимо знать, среди каких элементов массива вести поиск. Поэтому будем в качестве параметров передавать левую (l) и правую (r) границы подмассивов.
Дадим новое рекурсивное определение:
<math>minElem(A, l, r) = \begin
\\ min(A[l],\; A[r]), & r — l = 1 \\ min(\; minElem(A,\; l, \; (l + r) \; div\; 2), \; minElem( A, \; (l + r)\; div\; 2 + 1,\; r) \;), & l — r > 1\end
Глубина рекурсии такого алгоритма уже примерно равна <math>\log_2 n</math> (по количеству делений).
Пример 4. Вывод односвязного линейного списка на экран.
Вспомним, как выглядит список:
Решение:
Глубина рекурсии равна длина списка - 1
Рекурсия называется концевой, если рекурсивный вызов является последним в подпрограмме.
Концевая рекурсия наиболее легко превращается в итеративный алгоритм:
Доказательство завершимости рекурсии
Добавим к рекурсивной процедуре целый параметр n:
Если при каждом рекурсивном вызове параметр n уменьшается получим вызовы
И если рекурсия завершается при n <= 0, то это служит доказательством завершимости рекурсии.
Действительно, на каждом следующем уровне рекурсии n становится меньше.
Поскольку при n <= 0 рекурсивных вызовов нет, то число рекурсивных вызовов конечно.
Утверждать, что рекурсия завершима, можно не всегда.
Пример.
Формы рекурсивных подпрограмм
1. Действие выполняется на рекурсивном спуске
2. Действие выполняется на рекурсивном возврате
3. Действие выполняется и на рекурсивном спуске и на рекурсивном возврате
4. Каскадная рекурсия
Эта рекурсия называется каскадной, т.к. каждый вызов подпрограммы может порождать несколько рекурсивных вызовов (каскад).
5. Удаленная рекурсия:
Примером удаленной рекурсии служит функция Аккермана:
Примеры плохого и хорошего использования рекурсии
<xh4>Пример плохого использования рекурсии — числа Фибоначчи</xh4> Числа Фибоначчи задаются следующим рекуррентным соотношением:
<math>F_1 = 1,\quad F_2 = 1,\quad F_
Мы уже вычисляли их с помощью циклов. Возможно рекурсивное (плохое!) решение:
Вот что произойдет при вызове Fib(7):
дерево рекурсивных вызовов
Как видим, одни и те же числа вычисляются по несколько раз:
- Fib(7): 1
- Fib(6): 1
- Fib(5): 2
- Fib(4): 3
- Fib(3): 5
- Fib(2): 8
Алгоритм можно улучшить, использовав массив, первоначально заполненный нулями.
При первом вычислении fib(n) будем заполнять соответствующий элемент, а при всех последующих — просто обращаться к его значению. Подобная методика называется мемоизацией, т.е. запоминанием промежуточных результатов для исключения их повторного вычисления.
Очевидно, данный способ крайне неэффективен по сравнению с итерационным алгоритмом как по памяти, так и по времени работы. В частности, глубина рекурсии при вычислении n-того числа Фибоначчи составляет n-1.
Рекурсивный способ вычисления чисел Фибоначчи, построенный по итерационному алгоритму
Напомним итерационный алгоритм поиска n-того числа Фибоначчи:
Построим по нему рекурсивный алгоритм, передавая в каждую рекурсивную подпрограмму переменные a,b,c, меняющиеся на каждой итерации цикла. Фактически при каждом рекурсивном вызове мы будем совершать подстановку:
Рекурсивный алгоритм, реализованный по этой подстановке, будет иметь вид:
Рекурсия в данном примере — концевая. Как уже отмечалась, она легко заменяется итерацией, при этом как раз получается предыдущее итерационное решение. Хорошие оптимизирующие компиляторы делают это автоматически.
Пример хорошего использования рекурсии — ханойские башни
Задача состоит в следующем:
Даны три стержня. На первом лежат n дисков разного радиуса при условии, что ни один диск бОльшего радиуса не лежит на диске мЕньшего радиуса.
Hеобходимо перенести диски с первого стержня на третий, пользуясь вторым, при условии:
- за один ход можно переносить только один диск
- меньший диск должен лежать на большем
Идея алгоритма такая:
Т.о. имеем простое рекурсивное решение:
Быстрая сортировка
<xh4>Алгоритм</xh4> Алгоритм быстрой сортировки (разновидность алгоритма «разделяй и влавствуй») состоит из двух этапов:
1. Выбор некоторого элемента массива x и разделение массива на две части так, что в первой оказываются все элементы <= x, а в о второй — >= x
2. Рекурсивное применение нашего алгоритма к полученным частям
Очевидно, алгоритм будет работать тем быстрее, чем на более равные части мы будем делить массив (в идеале — каждый раз пополам).
Поэтому мы должны стремиться выбрать элемент x так, чтобы примерно половина элементов массива была <= его, и, соответственно, вторая половина — >=. С другой стороны, выбор x не должен занимать много времени и, по крайней мере, не зависеть от n — размера массива).
Мы будем использовать простейший способ выбора x — в качестве него брать первый элемент.
На следующей анимации представлен пример применения алгоритма быстрой сортировки к массиву
Рассмотрим этап 1 подробнее:
— Для разделения массива на указанные части заведем 2 индекса i и j.
— В начале i будет указывать на первый элемент и двигаться вправо, а j — на последний и двигаться влево.
Шаг 1.
Будем продвигать i вперед до тех пор, пока A[i] не станет >= x.
Далее будем продвигать j назад до тех пор, пока A[j] не станет <= x.
Пришли к элементам A[i] и A[j], которые «стоят не на своих местах» (вспомним, что мы хотим раскидать все меньшие или равные x элементы влево, а большие или равные — вправо)
Шаг 2.
Поменяем их местами и продвинем i вперед на один элемент, а j — назад, также на один элемент.
Будем повторять указанные действия до тех пор, пока i не станет >= j.
В результате получим массив A, разделенный на 2 части:
- слева все элементы <= x
- справа — >= x
Код программы
<xh4>Асимптотическая оценка сложности</xh4> Будем исходить из того, что массив всякий раз делится на 2 одинаковые части. Это самый лучший вариант.
Глубина рекурсии в этом случае = log2n.
Очевидно, что в алгоритме Partition мы просматриваем все элементы «своей части» ровно один раз. Т.е. на каждом уровне рекурсии будут по одному разу просмотрены все элементы массива.
Это означает, что асимптотическая сложность Partition на каждом уровне рекурсии = Θ(n).
Т.о., при условии деления примерно пополам, асимптотическая сложность всего алгоритма = Θ(n log n).
Теоретически доказано, что в среднем, если делим не точно пополам, асимптотическая сложность сохраняет формулу Θ(n log n).
Вопрос: какова сложность в худшем случае? Худший — когда в качестве x выбираем минимальный (или максимальный) элемент. Это происходит (в нашей ситуации, т.к. мы выбираем первый элемент), если массив уже отсортирован.
В этом случае в результате разбиения на части большая часть будет уменьшаться на 1, и глубина рекурсии в процедуре Sort будет равна <math>n — 1</math>.
Поэтому в худшем случае асимптотическая сложность = <math>\Theta(n^2)</math>.
Утверждение. Для произвольных данных не существует алгоритма с асимптотической сложностью лучше, чем Θ(n log n) в среднем.
Генерация всех перестановок
Основная идея алгоритма генерации всех перестановок заключается в следующем. В массиве длины n, содержащем перестановку, будем менять последний элемент с каждым, после чего будем рекурсивно будем делать то же самое для массива длины n-1 и затем возвращать переставленный элемент на старое место. Если достигнута длина массива n=1, то переставлять ничего не нужно, а следует выдавать содержимое всего массива-перестановки на экран. Такой алгоритм позволит сгенерировать все перестановки, что следует из словесного рекурсивного определения: на последнем месте побывает каждый элемент, содержащийся в рассматриваемом массиве, после чего к оставшейся части массива рекурсивно будет применен тот же алгоритм.
Нетрудно видеть, что глубина рекурсии составляет n-1, а количество вызовов процедуры Perm составляет n!.
Генерация всех подмножеств
Генерация всех подмножеств представляет собой алгоритм перебора. В алгоритмах перебора перебираются все варианты и для подходящих вариантов выполняется определенное действие. В данном случае просто выводятся все подмножества.