РЕКУРСИЯ

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

 

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

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

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

Мощность рекурсивного определения заключается в том, что оно позволяет с помощью конечного высказывания определить бесконечное множество объектов. Аналогично, с помощью конечной рекурсивной программы можно описать бесконечное вычисление, причем программа не будет содержать явных повторений. В общем виде рекурсивную программу Р можно выразить как некоторую композицию Р из множества операторов С (не содержащих Р) и самой Р: Р=Р[С,Р].

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

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

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

Р== 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, где n0.

Для решения будем использовать равенства 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. (см. тему "Размещения. Перестановки. Сочетания.")

При вводе задается набор символов в виде строки. Длина строки= 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
cmn(q,i+1,j);
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×n, при которых они не бьют друг друга. (см. тему "Обход дерева. Перебор с возвратами")

Const
N=8;
Type
YesHor = array[1..N] of boolean; {занятость горизонтали, где индекс массива
номер горизонтали}
YesD1 = array[-(N-1)..(N-1)] of boolean; {номер диагонали определяется
разностью индексов квадратной матрицы i-j, диагонали параллельные главной
диагонали матрицы}
YesD2 = array[2..2*N] of boolean; {номер диагонали определяется суммой
индексов i+j, диагонали параллельные вспомогательной}
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), то есть клетки
доски не находятся под боем}
FillChar(x,sizeof(x),0); {все ферзи вне доски, то есть все x[i]=0}
end;

BEGIN
Init; {устанавливаем все первоначальные данные}
Try(1); {выполняем расстановку}
END.

 

  •  
    •  
      •  
          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). Какие вообще значения принимает эта функция?
      • 1. Написать рекурсивную функцию вычисления чисел Фибоначчи, определяемых соотношением fibn+1=fibn + fibn-1 и fib1=1, fib0=0.
        2. Дана рекурсивная функция: 3. Решить задачу 2, если требуется, чтобы глубина рекурсии не превосходила C·logn, где n - показатель степени.
        4. Имеется Х населенных пунктов, перенумерованных от 1 до х (х=10). Некоторые пары пунктов соединены дорогами. Определить, можно ли попасть по этим дорогам из 1-го пункта в х-й. Информация о дорогах задается в виде последовательности пар чисел i и j (i<j). Указывающих, что i-й и j-й пункты соединены дорогой; признак конца этой последовательности - пара нулей.
    • Упражнения:
    •  

Другие записи

10.06.2016. МАССИВЫ
  В этом разделе предлагаются задачи, в которых реализуются алгоритмы работы с массивами (упорядоченными и неупорядоченными). Для решения задач достаточно уметь пользоваться основными конструкциями…
10.06.2016. РАЗМЕЩЕНИЯ. ПЕРЕСТАНОВКИ. СОЧЕТАНИЯ
В этой теме рассматриваются элементы комбинаторики и алгоритмы решения комбинаторных задач. Имеется n различных предметов. Сколько из них можно составить k-расстановок? При этом две расстановки считаются…
10.06.2016. ОБХОД ДЕРЕВА. ПЕРЕБОР С ВОЗВРАТАМИ
    1. Приведенная программа тратит довольно много времени на выполнение проверки есть_сверху (проверка, находится ли верхний ферзь под боем, требует числа действий порядка n). Изменить реализацию…
10.06.2016. СОРТИРОВКИ
 В данной теме мы рассмотрим некоторые методы сортировки массивов порядка n2. Проведет анализ производительности алгоритмов. Покажем, как путем улучшений алгоритма можно добиться некоторого выигрыша…
10.06.2016. УЛУЧШЕННЫЕ МЕТОДЫ СОРТИРОВКИ
  В этой теме продолжаем изучать методы сортировок массивов, которые получены усовершенствованием простых методов.       1. Дан массив целых чисел a[1..n]. Отсортировать его методом…