В этой теме рассматривается понятие рекурсия и ее применение к решению задач. Приводятся решения задач из предыдущих тем с использованием рекурсии.
 
Рекурсия

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

Рекурсивные определения представляют собой мощный аппарат в математике.
Например:

1)  Натуральные числа:
а) 0 есть натуральное число,
б) число, следующее за натуральным, есть натуральное число.
2)  Деревья:
а) 0 есть дерево (пустое дерево),
б) если А1 и А2 - деревья, то построение, содержащее вершину с двумя  ниже расположенными деревьями, опять дерево.
3) Функция n! факториал (для неотрицательных целых чисел):
а) 0!=1,
б) n>0: n!=n·(n-1)!
Мощность рекурсивного определения заключается в том, что оно позволяет с помощью конечного высказывания определить бесконечное множество объектов. Аналогично, с помощью конечной рекурсивной программы можно описать бесконечное вычисление, причем программа не будет содержать явных повторений. В общем виде рекурсивную программу Р можно выразить как некоторую композицию Р из множества операторов С (не содержащих Р) и самой Р:  Р=Р[С,Р].

Для выражения рекурсивных программ удобнее пользоваться процедурами или функциями. Если некоторая процедура Р содержит явную ссылку на саму себя, то её называют прямо рекурсивной, если же Р ссылается на другую процедуру В, содержащую ссылку на Р, то Р называют косвенно рекурсивной.

Как правило с процедурой связывают множество локальных переменных, которые определены только в этой процедуре. При каждой рекурсивной активации процедуры порождается новое множество локальных, связанных переменных. Хотя они имеют те же самые имена, что и соответствующие элементы локального множества предыдущего поколения этой процедуры, их значения отличны от последних, а любые конфликты по именам разрешаются с помощью правил, определяющих область действия идентификаторов: идентификатор всегда относится к самому последнему порожденному множеству переменных.

Рекурсивные процедуры могут приводить к не заканчивающимся вычислениям. Очевидно основное требование, чтобы рекурсивное обращение к Р управлялось некоторым условием Х, которое в какой-то момент становится ложным.

Р== if X then P[C,P]
 Основной способ доказательства конечности некоторого повторяющегося процесса:
1.  Определяется функция f(x), такая, что из f(x)<=0 следует истинность условия окончания цикла,
2.  Доказывается, что при каждом прохождении цикла f(x) уменьшается.
Аналогично доказывается и окончание рекурсии - показывается, что Р уменьшает f(x), такую, что из f(x)<=0 следует истинность В.
 
В практических приложениях важно убедится, что максимальная глубина рекурсий не только конечна, но и достаточно мала. Дело в том, что каждая рекурсивная активация процедуры Р требует памяти для размещения её переменных. Кроме этих переменных нужно ещё сохранять текущее "состояние вычислений", чтобы можно было вернуться в него по окончании новой активации Р.
Рассмотрим некоторые задачи, где можно применить рекурсию.

Задача1. Написать функцию вычисления факториала целого положительного числа n.
Для решения будем использовать равенства  0!=1,  n!=n·(n-1)!

Function fakt (n: integer): integer;
      begin
         if n=0 then fakt:=1 else fakt:= n*fakt (n-1);
     end;
Задача 2. Написать рекурсивную функцию вычисления xn   , где n>=0.
Для решения будем использовать равенства xn =1, при n=0, и xn =x·xn-1 , при n>0.
Function pow (x:real; n: byte):real;
     begin
          if n=0 then pow:=1 else pow:=x*pow(x,n-1);
     end;
Задача 3. Ханойские башни.
Когда-то в Ханое стоял храм и рядом с ним три башни (столба).  На первую башню надеты 64 диска разного диаметра:  самый большой - внизу, а самый маленький - вверху.  Монахи этого храма должны были  перенести все диски с первого столба на третий, соблюдая следующие правила:
1) можно перемещать только по одному диску;
2) больший диск нельзя класть на меньший;
3) снятый диск нельзя отложить,  его необходимо сразу  надеть  на  другой  столб.
Предположим, с первого столба А надо перенести на третий С n дисков. Диски пронумерованы в порядке возрастания их диаметров. Предположим, что мы умеем переносить n-1 дисков.  В этом случае n дисков перенесем посредством следующих шагов:
1) верхние  n-1  дисков перенесем с первого на второй,  пользуясь свободным третьим столбом;
2) последний диск наденем на третий столб;
3) n-1 дисков перенесем на  третий,  пользуясь  свободным  первым столбом.
Аналогичным образом можно перенести n-1,n-2 и т.д.  дисков. Когда n=1, перенос осуществляется непосредственно с первого столба на третий.
Var
  a,b,c: char;
  n: integer;
Procedure Move (n:integer; a,b,c: char);
BEGIN
  if N>=1 then
    begin
      move(n-1,a,c,b);
      Write(a,'-->',c,'  ');
      move(n-1,b,a,c);
    end;
END;
BEGIN
  write('введи количество колец'); readln (n);
  move (n,'1','2','3');
