Рекурсивным называется объект, частично состоящий или определяемый с помощью самого себя.
Рекурсивные
определения представляют собой мощный аппарат в математике.
Например:
1) Натуральные числа:Мощность рекурсивного определения заключается в том, что оно позволяет с помощью конечного высказывания определить бесконечное множество объектов. Аналогично, с помощью конечной рекурсивной программы можно описать бесконечное вычисление, причем программа не будет содержать явных повторений. В общем виде рекурсивную программу Р можно выразить как некоторую композицию Р из множества операторов С (не содержащих Р) и самой Р: Р=Р[С,Р].а) 0 есть натуральное число,2) Деревья:
б) число, следующее за натуральным, есть натуральное число.а) 0 есть дерево (╚пустое дерево╩),3) Функция n! ╚факториал╩ (для неотрицательных целых чисел):
б) если А1 и А2 - деревья, то построение, содержащее вершину с двумя ниже расположенными деревьями, опять дерево.а) 0!=1,
б) n>0: n!=n·(n-1)!
Для выражения рекурсивных программ удобнее пользоваться процедурами или функциями. Если некоторая процедура Р содержит явную ссылку на саму себя, то её называют прямо рекурсивной, если же Р ссылается на другую процедуру В, содержащую ссылку на Р, то Р называют косвенно рекурсивной.
Как правило с процедурой связывают множество локальных переменных, которые определены только в этой процедуре. При каждой рекурсивной активации процедуры порождается новое множество локальных, связанных переменных. Хотя они имеют те же самые имена, что и соответствующие элементы локального множества предыдущего ╚поколения╩ этой процедуры, их значения отличны от последних, а любые конфликты по именам разрешаются с помощью правил, определяющих область действия идентификаторов: идентификатор всегда относится к самому последнему порожденному множеству переменных.
Рекурсивные процедуры могут приводить к не заканчивающимся вычислениям. Очевидно основное требование, чтобы рекурсивное обращение к Р управлялось некоторым условием Х, которое в какой-то момент становится ложным.
Р== if X then P[C,P]Основной способ доказательства конечности некоторого повторяющегося процесса:
1. Определяется функция f(x), такая, что из f(x)<=0 следует истинность условия окончания цикла,Аналогично доказывается и окончание рекурсии - показывается, что Р уменьшает f(x), такую, что из f(x)<=0 следует истинность В.
2. Доказывается, что при каждом прохождении цикла f(x) уменьшается.
Задача1.
Написать функцию вычисления факториала целого положительного числа n.
Для решения
будем использовать равенства 0!=1, n!=n·(n-1)!
Function fakt (n: integer): integer;Задача 2. Написать рекурсивную функцию вычисления xn , где n>=0.
begin
if n=0 then fakt:=1 else fakt:= n*fakt (n-1);
end;
Function pow (x:real; n: byte):real;Задача 3. Ханойские башни.
begin
if n=0 then pow:=1 else pow:=x*pow(x,n-1);
end;
1) можно перемещать только по одному диску;Предположим, с первого столба А надо перенести на третий С n дисков. Диски пронумерованы в порядке возрастания их диаметров. Предположим, что мы умеем переносить n-1 дисков. В этом случае n дисков перенесем посредством следующих шагов:
2) больший диск нельзя класть на меньший;
3) снятый диск нельзя отложить, его необходимо сразу надеть на другой столб.
1) верхние n-1 дисков перенесем с первого на второй, пользуясь свободным третьим столбом;Аналогичным образом можно перенести n-1,n-2 и т.д. дисков. Когда n=1, перенос осуществляется непосредственно с первого столба на третий.
2) последний диск наденем на третий столб;
3) n-1 дисков перенесем на третий, пользуясь свободным первым столбом.
VarЗадача 4. Вывести все сочетания из n по k. (см. тему 3)
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.
typeЗадача 5. Перечислить все способы расстановки n ферзей на шахматной доске n x n, при которых они не бьют друг друга. (см. тему 4)
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.
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-й пункты соединены дорогой; признак конца этой последовательности - пара нулей.