Основы программирования — второй семестр 08-09; Михалкович С.С.; III часть — различия между версиями
Admin (обсуждение | вклад) (→Рекурсия) |
Admin (обсуждение | вклад) (→Рекурсия) |
||
Строка 53: | Строка 53: | ||
Быстрая сортировка | Быстрая сортировка | ||
− | < | + | <source lang="Pascal"> |
procedure QuickSort0(l,r: integer); | procedure QuickSort0(l,r: integer); | ||
var i,j,x: integer; | var i,j,x: integer; | ||
Строка 73: | Строка 73: | ||
if i<r then QuickSort0(i,r); | if i<r then QuickSort0(i,r); | ||
end; | end; | ||
− | </ | + | </source> |
Версия 01:41, 17 марта 2009
Рекурсия
Определение рекурсии.
Рекурсивные определения. Примеры: n!, a^n. Нерекурсивная часть рекурсивного определения. Праворекурсивное и леворекурсивное определения.
Рекурсия в программировании. Прямая и косвенная рекурсия. Необходимость forward при косвенной рекурсии.
Простые примеры использования рекурсии. Рекурсивное зацикливание.
Понятие рекурсивного спуска и рекурсивного возврата. Графическое изображение рекурсивного спуска и рекурсивного возврата. Глубина рекурсии, текущий уровень рекурсии.
Примеры вычисления 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.
Пример плохого использования рекурсии - числа Фибоначчи Исправление ситуации - вспомогательный массив
Пример хорошего использования рекурсии - ханойские башни.
Замена рекурсии итерацией с использованием стека
Быстрая сортировка
procedure QuickSort0(l,r: integer);
var i,j,x: integer;
begin
i:=l;
j:=r;
x:=A[(l+r) div 2];
repeat
while A[i]<x do Inc(i);
while A[j]>x do Dec(j);
if i<=j then
begin
Swap(A[i],A[j]);
Inc(i);
Dec(j)
end
until i>j;
if l<j then QuickSort0(l,j);
if i<r then QuickSort0(i,r);
end;