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

Лекция 5

Рекурсия

Введение

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

Пример.

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

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

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

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

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

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

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

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

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

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

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

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

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

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;

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

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

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

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