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

Версия 01:40, 17 марта 2009

Рекурсия

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

Рекурсивные определения. Примеры: 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);

  i:=l;
  j:=r;
  x:=A[(l+r) div 2];
  repeat
    while A[i]<x do Inc(i);

    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;