Основы программирования — второй семестр 08-09; Михалкович С.С.; III часть — различия между версиями
Juliet (обсуждение | вклад) (→Простые примеры использования рекурсии) |
Juliet (обсуждение | вклад) (→Простые примеры использования рекурсии) |
||
Строка 55: | Строка 55: | ||
− | '''Вывод.''' | + | '''Вывод.''' Чтобы '''''рекурсивного зацикливания''''' не произошло, рекурсивный вызов должен происходить не безусловно, а по какому-то условию, которое всякий раз меняется и при каком-то рекурсивном вызове становится ложным (так называемое '''условие продолжения рекурсии'''). |
+ | |||
+ | Исправим нашу процедуру в соответствии со сделанным выводом: | ||
+ | <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 />Однако, чтобы действия выполнялись в ''обратном'' порядке, их нужно вызывать на рекурсивном возврате. | ||
+ | |||
− | |||
<br>[[Изображение:Графическое_изображение_рекурсии.gif]]<br> | <br>[[Изображение:Графическое_изображение_рекурсии.gif]]<br> | ||
Глубина рекурсии, текущий уровень рекурсии. | Глубина рекурсии, текущий уровень рекурсии. | ||
− | + | ||
<source lang="Pascal"></source> | <source lang="Pascal"></source> | ||
<source lang="Pascal"></source> | <source lang="Pascal"></source> |
Версия 22:33, 24 марта 2009
Лекция 5
Содержание
- 1 Рекурсия
- 1.1 Введение
- 1.2 Простые примеры использования рекурсии
- 1.3 Графические изображения рекурсивных вызовов
- 1.4 Примеры использования рекурсии
- 1.5 Доказательство завершимости рекурсии
- 1.6 Формы рекурсивных подпрограмм
- 1.7 Примеры плохого и хорошего использования рекурсии
- 1.8 Алгоритм быстрой сортировки
- 1.9 Быстрая сортировка
Рекурсия
Введение
Рекурсией называется определение объекта через такой же объект.
Пример.
(1) <Список> ::= <Число> |<Список> ',' <Число>
В данном примере рекурсивной частью определения является "<Список> ',' <Число>".
Замечание 1. Рекурсивное определение, будучи конечным, определяет бесконечное множество объектов.
Заметим также, что <Список> можно определить и по-другому:
(2) <Список> ::= <Число> |<Число> ',' <Список>
Определение (1) называют леворекурсивным,
а (2) — праворекурсивным.
Замечание 2. В рекурсивном определении обязательно (!!!) должна присутствовать нерекурсивная часть.
Рекурсивное определение может быть косвенным:
- по одной из ветвей рекурсивного определения упоминается объект, в определении которого, в свою очередь, по одной из ветвей определяется исходный объект.
В программировании под рекурсией понимается:
- вызов из подпрограммы самой себя (прямая рекурсия)
- вызов из подпрограммы другой подпрограммы, которая вызывает исходную (косвенная рекурсия)
При косвенной рекурсии обязательно использование опережающего объявления с помощью ключевого слова forward:
procedure q; foreard; // опережающее определение
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
Графически, рекурсивные вызовы можно изобразить так:
Процесс последовательных рекурсивных вызовов подпрограммы из самой себя называется рекурсивным спуском.
Процесс возврата из рекурсивных вызовов называется рекурсивным возвратом.
В данном примере числа выводятся на рекурсивном спуске (т.е. в прямом порядке).
Однако, чтобы действия выполнялись в обратном порядке, их нужно вызывать на рекурсивном возврате.
Глубина рекурсии, текущий уровень рекурсии.
Графические изображения рекурсивных вызовов
Примеры использования рекурсии
Рекурсивные определения. Примеры: n!, a^n. Пример нахождения минимума в массиве.
Замечания
- О переполнении программного стека
- О накладных расходах на рекурсию
- О замене рекурсии итерацией
Пример вывода списка с помощью рекурсии, применения операции ко всем элементам списка.
Доказательство завершимости рекурсии
Формы рекурсивных подпрограмм
- Действия - на рекурсивном спуске
- Действия - на рекурсивном возврате
- Действия - на рекурсивном спуске и возврате
- Каскадная рекурсия
- Удаленная рекурсия:
function f(i: integer): integer; begin if B1(n) then Result:=... else Result:=f(f(i-1)); end;
Пр. Функция Аккермана.
A(n,m) = m+1, n=0; A(n,m) = A(n-1,1), n>0, m=0; A(n,m) = A(n-1,A(n,m-1)), n>0, m>0.
Примеры плохого и хорошего использования рекурсии
Пример плохого использования рекурсии - числа Фибоначчи Исправление ситуации - вспомогательный массив
Пример хорошего использования рекурсии - ханойские башни.
Алгоритм быстрой сортировки
Быстрая сортировка
Все элементы A[0]..A[q] меньше или равны x, а все элементы A[q+1]..A[n-1]
procedure QuickSort(A: array of integer);
// Partition - разделение A[l]..A[r] на части A[l]..A[q] <= A[q+1]..A[r]
function Partition(l,r: integer): integer;
begin
var i := l - 1;
var j := r + 1;
var x := A[l];
while True do
begin
repeat
i += 1;
until A[i]>=x;
repeat
j -= 1;
until A[j]<=x;
if i<j then
Swap(A[i],A[j])
else
begin
Result := j;
exit;
end;
end;
end;
// Сортировка частей
procedure Sort(l,r: integer);
begin
if l>=r then exit;
var j := Partition(l,r);
Sort(l,j);
Sort(j+1,r);
end;
begin
Sort(0,a.Length-1)
end;