END.
Задача 4. Вывести все сочетания из n по k. (см. тему 3)
При вводе задается набор символов в виде строки. Длина строки= n. Затем вводится число k.
type
   stroka        =string;
var
  s,ss           :stroka;
  k,n,ii         :byte;
  num,count      :integer;
procedure cmn(q:stroka;i,j:byte);
label 1;
var
  len             :integer;
  Ch                :char;
BEGIN
    while count<=n do
       begin
          q:=s[j];count:=count+1;{в стек заносятся элементы по одному}
          cmn(q,1,j+1);
       end;
1:
    len:=length(q);
    if len<k
       then
         begin
           if j+i<=n then
             begin
               cmn(q,i+1,j);
             end;
         end;
    if (len<k) and (j+i<=n) then
       begin
         if q[len]<>s[j+i]
          then
            begin
               q:=q+s[j+i];goto 1;
            end;
       end;
    if length(q)=k then begin Writeln(q,':',num); num:=num+1;end;
END;
BEGIN ClrScr;num:=1;
    Write('Элементы? ');Readln(s);n:=length(s);
    Write('Сколько элементов ? ');Readln(k);
    count:=1;
    cmn('',1,1);
END.
Задача 5. Перечислить все способы расстановки n ферзей на шахматной доске n x n, при которых они не бьют друг друга. (см. тему 4)
Const
    N=8;
Type
   {занятость горизонтали, где индекс массива номер горизонтали}
    YesHor =array[1..N] of boolean; 
   {номер диагонали определяется разностью индексов квадратной матрицы i-j,
     диагонали параллельные главной диагонали матрицы}
   YesD1  =array[-(N-1)..(N-1)] of boolean;
   {номер диагонали определяется суммой индексов i+j, диагонали параллельные вспомогательной}
   YesD2  =array[2..2*N] of boolean;
   {индекс -номер ферзя, то есть номер вертикали}
    ferz   =array[1..N] of integer;
Var
  x     :ferz;
  a     :yeshor;
  b     :yesD1;
  c     :YesD2;
  Count :integer; {номер варианта расстовки ферзей}
Procedure Print;
var
  k:integer;
BEGIN
  inc(Count);
  for k:=1 to N do Write(x[k],'..');Write(Count);
  Writeln;
  if (Count mod 24)=0 then Readln;
END;
Procedure Try(i:integer);
Var
  j:integer;
BEGIN
  for j:=1 to N do
   if a[j] and b[i-j] and c[i+j] then
   {если клетка не бьется, то}
     begin
       x[i]:=j;{то ферзю i,устанавливается номер горизонтали j}
       {соответсвующие горизонталь, и две вертикали становятся занятыми}
       a[j]:=false;b[i-j]:=false;c[i+j]:=false;
         {если это не последний ферзь, то пытаемся поставить следущий ферьз, иначе распечатка варианта}
       if i<n then Try(i+1) else print;
       a[j]:=true;b[i-j]:=true;c[i+j]:=true;
         {если нет не битого поля для данного ферзя, то предыдущая занятая
          позиция освобождается(отход назад) и все повторяется}
     end;
END;
Procedure Init;
BEGIN
  ClrScr;Count:=0;
  FillChar(a,sizeof(a),1);FillChar(b,sizeof(b),1);FillChar(c,sizeof(c),1);
  {Все элементы логических массивов a,b,c становятся TRUE (1),
    то есть то есть клетки доски не находятся под боем}
  {все ферзи вне доски , то есть все x[i]=0}
FillChar(x,sizeof(x),0);END;
BEGIN
  Init;{устанавливаем все первоначальные данные}
  Try(1);{выполняем расстановку}
END.
Литература:
1.  В.А.Дагене, Г.К.Григас, К.Ф.Аугутис . 100 задач по программированию.
2.  Ж.Арсак. Программирование игр и головоломок.
3.  Н.Вирт. Алгоритмы и структуры данных.
4.  С.Барт. Россыпи головоломок.
5.  Математический энциклопедический словарь.
6.  М.Гарднер. Математические досуги.
 Упражнения:
1.  Написать рекурсивную функцию вычисления чисел Фибоначчи, определяемых соотношением fibn+1=fibn + fibn-1 и fib1=1, fib0=0.
2.  Дана рекурсивная функция
       function f(n: integer):integer;
           begin
                if n>100 then f:=n-10 else f:=f(f(n+11));
           end;
     Вычислить f(106), f(99), f(85). Какие вообще значения принимает эта  функция?
3.  Решить задачу 2, если требуется, чтобы глубина рекурсии не превосходила C·logn, где n - показатель степени.
4.  Имеется Х населенных пунктов, перенумерованных от 1 до х (х=10). Некоторые пары пунктов соединены дорогами. Определить, можно ли попасть по этим дорогам из 1-го пункта в х-й. Информация о дорогах задается в виде последовательности пар чисел i и j (i<j). Указывающих, что i-й и j-й пункты соединены дорогой; признак конца этой последовательности - пара нулей.
Перейти на первую страницу