 |
 |
 |
РекурсияРекурсивным называется объект, частично состоящий или определяемый с помощью самого себя. Рекурсивные определения представляют собой мощный аппарат в математике. Например: 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;
Когда-то в Ханое стоял храм и рядом с ним три башни (столба). На первую башню надеты 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. Написать рекурсивную функцию вычисления чисел Фибоначчи, определяемых соотношением 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-й пункты соединены дорогой; признак конца этой последовательности - пара нулей. |
|
|
|
