Основы программирования — второй семестр 08-09; Михалкович С.С.; III часть — различия между версиями
Juliet (обсуждение | вклад) |
Admin (обсуждение | вклад) (→Задача об обходе конем шахматной доски) |
||
(не показано 80 промежуточных версий 9 участников) | |||
Строка 1: | Строка 1: | ||
− | [[Категория: | + | [[Категория:Основы программирования]] |
− | |||
== Рекурсия == | == Рекурсия == | ||
− | === | + | === Основные определения === |
'''Рекурсией''' называется определение объекта через такой же объект. | '''Рекурсией''' называется определение объекта через такой же объект. | ||
Строка 16: | Строка 15: | ||
|<Число> ',' <Список> | |<Число> ',' <Список> | ||
− | Определение (1) называют '''''леворекурсивным''''', | + | Определение (1) называют '''''леворекурсивным''''', а (2) — '''''праворекурсивным'''''. |
'''Замечание 2.''' В рекурсивном определении ''обязательно (!!!)'' должна присутствовать '''''нерекурсивная''''' часть. | '''Замечание 2.''' В рекурсивном определении ''обязательно (!!!)'' должна присутствовать '''''нерекурсивная''''' часть. | ||
Строка 23: | Строка 22: | ||
:по одной из ветвей рекурсивного определения упоминается объект, в определении которого, в свою очередь, по одной из ветвей определяется исходный объект. | :по одной из ветвей рекурсивного определения упоминается объект, в определении которого, в свою очередь, по одной из ветвей определяется исходный объект. | ||
+ | '''Пример'''. | ||
+ | <оператор> ::= <присваивание> | <составной оператор> | ||
+ | <присваивание> ::= <переменная> := <выражение> | ||
+ | <составной оператор> ::= begin <список операторов> end | ||
+ | <список операторов> ::= <пусто> | <оператор> ; <список операторов> | ||
+ | |||
+ | В данном примере имеется как прямое, так и косвенное рекурсивное определение. | ||
+ | |||
В программировании под '''рекурсией''' понимается: | В программировании под '''рекурсией''' понимается: | ||
Строка 29: | Строка 36: | ||
При косвенной рекурсии ''обязательно'' использование '''''опережающего объявления''''' с помощью ключевого слова <tt>'''forward'''</tt>: | При косвенной рекурсии ''обязательно'' использование '''''опережающего объявления''''' с помощью ключевого слова <tt>'''forward'''</tt>: | ||
− | <source lang="Pascal">procedure q; | + | <source lang="Pascal">procedure q; forward; // опережающее определение |
procedure p; | procedure p; | ||
Строка 46: | Строка 53: | ||
=== Простые примеры использования рекурсии === | === Простые примеры использования рекурсии === | ||
− | + | <u>''Пример 1''</u>. | |
− | + | <source lang="Pascal">procedure p(i: integer); | |
+ | begin | ||
+ | write(i, ' '); | ||
+ | p(i + 1); | ||
+ | end;</source> | ||
+ | При вызове этой процедуры произойдет '''''рекурсивное зацикливание''''', т.к. рекурсивный вызов производится безусловно. | ||
+ | |||
+ | '''Вывод.''' Чтобы '''''рекурсивного зацикливания''''' не произошло, рекурсивный вызов должен происходить не безусловно, а по какому-то условию, которое всякий раз меняется и при каком-то рекурсивном вызове становится ложным (так называемое '''условие продолжения рекурсии'''). | ||
+ | |||
+ | Исправим нашу процедуру в соответствии со сделанным выводом: | ||
+ | <source lang="Pascal">procedure p(i: integer); | ||
+ | begin | ||
+ | write(i, ' '); | ||
+ | if i < 5 then | ||
+ | p(i + 1); | ||
+ | end;</source> | ||
+ | При вызове <tt>p(0)</tt> будет выведено: | ||
+ | 0 1 2 3 4 5 | ||
+ | Графически, рекурсивные вызовы можно изобразить так:<br /> | ||
+ | [[Изображение:Recur1.png]]<br /> | ||
+ | |||
+ | Процесс последовательных рекурсивных вызовов подпрограммы из самой себя называется '''рекурсивным спуском'''. | ||
+ | <br />Процесс возврата из рекурсивных вызовов называется '''рекурсивным возвратом'''. | ||
+ | |||
+ | В данном примере числа выводятся на рекурсивном спуске (т.е. в ''прямом'' порядке). | ||
+ | <br />Однако, чтобы действия выполнялись в ''обратном'' порядке, их нужно вызывать на рекурсивном возврате. | ||
+ | |||
+ | <u>''Пример 2''</u>. Вывести | ||
+ | 0 1 2 3 4 5 4 3 2 1 0 | ||
+ | Решение: | ||
+ | <source lang="Pascal">procedure p(i: integer); | ||
+ | begin | ||
+ | write(i, ' '); | ||
+ | if i < 5 then then | ||
+ | begin | ||
+ | p(i + 1); | ||
+ | write(i, ' '); | ||
+ | end; | ||
+ | end;</source> | ||
+ | Максимальная глубина рекурсивных вызовов называется '''глубиной рекурсии'''. | ||
+ | <br />Текущая глубина называется '''текущим уровнем рекурсии'''. | ||
+ | |||
+ | '''Замечание'''. Чем больше глубина рекурсии, тем больше накладные расходы по памяти. | ||
+ | |||
+ | === Графические изображения рекурсивных вызовов === | ||
+ | Одно графическое изображение у нас уже было. Вспомним его: | ||
+ | <source lang="Pascal">procedure p(i: integer); | ||
+ | begin | ||
+ | write(i, ' '); | ||
+ | if i < 5 then | ||
+ | p(i + 1); | ||
+ | end;</source> | ||
+ | <br />[[Изображение:Recur1.png]]<br /> | ||
+ | |||
+ | Рассмотрим более детально вызов <tt>p(0)</tt> процедуры | ||
+ | <source lang="Pascal">procedure p(i: integer); | ||
+ | begin | ||
+ | write(i, ' '); | ||
+ | if i < 2 then | ||
+ | p(i + 1); | ||
+ | end;</source> | ||
+ | Вспомним, что: | ||
+ | *'''Программный стек''' — это непрерывная область памяти, выделяемая программе, в частности, для размещения в ней вызываемых подпрограмм. | ||
+ | *При каждом вызове подпрограммы на стек кладется её запись активации (ЗА), а при возврате — снимается со стека. | ||
<br>[[Изображение:Графическое_изображение_рекурсии.gif]]<br> | <br>[[Изображение:Графическое_изображение_рекурсии.gif]]<br> | ||
− | + | Т.о. на стеке фактически хранятся все значения переменной i. | |
+ | |||
+ | '''Замечание 1.''' Поскольку при каждом рекурсивном вызове на стек помещается ЗА, то при большой глубине рекурсии программный стек может '''<span style="color: Red">переполниться</span>''', и программа завершится с ошибкой. | ||
+ | <br />Это произойдет тем быстрее, чем больше суммарный объем формальных параметров и локальных переменных. | ||
− | = | + | Поэтому следующий код — '''''очень плохой!!!''''' |
+ | <source lang="Pascal">procedure p(i: integer); | ||
+ | var a : array[1..1000] of real; | ||
+ | begin | ||
+ | ... | ||
+ | p(i + 1); | ||
+ | ... | ||
+ | end;</source> | ||
+ | |||
+ | '''Замечание 2.''' Накладные расходы на помещение на стек ЗА, снятие ЗА со стека, а также присваивание значений формальным параметрам на стеке достаточно велики. | ||
+ | <br />Поэтому если имеется ''простое нерекурсивное решение'' (итерационное), то следует использовать именно его. | ||
+ | |||
+ | '''Замечание 3.''' Любую рекурсию можно заменить итерацией. | ||
=== Примеры использования рекурсии === | === Примеры использования рекурсии === | ||
− | + | ''<u>Пример 1.</u>'' Найти <tt>n! = n(n - 1)(n - 2)...2*1</tt> | |
− | + | <br />Очевидно, определить <tt>n!</tt> можем следующим образом: | |
+ | :<math>f(n) = \begin{cases} n (n - 1), & n > 0 \\ 1, & n = 0 \end{cases}</math> | ||
+ | Тогда решение имеет вид: | ||
+ | <source lang="Pascal">function nfact(n: integer): integer; | ||
+ | begin | ||
+ | if n = 0 then | ||
+ | Result := 1 | ||
+ | else | ||
+ | Result := n * nfact(n - 1); | ||
+ | end;</source> | ||
+ | Однако, заметим, что возвращаемое значение не определено для <tt>n < 0</tt>. | ||
+ | <br />Как минимум, можно заменить условие <tt>n = 0</tt> на <tt>n <= 0</tt>, но, в таком случае, мы получим неверный результат, т.к. факториал вообще не определен для отрицательных чисел. | ||
+ | <br />Очевидно, необходимо с помощью утверждения проверить корректность входного параметра (<tt>Assert(n >= 0))</tt>. Но его использование при каждом рекурсивном вызове накладно. Поэтому можно "обернуть" рекурсивную подпрограмму, например, так: | ||
+ | <source lang="Pascal">function nfact(n: integer): integer; | ||
+ | function nfactRecur(n: integer): integer; | ||
+ | begin | ||
+ | if n = 0 then | ||
+ | Result := 1 | ||
+ | else | ||
+ | Result := n * nfact(n - 1); | ||
+ | end; | ||
+ | begin | ||
+ | Assert(n >= 0); | ||
+ | Result := nfactRecur(n); | ||
+ | end;</source> | ||
+ | ''Глубина рекурсии'' этого алгоритма равна ''n''. | ||
+ | |||
+ | |||
+ | ''<u>Пример 2.</u>'' Найти <math>a^n</math>. | ||
+ | Дадим рекурсивное определение: | ||
+ | :<math>f(n) = \begin{cases} (a^{\frac{n}{2}})^2, & \mbox{if }n\mbox{ is even}, n > 0 | ||
+ | \\ a a^{n-1}, & \mbox{if }n\mbox{ is odd}, n > 0 | ||
+ | \\ 1, & n = 0 | ||
+ | \\ \frac{1}{a^n}, & n < 0\end{cases}</math> | ||
+ | <source lang="Pascal">function power(a: real; n: integer): real; | ||
+ | begin | ||
+ | if n = 0 then | ||
+ | Result := 1 | ||
+ | else if n < 0 then | ||
+ | Result := 1 / power(a, -n) | ||
+ | else // n > 0 | ||
+ | if n mod 2 = 0 then | ||
+ | Result := sqr(power(a, n div 2)) | ||
+ | else | ||
+ | Result := a * power(a, n - 1); | ||
+ | end;</source> | ||
+ | ''Глубина рекурсии'' равна: | ||
+ | *<math>\log_2 n</math> — в лучшем случае | ||
+ | *<math>2\log_2 n</math> — в худшем | ||
− | |||
− | |||
− | |||
− | |||
− | Пример | + | ''<u>Пример 3.</u>'' Нахождение минимального элемента в массиве. |
+ | Определить этот элемент можем как ''минимальный(один элемент, минимальный из массива без этого элемента)'', т.е. рекурсивное определение следующее: | ||
+ | :<math>minElem(A, n) = \begin{cases} A[n-1], & n = 1 | ||
+ | \\ min(\; minElem(A, \; n - 1),\; A[n - 1]\;), & n > 1\end{cases}</math> | ||
+ | В соответствии с этим имеем решение: | ||
+ | <source lang="Pascal">function MinElem(A: array of integer; n: integer): integer; | ||
+ | begin | ||
+ | if n = 1 then | ||
+ | Result := A[0] | ||
+ | else | ||
+ | Result := min(MinElem(A, n-1), A[n-1])); | ||
+ | end;</source> | ||
+ | ''Глубина рекурсии'' равна <tt>n - 1</tt>. | ||
+ | |||
+ | Ясно, что это не очень хороший результат. | ||
+ | <br />Можно значительно уменьшить глубину, если искать минимальный среди примерно равных частей массива. | ||
+ | Т.е. нужно поделить массив пополам, найти в каждой половине минимальные элементы и сравнить их. Поиск в половине осуществляется подобным же образом, и деление производится до тех пор, пока в подмассиве не останется один элемент. | ||
+ | <br />Можно еще немного оптимизировать этот алгоритм — если в подмассиве два элемента, достаточно вернуть минимальный из них. | ||
+ | <br />Теперь знания количества элементов недостаточно: необходимо знать, среди ''каких'' элементов массива вести поиск. Поэтому будем в качестве параметров передавать левую (<tt>l</tt>) и правую (<tt>r</tt>) границы подмассивов. | ||
+ | <br />Дадим новое рекурсивное определение: | ||
+ | :<math>minElem(A, l, r) = \begin{cases} A[l], & l = r | ||
+ | \\ 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{cases}</math> | ||
+ | Решение: | ||
+ | <source lang="Pascal">function MinElem(a: array of integer; l, r: integer): integer; | ||
+ | begin | ||
+ | if l = r then // если всего один элемент | ||
+ | Result := a[l] | ||
+ | else if r - l = 1 then // если ищем минимум из двух элементов | ||
+ | Result := min(a[l], a[r]) | ||
+ | else | ||
+ | begin | ||
+ | var mid := (l + r) div 2; | ||
+ | Result := min(MinElem(a, l, mid), MinElem(a, mid+1, r)); | ||
+ | end; | ||
+ | end;</source> | ||
+ | ''Глубина рекурсии'' такого алгоритма уже примерно равна <math>\log_2 n</math> (по количеству делений). | ||
+ | |||
+ | |||
+ | ''<u>Пример 4.</u>'' Вывод односвязного линейного списка на экран. | ||
+ | <br>Вспомним, как выглядит список: | ||
+ | <br>[[Изображение:Линейный_односвязный_список.png]] <br /> | ||
+ | Решение: | ||
+ | <source lang="Pascal">procedure Print<T>(h: Node<T>); | ||
+ | begin | ||
+ | if h = nil then | ||
+ | exit; | ||
+ | write(h.data, ' '); | ||
+ | Print(h.next); | ||
+ | end;</source> | ||
+ | ''Глубина рекурсии'' равна <tt>длина списка - 1</tt> | ||
+ | |||
+ | Рекурсия называется '''концевой''', если рекурсивный вызов является последним в подпрограмме. | ||
+ | |||
+ | Концевая рекурсия наиболее легко превращается в ''итеративный'' алгоритм: | ||
+ | <source lang="Pascal">while h <> nil do | ||
+ | begin | ||
+ | write(h.data, ' '); | ||
+ | h := h.next; | ||
+ | end;</source> | ||
=== Доказательство завершимости рекурсии === | === Доказательство завершимости рекурсии === | ||
+ | Добавим к рекурсивной процедуре целый параметр <tt>n</tt>: | ||
+ | p(n, ...); | ||
+ | Если при каждом рекурсивном вызове параметр n уменьшается получим вызовы | ||
+ | p(n) | ||
+ | p(n - 1) | ||
+ | p(n - 2) | ||
+ | p(n - 3) | ||
+ | И если рекурсия завершается при <tt>n <= 0</tt>, то это служит доказательством завершимости рекурсии. | ||
+ | |||
+ | Действительно, на каждом следующем уровне рекурсии <tt>n</tt> становится меньше. | ||
+ | <br />Поскольку при <tt>n <= 0</tt> рекурсивных вызовов нет, то число рекурсивных вызовов конечно. | ||
+ | |||
+ | Утверждать, что рекурсия завершима, можно не всегда. | ||
+ | <br />''<u>Пример.</u>'' | ||
+ | <source lang="Pascal">procedure p(n); | ||
+ | begin | ||
+ | if n <= 0 then | ||
+ | exit | ||
+ | else | ||
+ | p(Random(2 * n) - n + 1); | ||
+ | end;</source> | ||
=== Формы рекурсивных подпрограмм === | === Формы рекурсивных подпрограмм === | ||
− | + | 1. Действие выполняется на '''''рекурсивном спуске''''' | |
− | + | p(n) | |
− | + | S(n) | |
− | + | '''if''' B(n) '''then''' | |
− | + | p(n - 1) | |
− | function f(i: integer): integer; | + | 2. Действие выполняется на '''''рекурсивном возврате''''' |
− | begin | + | p(n) |
− | if B1(n) then Result:=... | + | '''if''' B(n) '''then''' |
− | else Result:=f(f(i-1)); | + | p(n - 1) |
− | end; | + | S(n) |
+ | 3. Действие выполняется и на '''''рекурсивном спуске''''' и на '''''рекурсивном возврате''''' | ||
+ | p(n) | ||
+ | S<sub>1</sub>(n) | ||
+ | '''if''' B(n) '''then''' | ||
+ | p(n - 1) | ||
+ | S<sub>2</sub>(n) | ||
+ | 4. '''''Каскадная рекурсия''''' | ||
+ | p(n) | ||
+ | S(n) | ||
+ | '''if''' B<sub>1</sub>(n) '''then''' | ||
+ | p(n - 1) | ||
+ | '''if''' B<sub>2</sub>(n) '''then''' | ||
+ | p(n - 1) | ||
+ | Эта рекурсия называется '''каскадной''', т.к. каждый вызов подпрограммы может порождать несколько рекурсивных вызовов ('''каскад'''). | ||
+ | |||
+ | 5. '''''Удаленная рекурсия''''': | ||
+ | '''function''' f(i: integer): integer; | ||
+ | '''begin''' | ||
+ | '''if''' B1(n) '''then''' | ||
+ | Result := ... | ||
+ | '''else''' | ||
+ | Result := f(f(i-1)); | ||
+ | '''end'''; | ||
+ | |||
+ | Примером удаленной рекурсии служит [http://ru.wikipedia.org/wiki/Функция_Аккермана '''функция Аккермана''']: | ||
+ | : <math>A(m,\;n)=\begin{cases}n+1,&m=0; | ||
+ | \\A(m-1,\;1),&m>0,\; n = 0; | ||
+ | \\A(m-1,\;A(m,\;n-1)),& m > 0,\; n > 0.\end{cases}</math> | ||
− | |||
− | |||
− | |||
− | |||
=== Примеры плохого и хорошего использования рекурсии === | === Примеры плохого и хорошего использования рекурсии === | ||
− | Пример плохого использования рекурсии - числа Фибоначчи | + | <xh4>Пример плохого использования рекурсии - числа Фибоначчи</xh4> |
− | + | Числа Фибоначчи задаются следующим рекуррентным соотношением: | |
+ | : <math>F_1 = 1,\quad F_2 = 1,\quad F_{n+1} = F_n + F_{n-1} \quad n\in\mathbb{N}.</math> | ||
+ | Мы уже вычисляли их с помощью циклов. Возможно рекурсивное ('''плохое!''') решение: | ||
+ | <source lang="Pascal">function Fib(n: integer): integer; | ||
+ | begin | ||
+ | if (n = 1) or (n = 2) then | ||
+ | Result := 1 | ||
+ | else | ||
+ | Result := Fib(n - 1) + Fib(n - 2); | ||
+ | end;</source> | ||
+ | Вот что произойдет при вызове <tt>Fib(7)</tt>: | ||
+ | <br />[[Изображение:Fib1.png]]<br /> | ||
+ | '''дерево рекурсивных вызовов''' | ||
+ | |||
+ | Как видим, одни и те же числа вычисляются по несколько раз: | ||
+ | *<tt>Fib(7): 1</tt> | ||
+ | *<tt>Fib(6): 1</tt> | ||
+ | *<tt>Fib(5): 2</tt> | ||
+ | *<tt>Fib(4): 3</tt> | ||
+ | *<tt>Fib(3): 5</tt> | ||
+ | *<tt>Fib(2): 8</tt> | ||
+ | |||
+ | Алгоритм можно улучшить, использовав массив, первоначально заполненный нулями. | ||
+ | <br />При первом вычислении <tt>fib(n)</tt> будем заполнять соответствующий элемент, а при всех последующих — просто обращаться к его значению. Подобная методика называется [http://ru.wikipedia.org/wiki/Мемоизация мемоизацией], т.е. запоминанием промежуточных результатов для исключения их повторного вычисления. | ||
+ | |||
+ | <source lang="Pascal">var F: array[1..1000] of integer; | ||
+ | |||
+ | function Fib(n: integer): integer; | ||
+ | begin | ||
+ | if F[n] <> 0 then | ||
+ | Result := F[n] | ||
+ | else if (n = 1) or (n = 2) then | ||
+ | begin | ||
+ | Result := 1; | ||
+ | F[n] := 1; | ||
+ | end | ||
+ | else | ||
+ | begin | ||
+ | Result := Fib(n - 1) + Fib(n - 2); | ||
+ | F[n] := Result; | ||
+ | end; | ||
+ | end;</source> | ||
+ | |||
+ | Очевидно, данный способ крайне неэффективен по сравнению с итерационным алгоритмом как по памяти, так и по времени работы. В частности, глубина рекурсии при вычислении n-того числа Фибоначчи составляет n-1. | ||
+ | |||
+ | ====Рекурсивный способ вычисления чисел Фибоначчи, построенный по итерационному алгоритму==== | ||
+ | Напомним итерационный алгоритм поиска n-того числа Фибоначчи: | ||
+ | <source lang="Delphi"> | ||
+ | a := 1; | ||
+ | b := 1; | ||
+ | for var i := 3 to n do | ||
+ | begin | ||
+ | c := a + b; | ||
+ | a := b; | ||
+ | b := c; | ||
+ | end; | ||
+ | Result := c; | ||
+ | </source> | ||
+ | |||
+ | Построим по нему рекурсивный алгоритм, передавая в каждую рекурсивную подпрограмму переменные a,b,c, меняющиеся на каждой итерации цикла. Фактически при каждом рекурсивном вызове мы будем совершать подстановку: | ||
+ | (a,b)->(b,a+b) | ||
+ | |||
+ | Рекурсивный алгоритм, реализованный по этой подстановке, будет иметь вид: | ||
+ | <source lang="Delphi">function fib (a,b,n: integer): integer; | ||
+ | begin | ||
+ | if n = 1 then | ||
+ | Result := a | ||
+ | else Result := fib(b,a+b,n-1) | ||
+ | end; | ||
+ | |||
+ | begin | ||
+ | for var i:=1 to 10 do | ||
+ | Print(fib(1,1,i)); | ||
+ | end.</source> | ||
+ | |||
+ | Рекурсия в данном примере - концевая. Как уже отмечалась, она легко заменяется итерацией, при этом как раз получается предыдущее итерационное решение. Хорошие оптимизирующие компиляторы делают это автоматически. | ||
+ | |||
+ | ====Пример хорошего использования рекурсии - ханойские башни==== | ||
+ | Задача состоит в следующем: <br /> | ||
+ | Даны три стержня. На первом лежат n дисков разного радиуса при условии, что ни один диск бОльшего радиуса не лежит на диске мЕньшего радиуса. <br /> | ||
+ | Hеобходимо перенести диски с первого стержня на третий, пользуясь вторым, при условии: | ||
+ | * за один ход можно переносить только один диск | ||
+ | * меньший диск должен лежать на большем'' | ||
+ | [[Изображение:Tower_of_Hanoi.jpeg|350px|Модель Ханойской башни с восемью дисками]] | ||
− | + | Идея алгоритма такая: | |
+ | перекладываем n-1 диск с исходного стержня на вспомогательный | ||
+ | оставшийся диск перекладываем на требуемый стержень | ||
+ | лежащие на вспомогательном стержне диски перекладываем на требуемый диск | ||
− | == | + | Т.о. имеем простое рекурсивное решение: |
+ | <source lang="Pascal">procedure MovePiramid(n: integer; f, t, w : integer); | ||
+ | begin | ||
+ | if n = 0 then | ||
+ | exit; | ||
+ | MovePiramid(n - 1, f, w, t); | ||
+ | writelnFormat('Переложить диск с {0} на {1}', f, t); | ||
+ | MovePiramid(n - 1, w, t, f); | ||
+ | end;</source> | ||
===Быстрая сортировка=== | ===Быстрая сортировка=== | ||
+ | <xh4>Алгоритм</xh4> | ||
+ | Алгоритм '''быстрой сортировки''' (разновидность алгоритма «'''разделяй и влавствуй'''») состоит из двух этапов: <br /> | ||
+ | 1. Выбор некоторого элемента массива x и разделение массива на две части так, что в первой оказываются все элементы <= x, а в о второй — >= x <br /> | ||
+ | 2. Рекурсивное применение нашего алгоритма к полученным частям | ||
+ | |||
+ | Очевидно, алгоритм будет работать тем быстрее, чем на более равные части мы будем делить массив (в идеале — каждый раз пополам). <br /> | ||
+ | Поэтому мы должны стремиться выбрать элемент x так, чтобы примерно половина элементов массива была <= его, и, соответственно, вторая половина — >=. С другой стороны, выбор x не должен занимать много времени и, по крайней мере, не зависеть от n — размера массива). | ||
+ | |||
+ | Мы будем использовать простейший способ выбора x — в качестве него брать первый элемент. | ||
+ | |||
+ | На следующей анимации представлен пример применения алгоритма быстрой сортировки к массиву | ||
+ | 4 1 7 3 2 9 5 8 6 | ||
− | + | [[Изображение:Quick_sort.gif|400px]]<br /> | |
+ | Рассмотрим ''этап 1'' подробнее: <br /> | ||
+ | - Для разделения массива на указанные части заведем 2 индекса <tt>i</tt> и <tt>j</tt>. <br /> | ||
+ | - В начале <tt>i</tt> будет указывать на первый элемент и двигаться вправо, а <tt>j</tt> — на последний и двигаться влево. | ||
+ | |||
+ | <u>Шаг 1.</u> <br /> | ||
+ | Будем продвигать <tt>i</tt> вперед до тех пор, пока <tt>'''A[i]'''</tt> не станет <tt>'''>= x'''</tt>. <br /> | ||
+ | Далее будем продвигать <tt>j</tt> назад до тех пор, пока <tt>'''A[j]'''</tt> не станет <tt>'''<= x'''</tt>. <br /> | ||
+ | Пришли к элементам <tt>A[i]</tt> и <tt>A[j]</tt>, которые "стоят не на своих местах" (вспомним, что мы хотим раскидать все меньшие или равные <tt>x</tt> элементы влево, а большие или равные — вправо) <br /> | ||
+ | <u>Шаг 2.</u> <br /> | ||
+ | Поменяем их местами и продвинем <tt>i</tt> вперед на один элемент, а <tt>j</tt> — назад, также на один элемент. | ||
+ | |||
+ | Будем повторять указанные действия до тех пор, пока <tt>'''i'''</tt> не станет <tt>'''>= j'''</tt>. <br /> | ||
+ | В результате получим массив <tt>A</tt>, разделенный на 2 части: | ||
+ | * слева все элементы <tt><= x</tt> | ||
+ | * справа — <tt>>= x</tt> | ||
+ | |||
+ | ====Код программы ==== | ||
<source lang="Pascal"> | <source lang="Pascal"> | ||
− | + | // Быстрая сортировка Ч. Хоара | |
− | + | /// Разделение a[l]..a[r] на части a[l]..a[q] <= a[q+1]..a[r] | |
− | + | function Partition(a: array of integer; l,r: integer): integer; | |
− | + | begin | |
− | + | var i := l - 1; | |
− | + | var j := r + 1; | |
− | + | var x := a[l]; | |
− | + | while True do | |
− | + | begin | |
− | + | repeat | |
− | + | Inc(i); | |
− | + | until a[i]>=x; | |
− | + | repeat | |
− | + | Dec(j); | |
− | + | until a[j]<=x; | |
− | + | if i<j then | |
− | + | Swap(a[i],a[j]) | |
− | + | else | |
− | + | begin | |
− | + | Result := j; | |
− | + | exit; | |
− | + | end; | |
− | + | end; | |
− | + | end; | |
+ | |||
+ | /// Сортировка частей | ||
+ | procedure QuickSort(a: array of integer; l,r: integer); | ||
+ | begin | ||
+ | if l>=r then exit; | ||
+ | var j := Partition(a,l,r); | ||
+ | QuickSort(a,l,j); | ||
+ | QuickSort(a,j+1,r); | ||
+ | end; | ||
− | + | const n = 20; | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
+ | begin | ||
+ | var a := ArrRandom(); | ||
+ | writeln('До сортировки: '); | ||
+ | Writeln(a); | ||
+ | QuickSort(a,0,a.Length-1); | ||
+ | writeln('После сортировки: '); | ||
+ | Writeln(a); | ||
+ | end. | ||
+ | </source> | ||
+ | |||
+ | <xh4>Асимптотическая оценка сложности</xh4> | ||
+ | Будем исходить из того, что массив всякий раз делится на 2 одинаковые части. Это самый лучший вариант. <br /> | ||
+ | ''Глубина рекурсии'' в этом случае = <tt>log<sub>2</sub>n</tt>. | ||
+ | |||
+ | Очевидно, что в алгоритме <tt>Partition</tt> мы просматриваем все элементы «своей части» ровно один раз. Т.е. на каждом уровне рекурсии будут по одному разу просмотрены все элементы массива. <br /> | ||
+ | Это означает, что ''асимптотическая сложность <tt>Partition</tt>'' на каждом уровне рекурсии = <tt>Θ(n)</tt>. | ||
+ | |||
+ | Т.о., при условии ''деления примерно пополам'', '''асимптотическая сложность всего алгоритма = <tt>Θ(n log n)</tt>'''. | ||
+ | |||
+ | Теоретически доказано, что в среднем, если делим не точно пополам, асимптотическая сложность сохраняет формулу <tt>Θ(n log n)</tt>. <br /> | ||
+ | Вопрос: какова сложность в ''худшем'' случае? Худший — когда в качестве x выбираем минимальный (или максимальный) элемент. Это происходит (в нашей ситуации, т.к. мы выбираем первый элемент), если массив уже отсортирован. <br /> | ||
+ | В этом случае в результате разбиения на части большая часть будет уменьшаться на 1, и глубина рекурсии в процедуре <tt>Sort</tt> будет равна <math>n - 1</math>. <br /> | ||
+ | Поэтому в ''худшем'' случае '''асимптотическая сложность = <math>\Theta(n^2)</math>'''. | ||
+ | |||
+ | '''Утверждение.''' Для произвольных данных не существует алгоритма с асимптотической сложностью лучше, чем '''Θ(''n'' log ''n'')''' в среднем. | ||
+ | |||
+ | ===Генерация всех перестановок=== | ||
+ | |||
+ | Основная идея алгоритма генерации всех перестановок заключается в следующем. В массиве длины n, содержащем перестановку, будем менять последний элемент с каждым, после чего будем рекурсивно будем делать то же самое для массива длины n-1 и затем возвращать переставленный элемент на старое место. Если достигнута длина массива n=1, то переставлять ничего не нужно, а следует выдавать содержимое всего массива-перестановки на экран. Такой алгоритм позволит сгенерировать все перестановки, что следует из словесного рекурсивного определения: на последнем месте побывает каждый элемент, содержащийся в рассматриваемом массиве, после чего к оставшейся части массива рекурсивно будет применен тот же алгоритм. | ||
+ | <source lang="Pascal">procedure Perm(a: array of integer; n: integer); | ||
+ | begin | ||
+ | if n=1 then | ||
+ | Writeln(a) | ||
+ | else | ||
+ | for var i:=0 to n-1 do | ||
begin | begin | ||
− | + | Swap(a[i],a[n-1]); | |
− | end; | + | Perm(a,n-1); |
+ | Swap(a[i],a[n-1]); | ||
+ | end; | ||
+ | end; | ||
+ | |||
+ | const n=3; | ||
+ | |||
+ | begin | ||
+ | var a := ArrGen(n,i->i,1); | ||
+ | Perm(a,n); | ||
+ | end.</source> | ||
+ | Нетрудно видеть, что глубина рекурсии составляет n-1, а количество вызовов процедуры Perm составляет n!. | ||
+ | |||
+ | ===Генерация всех подмножеств=== | ||
+ | Генерация всех подмножеств представляет собой алгоритм '''перебора'''. В алгоритмах перебора перебираются все варианты и для подходящих вариантов выполняется определенное действие. В данном случае просто выводятся все подмножества. | ||
+ | <source lang="Delphi"> | ||
+ | procedure Generate(A: array of integer; i: integer; Subset: LinkedList<integer>); | ||
+ | begin | ||
+ | if i = A.Length then | ||
+ | Subset.Println | ||
+ | else | ||
+ | begin | ||
+ | Generate(A,i+1,Subset); // не добавлять | ||
+ | Subset.AddLast(A[i]); | ||
+ | Generate(A,i+1,Subset); // добавить | ||
+ | Subset.RemoveLast; | ||
+ | end; | ||
+ | end; | ||
+ | |||
+ | begin | ||
+ | var A := Arr(5,3,8,13,15); | ||
+ | var Subset := new LinkedList<integer>; | ||
+ | Generate(A,0,Subset); | ||
+ | end. | ||
</source> | </source> | ||
+ | |||
+ | ===Перебор с возвратом (backtracking)=== | ||
+ | ====Общая схема перебора с возвратом==== | ||
+ | |||
+ | <source lang="Delphi">procedure backtracking(k: integer); // k - номер хода | ||
+ | begin | ||
+ | { запись варианта } | ||
+ | |||
+ | if { решение найдено } then | ||
+ | { вывод решения } | ||
+ | else | ||
+ | { перебор всех вариантов } | ||
+ | if { вариант подходит } then | ||
+ | backtracking(k+1); | ||
+ | |||
+ | { стирание варианта } | ||
+ | end; | ||
+ | |||
+ | begin | ||
+ | backtracking(1); | ||
+ | end.</source> | ||
+ | |||
+ | ====Задача об обходе конем шахматной доски==== | ||
+ | <source lang="Delphi"> | ||
+ | const n = 8; | ||
+ | |||
+ | var | ||
+ | dx := Arr(2, 2, 1, 1, -1, -1, -2, -2); | ||
+ | dy := Arr(1, -1, 2, -2, 2, -2, 1, -1); | ||
+ | |||
+ | type KnightProblem = class | ||
+ | |||
+ | Solution := new integer[n, n]; | ||
+ | Success: boolean := false; | ||
+ | |||
+ | procedure Step(i, x, y: integer); | ||
+ | begin | ||
+ | if Success then | ||
+ | exit; | ||
+ | // отсечение неверных вариантов | ||
+ | if (x < 0) or (x >= n) or (y < 0) or (y >= n) or (Solution[x, y] > 0) then | ||
+ | exit; | ||
+ | |||
+ | // запись частичного решения | ||
+ | Solution[x, y] := i; | ||
+ | |||
+ | if i = n * n then | ||
+ | Success := true | ||
+ | else | ||
+ | for var k:=0 to 7 do // перебор вариантов | ||
+ | Step(i + 1, x + dx[k], y + dy[k]); | ||
+ | |||
+ | if not Success then | ||
+ | Solution[x, y] := 0; // возврат - стирание частичного решения | ||
+ | end; | ||
+ | end; | ||
+ | |||
+ | const | ||
+ | x0 = 1; // начальная клетка коня | ||
+ | y0 = 3; | ||
+ | |||
+ | begin | ||
+ | var kp := new KnightProblem(); | ||
+ | kp.Step(1, x0, y0); | ||
+ | if kp.Success then | ||
+ | writeln(kp.Solution); | ||
+ | |||
+ | writelnFormat('Время: {0} мс', Milliseconds/1000); | ||
+ | end.</source> |
Текущая версия на 13:34, 23 марта 2016
Содержание
- 1 Рекурсия
- 1.1 Основные определения
- 1.2 Простые примеры использования рекурсии
- 1.3 Графические изображения рекурсивных вызовов
- 1.4 Примеры использования рекурсии
- 1.5 Доказательство завершимости рекурсии
- 1.6 Формы рекурсивных подпрограмм
- 1.7 Примеры плохого и хорошего использования рекурсии
- 1.8 Быстрая сортировка
- 1.9 Генерация всех перестановок
- 1.10 Генерация всех подмножеств
- 1.11 Перебор с возвратом (backtracking)
Рекурсия
Основные определения
Рекурсией называется определение объекта через такой же объект.
Пример.
(1) <Список> ::= <Число> |<Список> ',' <Число>
В данном примере рекурсивной частью определения является "<Список> ',' <Число>".
Замечание 1. Рекурсивное определение, будучи конечным, определяет бесконечное множество объектов.
Заметим также, что <Список> можно определить и по-другому:
(2) <Список> ::= <Число> |<Число> ',' <Список>
Определение (1) называют леворекурсивным, а (2) — праворекурсивным.
Замечание 2. В рекурсивном определении обязательно (!!!) должна присутствовать нерекурсивная часть.
Рекурсивное определение может быть косвенным:
- по одной из ветвей рекурсивного определения упоминается объект, в определении которого, в свою очередь, по одной из ветвей определяется исходный объект.
Пример.
<оператор> ::= <присваивание> | <составной оператор> <присваивание> ::= <переменная> := <выражение> <составной оператор> ::= begin <список операторов> end <список операторов> ::= <пусто> | <оператор> ; <список операторов>
В данном примере имеется как прямое, так и косвенное рекурсивное определение.
В программировании под рекурсией понимается:
- вызов из подпрограммы самой себя (прямая рекурсия)
- вызов из подпрограммы другой подпрограммы, которая вызывает исходную (косвенная рекурсия)
При косвенной рекурсии обязательно использование опережающего объявления с помощью ключевого слова forward:
procedure q; forward; // опережающее определение
procedure p;
begin
...
q;
...
end;
procedure q;
begin
...
p;
...
end;
Простые примеры использования рекурсии
Пример 1.
procedure p(i: integer);
begin
write(i, ' ');
p(i + 1);
end;
При вызове этой процедуры произойдет рекурсивное зацикливание, т.к. рекурсивный вызов производится безусловно.
Вывод. Чтобы рекурсивного зацикливания не произошло, рекурсивный вызов должен происходить не безусловно, а по какому-то условию, которое всякий раз меняется и при каком-то рекурсивном вызове становится ложным (так называемое условие продолжения рекурсии).
Исправим нашу процедуру в соответствии со сделанным выводом:
procedure p(i: integer);
begin
write(i, ' ');
if i < 5 then
p(i + 1);
end;
При вызове p(0) будет выведено:
0 1 2 3 4 5
Графически, рекурсивные вызовы можно изобразить так:
Процесс последовательных рекурсивных вызовов подпрограммы из самой себя называется рекурсивным спуском.
Процесс возврата из рекурсивных вызовов называется рекурсивным возвратом.
В данном примере числа выводятся на рекурсивном спуске (т.е. в прямом порядке).
Однако, чтобы действия выполнялись в обратном порядке, их нужно вызывать на рекурсивном возврате.
Пример 2. Вывести
0 1 2 3 4 5 4 3 2 1 0
Решение:
procedure p(i: integer);
begin
write(i, ' ');
if i < 5 then then
begin
p(i + 1);
write(i, ' ');
end;
end;
Максимальная глубина рекурсивных вызовов называется глубиной рекурсии.
Текущая глубина называется текущим уровнем рекурсии.
Замечание. Чем больше глубина рекурсии, тем больше накладные расходы по памяти.
Графические изображения рекурсивных вызовов
Одно графическое изображение у нас уже было. Вспомним его:
procedure p(i: integer);
begin
write(i, ' ');
if i < 5 then
p(i + 1);
end;
Рассмотрим более детально вызов p(0) процедуры
procedure p(i: integer);
begin
write(i, ' ');
if i < 2 then
p(i + 1);
end;
Вспомним, что:
- Программный стек — это непрерывная область памяти, выделяемая программе, в частности, для размещения в ней вызываемых подпрограмм.
- При каждом вызове подпрограммы на стек кладется её запись активации (ЗА), а при возврате — снимается со стека.
Т.о. на стеке фактически хранятся все значения переменной i.
Замечание 1. Поскольку при каждом рекурсивном вызове на стек помещается ЗА, то при большой глубине рекурсии программный стек может переполниться, и программа завершится с ошибкой.
Это произойдет тем быстрее, чем больше суммарный объем формальных параметров и локальных переменных.
Поэтому следующий код — очень плохой!!!
procedure p(i: integer);
var a : array[1..1000] of real;
begin
...
p(i + 1);
...
end;
Замечание 2. Накладные расходы на помещение на стек ЗА, снятие ЗА со стека, а также присваивание значений формальным параметрам на стеке достаточно велики.
Поэтому если имеется простое нерекурсивное решение (итерационное), то следует использовать именно его.
Замечание 3. Любую рекурсию можно заменить итерацией.
Примеры использования рекурсии
Пример 1. Найти n! = n(n - 1)(n - 2)...2*1
Очевидно, определить n! можем следующим образом:
- <math>f(n) = \begin{cases} n (n - 1), & n > 0 \\ 1, & n = 0 \end{cases}</math>
Тогда решение имеет вид:
function nfact(n: integer): integer;
begin
if n = 0 then
Result := 1
else
Result := n * nfact(n - 1);
end;
Однако, заметим, что возвращаемое значение не определено для n < 0.
Как минимум, можно заменить условие n = 0 на n <= 0, но, в таком случае, мы получим неверный результат, т.к. факториал вообще не определен для отрицательных чисел.
Очевидно, необходимо с помощью утверждения проверить корректность входного параметра (Assert(n >= 0)). Но его использование при каждом рекурсивном вызове накладно. Поэтому можно "обернуть" рекурсивную подпрограмму, например, так:
function nfact(n: integer): integer;
function nfactRecur(n: integer): integer;
begin
if n = 0 then
Result := 1
else
Result := n * nfact(n - 1);
end;
begin
Assert(n >= 0);
Result := nfactRecur(n);
end;
Глубина рекурсии этого алгоритма равна n.
Пример 2. Найти <math>a^n</math>.
Дадим рекурсивное определение:
- <math>f(n) = \begin{cases} (a^{\frac{n}{2}})^2, & \mbox{if }n\mbox{ is even}, n > 0
\\ a a^{n-1}, & \mbox{if }n\mbox{ is odd}, n > 0 \\ 1, & n = 0 \\ \frac{1}{a^n}, & n < 0\end{cases}</math>
function power(a: real; n: integer): real;
begin
if n = 0 then
Result := 1
else if n < 0 then
Result := 1 / power(a, -n)
else // n > 0
if n mod 2 = 0 then
Result := sqr(power(a, n div 2))
else
Result := a * power(a, n - 1);
end;
Глубина рекурсии равна:
- <math>\log_2 n</math> — в лучшем случае
- <math>2\log_2 n</math> — в худшем
Пример 3. Нахождение минимального элемента в массиве.
Определить этот элемент можем как минимальный(один элемент, минимальный из массива без этого элемента), т.е. рекурсивное определение следующее:
- <math>minElem(A, n) = \begin{cases} A[n-1], & n = 1
\\ min(\; minElem(A, \; n - 1),\; A[n - 1]\;), & n > 1\end{cases}</math> В соответствии с этим имеем решение:
function MinElem(A: array of integer; n: integer): integer;
begin
if n = 1 then
Result := A[0]
else
Result := min(MinElem(A, n-1), A[n-1]));
end;
Глубина рекурсии равна n - 1.
Ясно, что это не очень хороший результат.
Можно значительно уменьшить глубину, если искать минимальный среди примерно равных частей массива.
Т.е. нужно поделить массив пополам, найти в каждой половине минимальные элементы и сравнить их. Поиск в половине осуществляется подобным же образом, и деление производится до тех пор, пока в подмассиве не останется один элемент.
Можно еще немного оптимизировать этот алгоритм — если в подмассиве два элемента, достаточно вернуть минимальный из них.
Теперь знания количества элементов недостаточно: необходимо знать, среди каких элементов массива вести поиск. Поэтому будем в качестве параметров передавать левую (l) и правую (r) границы подмассивов.
Дадим новое рекурсивное определение:
- <math>minElem(A, l, r) = \begin{cases} A[l], & l = r
\\ 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{cases}</math> Решение:
function MinElem(a: array of integer; l, r: integer): integer;
begin
if l = r then // если всего один элемент
Result := a[l]
else if r - l = 1 then // если ищем минимум из двух элементов
Result := min(a[l], a[r])
else
begin
var mid := (l + r) div 2;
Result := min(MinElem(a, l, mid), MinElem(a, mid+1, r));
end;
end;
Глубина рекурсии такого алгоритма уже примерно равна <math>\log_2 n</math> (по количеству делений).
Пример 4. Вывод односвязного линейного списка на экран.
Вспомним, как выглядит список:
Решение:
procedure Print<T>(h: Node<T>);
begin
if h = nil then
exit;
write(h.data, ' ');
Print(h.next);
end;
Глубина рекурсии равна длина списка - 1
Рекурсия называется концевой, если рекурсивный вызов является последним в подпрограмме.
Концевая рекурсия наиболее легко превращается в итеративный алгоритм:
while h <> nil do
begin
write(h.data, ' ');
h := h.next;
end;
Доказательство завершимости рекурсии
Добавим к рекурсивной процедуре целый параметр n:
p(n, ...);
Если при каждом рекурсивном вызове параметр n уменьшается получим вызовы
p(n) p(n - 1) p(n - 2) p(n - 3)
И если рекурсия завершается при n <= 0, то это служит доказательством завершимости рекурсии.
Действительно, на каждом следующем уровне рекурсии n становится меньше.
Поскольку при n <= 0 рекурсивных вызовов нет, то число рекурсивных вызовов конечно.
Утверждать, что рекурсия завершима, можно не всегда.
Пример.
procedure p(n);
begin
if n <= 0 then
exit
else
p(Random(2 * n) - n + 1);
end;
Формы рекурсивных подпрограмм
1. Действие выполняется на рекурсивном спуске
p(n) S(n) if B(n) then p(n - 1)
2. Действие выполняется на рекурсивном возврате
p(n) if B(n) then p(n - 1) S(n)
3. Действие выполняется и на рекурсивном спуске и на рекурсивном возврате
p(n) S1(n) if B(n) then p(n - 1) S2(n)
4. Каскадная рекурсия
p(n) S(n) if B1(n) then p(n - 1) if B2(n) then p(n - 1)
Эта рекурсия называется каскадной, т.к. каждый вызов подпрограммы может порождать несколько рекурсивных вызовов (каскад).
5. Удаленная рекурсия:
function f(i: integer): integer; begin if B1(n) then Result := ... else Result := f(f(i-1)); end;
Примером удаленной рекурсии служит функция Аккермана:
- <math>A(m,\;n)=\begin{cases}n+1,&m=0;
\\A(m-1,\;1),&m>0,\; n = 0; \\A(m-1,\;A(m,\;n-1)),& m > 0,\; n > 0.\end{cases}</math>
Примеры плохого и хорошего использования рекурсии
<xh4>Пример плохого использования рекурсии - числа Фибоначчи</xh4> Числа Фибоначчи задаются следующим рекуррентным соотношением:
- <math>F_1 = 1,\quad F_2 = 1,\quad F_{n+1} = F_n + F_{n-1} \quad n\in\mathbb{N}.</math>
Мы уже вычисляли их с помощью циклов. Возможно рекурсивное (плохое!) решение:
function Fib(n: integer): integer;
begin
if (n = 1) or (n = 2) then
Result := 1
else
Result := Fib(n - 1) + Fib(n - 2);
end;
Вот что произойдет при вызове Fib(7):
дерево рекурсивных вызовов
Как видим, одни и те же числа вычисляются по несколько раз:
- Fib(7): 1
- Fib(6): 1
- Fib(5): 2
- Fib(4): 3
- Fib(3): 5
- Fib(2): 8
Алгоритм можно улучшить, использовав массив, первоначально заполненный нулями.
При первом вычислении fib(n) будем заполнять соответствующий элемент, а при всех последующих — просто обращаться к его значению. Подобная методика называется мемоизацией, т.е. запоминанием промежуточных результатов для исключения их повторного вычисления.
var F: array[1..1000] of integer;
function Fib(n: integer): integer;
begin
if F[n] <> 0 then
Result := F[n]
else if (n = 1) or (n = 2) then
begin
Result := 1;
F[n] := 1;
end
else
begin
Result := Fib(n - 1) + Fib(n - 2);
F[n] := Result;
end;
end;
Очевидно, данный способ крайне неэффективен по сравнению с итерационным алгоритмом как по памяти, так и по времени работы. В частности, глубина рекурсии при вычислении n-того числа Фибоначчи составляет n-1.
Рекурсивный способ вычисления чисел Фибоначчи, построенный по итерационному алгоритму
Напомним итерационный алгоритм поиска n-того числа Фибоначчи:
a := 1;
b := 1;
for var i := 3 to n do
begin
c := a + b;
a := b;
b := c;
end;
Result := c;
Построим по нему рекурсивный алгоритм, передавая в каждую рекурсивную подпрограмму переменные a,b,c, меняющиеся на каждой итерации цикла. Фактически при каждом рекурсивном вызове мы будем совершать подстановку:
(a,b)->(b,a+b)
Рекурсивный алгоритм, реализованный по этой подстановке, будет иметь вид:
function fib (a,b,n: integer): integer;
begin
if n = 1 then
Result := a
else Result := fib(b,a+b,n-1)
end;
begin
for var i:=1 to 10 do
Print(fib(1,1,i));
end.
Рекурсия в данном примере - концевая. Как уже отмечалась, она легко заменяется итерацией, при этом как раз получается предыдущее итерационное решение. Хорошие оптимизирующие компиляторы делают это автоматически.
Пример хорошего использования рекурсии - ханойские башни
Задача состоит в следующем:
Даны три стержня. На первом лежат n дисков разного радиуса при условии, что ни один диск бОльшего радиуса не лежит на диске мЕньшего радиуса.
Hеобходимо перенести диски с первого стержня на третий, пользуясь вторым, при условии:
- за один ход можно переносить только один диск
- меньший диск должен лежать на большем
Идея алгоритма такая:
перекладываем n-1 диск с исходного стержня на вспомогательный оставшийся диск перекладываем на требуемый стержень лежащие на вспомогательном стержне диски перекладываем на требуемый диск
Т.о. имеем простое рекурсивное решение:
procedure MovePiramid(n: integer; f, t, w : integer);
begin
if n = 0 then
exit;
MovePiramid(n - 1, f, w, t);
writelnFormat('Переложить диск с {0} на {1}', f, t);
MovePiramid(n - 1, w, t, f);
end;
Быстрая сортировка
<xh4>Алгоритм</xh4>
Алгоритм быстрой сортировки (разновидность алгоритма «разделяй и влавствуй») состоит из двух этапов:
1. Выбор некоторого элемента массива x и разделение массива на две части так, что в первой оказываются все элементы <= x, а в о второй — >= x
2. Рекурсивное применение нашего алгоритма к полученным частям
Очевидно, алгоритм будет работать тем быстрее, чем на более равные части мы будем делить массив (в идеале — каждый раз пополам).
Поэтому мы должны стремиться выбрать элемент x так, чтобы примерно половина элементов массива была <= его, и, соответственно, вторая половина — >=. С другой стороны, выбор x не должен занимать много времени и, по крайней мере, не зависеть от n — размера массива).
Мы будем использовать простейший способ выбора x — в качестве него брать первый элемент.
На следующей анимации представлен пример применения алгоритма быстрой сортировки к массиву
4 1 7 3 2 9 5 8 6
Рассмотрим этап 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
Код программы
// Быстрая сортировка Ч. Хоара
/// Разделение a[l]..a[r] на части a[l]..a[q] <= a[q+1]..a[r]
function Partition(a: array of integer; l,r: integer): integer;
begin
var i := l - 1;
var j := r + 1;
var x := a[l];
while True do
begin
repeat
Inc(i);
until a[i]>=x;
repeat
Dec(j);
until a[j]<=x;
if i<j then
Swap(a[i],a[j])
else
begin
Result := j;
exit;
end;
end;
end;
/// Сортировка частей
procedure QuickSort(a: array of integer; l,r: integer);
begin
if l>=r then exit;
var j := Partition(a,l,r);
QuickSort(a,l,j);
QuickSort(a,j+1,r);
end;
const n = 20;
begin
var a := ArrRandom();
writeln('До сортировки: ');
Writeln(a);
QuickSort(a,0,a.Length-1);
writeln('После сортировки: ');
Writeln(a);
end.
<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, то переставлять ничего не нужно, а следует выдавать содержимое всего массива-перестановки на экран. Такой алгоритм позволит сгенерировать все перестановки, что следует из словесного рекурсивного определения: на последнем месте побывает каждый элемент, содержащийся в рассматриваемом массиве, после чего к оставшейся части массива рекурсивно будет применен тот же алгоритм.
procedure Perm(a: array of integer; n: integer);
begin
if n=1 then
Writeln(a)
else
for var i:=0 to n-1 do
begin
Swap(a[i],a[n-1]);
Perm(a,n-1);
Swap(a[i],a[n-1]);
end;
end;
const n=3;
begin
var a := ArrGen(n,i->i,1);
Perm(a,n);
end.
Нетрудно видеть, что глубина рекурсии составляет n-1, а количество вызовов процедуры Perm составляет n!.
Генерация всех подмножеств
Генерация всех подмножеств представляет собой алгоритм перебора. В алгоритмах перебора перебираются все варианты и для подходящих вариантов выполняется определенное действие. В данном случае просто выводятся все подмножества.
procedure Generate(A: array of integer; i: integer; Subset: LinkedList<integer>);
begin
if i = A.Length then
Subset.Println
else
begin
Generate(A,i+1,Subset); // не добавлять
Subset.AddLast(A[i]);
Generate(A,i+1,Subset); // добавить
Subset.RemoveLast;
end;
end;
begin
var A := Arr(5,3,8,13,15);
var Subset := new LinkedList<integer>;
Generate(A,0,Subset);
end.
Перебор с возвратом (backtracking)
Общая схема перебора с возвратом
procedure backtracking(k: integer); // k - номер хода
begin
{ запись варианта }
if { решение найдено } then
{ вывод решения }
else
{ перебор всех вариантов }
if { вариант подходит } then
backtracking(k+1);
{ стирание варианта }
end;
begin
backtracking(1);
end.
Задача об обходе конем шахматной доски
const n = 8;
var
dx := Arr(2, 2, 1, 1, -1, -1, -2, -2);
dy := Arr(1, -1, 2, -2, 2, -2, 1, -1);
type KnightProblem = class
Solution := new integer[n, n];
Success: boolean := false;
procedure Step(i, x, y: integer);
begin
if Success then
exit;
// отсечение неверных вариантов
if (x < 0) or (x >= n) or (y < 0) or (y >= n) or (Solution[x, y] > 0) then
exit;
// запись частичного решения
Solution[x, y] := i;
if i = n * n then
Success := true
else
for var k:=0 to 7 do // перебор вариантов
Step(i + 1, x + dx[k], y + dy[k]);
if not Success then
Solution[x, y] := 0; // возврат - стирание частичного решения
end;
end;
const
x0 = 1; // начальная клетка коня
y0 = 3;
begin
var kp := new KnightProblem();
kp.Step(1, x0, y0);
if kp.Success then
writeln(kp.Solution);
writelnFormat('Время: {0} мс', Milliseconds/1000);
end.