Основы программирования — второй семестр 08-09; Михалкович С.С.; III часть
Рекурсия
Определение рекурсии.
Рекурсивные определения. Примеры: 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.
Пример плохого использования рекурсии - числа Фибоначчи Исправление ситуации - вспомогательный массив
Пример хорошего использования рекурсии - ханойские башни.
Быстрая сортировка
Все элементы 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;