Основы программирования — второй семестр 08-09; Михалкович С.С.; III часть — различия между версиями
Juliet (обсуждение | вклад) |
|||
Строка 1: | Строка 1: | ||
− | === | + | [[Категория:Конспекты]] |
+ | <small>Лекция 5</small> | ||
+ | == Рекурсия == | ||
+ | === Введение === | ||
+ | '''Рекурсией''' называется определение объекта через такой же объект. | ||
+ | |||
+ | <u>''Пример''</u>. | ||
+ | (1) <Список> ::= <Число> | ||
+ | |<Список> ',' <Число> | ||
+ | В данном примере ''рекурсивной'' частью определения является "<tt><Список> ',' <Число></tt>". | ||
+ | |||
+ | '''Замечание 1.''' Рекурсивное определение, будучи конечным, определяет бесконечное множество объектов. | ||
+ | |||
+ | Заметим также, что <Список> можно определить и по-другому: | ||
+ | (2) <Список> ::= <Число> | ||
+ | |<Число> ',' <Список> | ||
+ | |||
+ | Определение (1) называют '''''леворекурсивным''''', <br /> а (2) — '''''праворекурсивным'''''. | ||
+ | |||
+ | '''Замечание 2.''' В рекурсивном определении ''обязательно (!!!)'' должна присутствовать '''''нерекурсивная''''' часть. | ||
+ | |||
+ | Рекурсивное определение может быть '''косвенным''': | ||
+ | :по одной из ветвей рекурсивного определения упоминается объект, в определении которого, в свою очередь, по одной из ветвей определяется исходный объект. | ||
− | |||
− | + | В программировании под '''рекурсией''' понимается: | |
− | + | * вызов из подпрограммы самой себя ('''''прямая''' рекурсия'') | |
− | + | * вызов из подпрограммы другой подпрограммы, которая вызывает исходную ('''''косвенная''' рекурсия'') | |
+ | |||
+ | При косвенной рекурсии ''обязательно'' использование '''''опережающего объявления''''' с помощью ключевого слова <tt>'''forward'''</tt>: | ||
+ | <source lang="Pascal">procedure q; foreard; // опережающее определение | ||
− | + | procedure p; | |
− | + | begin | |
+ | ... | ||
+ | q; | ||
+ | ... | ||
+ | end; | ||
− | + | procedure q; | |
+ | begin | ||
+ | ... | ||
+ | p; | ||
+ | ... | ||
+ | end;</source> | ||
+ | === Простые примеры использования рекурсии === | ||
+ | Рекурсивное зацикливание. | ||
Понятие рекурсивного спуска и рекурсивного возврата. Графическое изображение рекурсивного спуска и рекурсивного возврата. | Понятие рекурсивного спуска и рекурсивного возврата. Графическое изображение рекурсивного спуска и рекурсивного возврата. | ||
<br>[[Изображение:Графическое_изображение_рекурсии.gif]]<br> | <br>[[Изображение:Графическое_изображение_рекурсии.gif]]<br> | ||
− | |||
Глубина рекурсии, текущий уровень рекурсии. | Глубина рекурсии, текущий уровень рекурсии. | ||
+ | === Графические изображения рекурсивных вызовов === | ||
− | Примеры | + | === Примеры использования рекурсии === |
− | + | Рекурсивные определения. Примеры: n!, a^n. | |
Пример нахождения минимума в массиве. | Пример нахождения минимума в массиве. | ||
Строка 27: | Строка 62: | ||
Пример вывода списка с помощью рекурсии, применения операции ко всем элементам списка. | Пример вывода списка с помощью рекурсии, применения операции ко всем элементам списка. | ||
+ | === Доказательство завершимости рекурсии === | ||
− | + | === Формы рекурсивных подпрограмм === | |
− | |||
− | Формы рекурсивных подпрограмм | ||
# Действия - на рекурсивном спуске | # Действия - на рекурсивном спуске | ||
# Действия - на рекурсивном возврате | # Действия - на рекурсивном возврате | ||
Строка 46: | Строка 80: | ||
A(n,m) = A(n-1,1), n>0, m=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(n,m) = A(n-1,A(n,m-1)), n>0, m>0. | ||
− | + | === Примеры плохого и хорошего использования рекурсии === | |
Пример плохого использования рекурсии - числа Фибоначчи | Пример плохого использования рекурсии - числа Фибоначчи | ||
Исправление ситуации - вспомогательный массив | Исправление ситуации - вспомогательный массив | ||
Пример хорошего использования рекурсии - ханойские башни. | Пример хорошего использования рекурсии - ханойские башни. | ||
+ | === Алгоритм быстрой сортировки === | ||
===Быстрая сортировка=== | ===Быстрая сортировка=== | ||
Строка 96: | Строка 131: | ||
end; | end; | ||
</source> | </source> | ||
− |
Версия 21:36, 22 марта 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;
Простые примеры использования рекурсии
Рекурсивное зацикливание.
Понятие рекурсивного спуска и рекурсивного возврата. Графическое изображение рекурсивного спуска и рекурсивного возврата.
Глубина рекурсии, текущий уровень рекурсии.
Графические изображения рекурсивных вызовов
Примеры использования рекурсии
Рекурсивные определения. Примеры: 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;