Основы программирования — второй семестр 08-09; Михалкович С.С.; III часть

Рекурсия

Определение рекурсии.

Рекурсивные определения. Примеры: n!, a^n. Нерекурсивная часть рекурсивного определения. Праворекурсивное и леворекурсивное определения.

Рекурсия в программировании. Прямая и косвенная рекурсия. Необходимость forward при косвенной рекурсии.

Простые примеры использования рекурсии. Рекурсивное зацикливание.

Понятие рекурсивного спуска и рекурсивного возврата. Графическое изображение рекурсивного спуска и рекурсивного возврата. Глубина рекурсии, текущий уровень рекурсии.

Примеры вычисления n!, a^n.

Пример нахождения минимума в массиве.

Замечания

• О переполнении программного стека
• О накладных расходах на рекурсию
• О замене рекурсии итерацией

Пример вывода списка с помощью рекурсии, применения операции ко всем элементам списка.

Доказательство завершимости рекурсии

Формы рекурсивных подпрограмм

1. Действия - на рекурсивном спуске
2. Действия - на рекурсивном возврате
3. Действия - на рекурсивном спуске и возврате
4. Каскадная рекурсия
5. Удаленная рекурсия:

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;