Основы программирования — второй семестр 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.

Пример плохого использования рекурсии - числа Фибоначчи Исправление ситуации - вспомогательный массив

Пример хорошего использования рекурсии - ханойские башни.

Быстрая сортировка

Все элементы 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;