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

Лекция 5

Содержание

1 Рекурсия

Рекурсия

Введение

Рекурсией называется определение объекта через такой же объект.

Пример.

(1)  <Список> ::= <Число>
                 |<Список> ',' <Число>

В данном примере рекурсивной частью определения является "<Список> ',' <Число>".

Замечание 1. Рекурсивное определение, будучи конечным, определяет бесконечное множество объектов.

Заметим также, что <Список> можно определить и по-другому:

(2)  <Список> ::= <Число>
                 |<Число> ',' <Список>

Определение (1) называют леворекурсивным,
а (2) — праворекурсивным.

Замечание 2. В рекурсивном определении обязательно (!!!) должна присутствовать нерекурсивная часть.

Рекурсивное определение может быть косвенным:

по одной из ветвей рекурсивного определения упоминается объект, в определении которого, в свою очередь, по одной из ветвей определяется исходный объект.

В программировании под рекурсией понимается:

вызов из подпрограммы самой себя (прямая рекурсия)
вызов из подпрограммы другой подпрограммы, которая вызывает исходную (косвенная рекурсия)

При косвенной рекурсии обязательно использование опережающего объявления с помощью ключевого слова forward:

procedure q; forward;  // опережающее определение

procedure p;
begin
  ...
  q;
  ...
end;

procedure q;
begin
  ...
  p;
  ...
end;

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

Пример 1.

procedure p(i: integer);
begin
  write(i, ' ');
  p(i + 1);
end;

При вызове этой процедуры произойдет рекурсивное зацикливание, т.к. рекурсивный вызов производится безусловно.

Вывод. Чтобы рекурсивного зацикливания не произошло, рекурсивный вызов должен происходить не безусловно, а по какому-то условию, которое всякий раз меняется и при каком-то рекурсивном вызове становится ложным (так называемое условие продолжения рекурсии).

Исправим нашу процедуру в соответствии со сделанным выводом:

procedure p(i: integer);
begin
  write(i, ' ');
  if i < 5 then
    p(i + 1);
end;

При вызове p(0) будет выведено:

0 1 2 3 4 5

Графически, рекурсивные вызовы можно изобразить так:

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

В данном примере числа выводятся на рекурсивном спуске (т.е. в прямом порядке).
Однако, чтобы действия выполнялись в обратном порядке, их нужно вызывать на рекурсивном возврате.

Пример 2. Вывести

0 1 2 3 4 5 4 3 2 1 0

Решение:

procedure p(i: integer);
begin
  write(i, ' ');
  if i < 5 then then
  begin
    p(i + 1);
    write(i, ' ');
  end;
end;

Максимальная глубина рекурсивных вызовов называется глубиной рекурсии.
Текущая глубина называется текущим уровнем рекурсии.

Замечание. Чем больше глубина рекурсии, тем больше накладные расходы по памяти.

Графические изображения рекурсивных вызовов

Одно графическое изображение у нас уже было. Вспомним его:

procedure p(i: integer);
begin
  write(i, ' ');
  if i < 5 then
    p(i + 1);
end;

Рассмотрим более детально вызов p(0) процедуры

procedure p(i: integer);
begin
  write(i, ' ');
  if i < 2 then
    p(i + 1);
end;

Вспомним, что:

Программный стек — это непрерывная область памяти, выделяемая программе для помощи в вызове подпрограмм.
При каждом вызове подпрограммы на стек кладется её ЗА, а при возврате — снимается со стека.

Т.о. на стеке фактически хранятся все значения переменной i.

Замечание 1. Поскольку при каждом рекурсивном вызове на стек помещается ЗА, то при большой глубине рекурсии программный стек может переполниться, и программа завершится с ошибкой.
Это произойдет тем быстрее, чем больше суммарный объем формальных параметров и локальных переменных.

Поэтому следующий код — очень плохой!!!

procedure p(i: integer);
var a : array[1..1000] of real;
begin
  ...
  p(i + 1);
  ...
end;

Замечание 2. Накладные расходы на помещение на стек ЗА, снятие ЗА со стека, а также присваивание значений формальным параметрам на стеке достаточно велики.
Поэтому если имеется простое нерекурсивное решение (итерационное), то следует использовать именно его.

Замечание 3. НЕ любую рекурсию можно заменить итерацией.

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

Пример 1. Найти n! = n(n - 1)(n - 2)...2*1
Очевидно, определить n! можем следующим образом:

<math>f(n) = \begin{cases} n (n - 1), & n > 0 \\ 1, & n = 0 \end{cases}</math>

Тогда решение имеет вид:

function nfact(n: integer): integer;
begin
  if n = 0 then
    Result := 1
  else
    Result := n * nfact(n - 1);
end;

Однако, заметим, что возвращаемое значение не определено для n < 0.
Как минимум, можно заменить условие n = 0 на n <= 0, но, в таком случае, мы получим неверный результат, т.к. факториал вообще не определен для отрицательных чисел.
Очевидно, необходимо с помощью утверждения проверить корректность входного параметра (Assert(n >= 0)). Но его использование при каждом рекурсивном вызове накладно. Поэтому можно "обернуть" рекурсивную подпрограмму, например, так:

function nfact(n: integer): integer;
  function nfactRecur(n: integer): integer;
  begin
    if n = 0 then
      Result := 1
    else
      Result := n * nfact(n - 1);
  end;
begin
  Assert(n >= 0);
  Result := nfactRecur(n);
end;

Глубина рекурсии этого алгоритма равна n.

Пример 2. Найти aⁿ. Дадим рекурсивное определение:

<math>f(n) = \begin{cases} (a^{\frac{n}{2}})^2, & \mbox{if }n\mbox{ is even}, n > 0

\\ a a^{n-1}, & \mbox{if }n\mbox{ is odd}, n > 0 \\ 1, & n = 0 \\ \frac{1}{a^n}, & n < 0\end{cases}</math>

function power(a: real; n: integer): real;
begin
  if n = 0 then
    Result := 1
  else if n < 0 then
    Result := 1 / power(a, -n)
  else  // n > 0
    if n mod 2 = 0 then
      Result := sqr(power(a, n div 2))
    else
      Result := a * power(a, n - 1);
end;

Глубина рекурсии равна:

log₂n — в лучшем случае
2log₂n — в худшем

Пример 3. Нахождение минимального элемента в массиве. Определить этот элемент можем как минимальный(один элемент, минимальный из массива без этого элемента), т.е. рекурсивное определение следующее:

<math>minElem(A, n) = \begin{cases} A[n-1], & n = 1

\\ min( minElem(A, n-1), A[n - 1] ), & n > 1\end{cases}</math> В соответствии с этим имеем решение:

function MinElem(A: array of integer; n: integer): integer;
begin
  if n = 1 then
    Result := A[0]
  else
    Result := min(MinElem(A, n-1), A[n-1]));
end;

Глубина рекурсии равна n - 1.

Ясно, что это не очень хороший результат.

Пример 4. Вывод односвязного линейного списка на экран.

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