close

Вход

Забыли?

вход по аккаунту

?

Программирование рекурсий разных видов.

код для вставкиСкачать
УДК 681.3
В.П. Гладков
Пермский государственный технический университет
ПРОГРАММИРОВАНИЕ РЕКУРСИЙ РАЗНЫХ ВИДОВ
Рассматриваются вопросы программирования рекурсивных алгоритмов. Устанавливаются правила их построения.
Рекурсия – это такой способ организации вспомогательного алгоритма (подпрограммы: процедуры или функции), при котором он
обращается сам к себе. Вообще, рекурсивным определением объекта
называется определение, которое содержит ссылку на определяемый
объект. Рекурсивно определенный объект называется рекурсивным.
В рекурсивном определении должно присутствовать ограничение,
граничное условие, при выходе на которое дальнейшая инициация рекурсивных обращений прекращается. Для реализации рекурсии используется стек.
Типичная конструкция рекурсивной процедуры имеет вид:
procedure REC(t : integer);
begin {действия на входе в рекурсию. "Рекурсивный спуск"}
if
{граничное
условие}
then
REC(t+1);
{действия на выходе из рекурсии.
"Рекурсивный подъем"}
end;
Классическим примером рекурсивного алгоритма является вычисление факториала в соответствии с определением:
1, при n = 0 или n = 1,
n!= 
 (n − 1)!⋅n, при n > 1.
Получаем следующую рекурсивную функцию:
function fact1(n : longint) : longint;
begin if n = 1 then fact1 := 1
else fact(n–1)*n;
end;
87
Операция умножения, используемая в функции, является коммутативной и ассоциативной, поэтому при вычислении, например 5!
(вызов fact1(5)), имеем:
5! = 4!*5
= (3! * 4)*5
= ((2! * 3)*4)*5
= (((1! * 2)*3)*4)*5
= (((1 * 2)*3)*4)*5
(*)
= ((3 * 3)*4)*5
= (6 * 4)*5
= 24 * 5
= 120.
Из приведенных преобразований видно, что вычисления проводятся на рекурсивном подъеме, а рекурсивный спуск используется
для отсчета нужного количества вызовов функции. Параметр n играет
роль счетчика. Если в строке, отмеченной звездочкой, воспользоваться свойством ассоциативности, то получим формулу нахождения факториала как произведения натуральных чисел от 1 до 5, что позволит
легко перейти к итерационному алгоритму.
Для перехода к итерационному циклу заметим, что можно сохранять значения переменной n (однако в данном простом случае это
необязательно) для того, чтобы во время подъема можно было бы использовать их для вычислений. С этой целью используется стек, а переменная n играет роль счетчика. Получаем следующую программу:
var st : array[1..100]of integer; {моделирует
стек}
yk {указатель вершины стека}, n{исходное
число}, p{факториал} : integer;
begin
n := 5;
{моделируем рекурсивный спуск}
yk := 0;
while n <> 1 do
begin inc(yk); st[yk] := n; dec(n); end;
{моделируем рекурсивный подъем и вычисления}
p:=1;
while yk>0 do
88
begin p:=p*st[yk];
dec(yk);
end;
write(p);
Запишем рекурсивную функцию вычисления факториала на рекурсивном спуске:
function fact2(n, s : longint) : longint;
begin if n = 1 then fact2 := s
else begin s := s*n;
fact2 := fact2(n-1,s);
end;
или равносильный вариант:
function fact2(n, s : longint) : longint;
begin if n = 1 then fact2 := s
else fact2 := fact2(n-1, s*n);
end;
Вызов fact2 (5, 1) приводит к вычислениям:
fact2(5,1) = fact2(4, 1*5)
= fact2(3, 1*5*4)
= fact2(2, 1*5*4*3)
= fact2(1, 1*5*4*3*2)
= fact2 = 120
= 120
= 120
= 120
= 120.
Из приведенных функций видно, что если требуется передать
глубже по рекурсии значения, полученные на рекурсивном спуске, то
необходимо создать специальный параметр.
Рассмотренные варианты легко приводятся к равносильной
итерационной программе:
s:=1;
for i := 1 to n do s := s*i;
Рассмотрим задачу вычисления суммы элементов арифметической прогрессии. Арифметическая прогрессия определяется тремя параметрами: первым элементом (a1 = a), разностью между соседними элементами (d) и количеством членов прогрессии (n). Очередной элемент
89
прогрессии вычисляется из предыдущего прибавлением разности –
a := a + d.
Его можно вычислить и по формуле a n = a1 + (n − 1) ⋅ d .
Для вычисления суммы можно воспользоваться выражением
(пример для n = 4): S4 = a1 + a2 + a3 + a4 = a + a + d + a + 2d + a + 3d =
(((0 + a) + a + d) + a + 2d) + a + 3d = S3 + a + 3d = (S2 + a + 2d) + a +3d =
((S1 + a + d) + a + 2d) + a + 3d = (((S0 + a) + a + d) + a + 2d) + a + 3d.
Полученная запись позволяет написать рекурсивную программу, в которой рекурсия используется для отсчета вычислений (равносильна циклу), а сами вычисления выполняются на рекурсивном
подъеме,
function sa1(n : integer) : integer;
begin if n > 0
then sa1 := a + (n–1)*d + sa1(n–1)
else sa1 := 0;
end;
Приведенная рекурсивная программа эквивалентна следующей
итерационной программе:
s := 0;
for i := 1 to n do s := s + a+(i–1)*d;
Другой подход к построению формулы позволяет получить рекурсивную программу, в которой члены ряда вычисляются на рекурсивном спуске, а сумма считается на рекурсивном подъеме. Эта
функция имеет два параметра: первый – количество слагаемых в сумме, второй – само слагаемое.
S(4, a) = a+S(3, a+d) = a+(a+d+S(2, a+2d)) =
a+(a+d+(a+2d+S(1, a+3d))) =
a+(a+d+(a+2d+(a+3d+S(0, a+4d)))) =
a+(a+d+(a+2d+(0+a+3d))) =
a+a+d+a+2d+a+3d.
Программируя по этой формуле, получаем программу:
function sa2(n, a : integer) : integer;
begin if n > 0
then sa2 := a + sa2(n–1, a+d)
else sa2 := 0;
end;
90
Приведенная рекурсивная программа эквивалентна следующей
итерационной программе:
s := 0; a := a – d;
for i := 1 to n do begin a := a + d; s := s +
a; end;
Наконец, можно предложить программу, которая вычисляет результат только во время рекурсивного спуска. В этом случае рекурсивная программа имеет три параметра: первый предназначен для отсчета количества вычислений, второй вычисляет очередное слагаемое,
а третий – сумму.
S(4, a, 0) = S(3, a + d, 0 + a) = S(2, a + 2d, 0 + a + a + d) =
=S(1, a + 3d, 0 + a + a + d + a + 2d) = S(0, a + 4d, 0 + a + a + d + a + 2d +
+a + 3d) = =0 + a + a + d + a + 2d + a + 3d.
Эта формула приводит к программе:
function sa3(n, a, s : integer) : integer;
begin if n > 0
then begin s := s + a;
a := a + d;
sa3 := sa3(n–1, a, s)
end
else sa3 := s;
end;
Программа может быть переписана:
function sa31(n, a, s : integer) : integer;
begin if n > 0
then sa31 := sa31(n–1, a+d, s+a)
else sa31 := s;
end;
Приведенные рекурсивные программы эквивалентны следующей итерационной программе:
s := 0;
for i := 1 to n do begin s := s + a; a := a +
d; end;
Обобщим способы организации рекурсии на примере решения
задачи. Вычислить s =
n + n −1+ n − 2 +K + 1 .
91
Вначале построим итерационный процесс. Заметим, что под
каждым корнем значение изменяется, возрастая от 1 до n, поэтому его
можно обозначить переменной i.
Начнем построение итерационного процесса от самого вложенного корня (просматриваем выражение справа налево).
При n = 1 S1 = 1 . При n = 2 S 2 = 2 + 1 или, подставляя предыдущее выражение, S 2 = 2 + S1 . При n = 3 аналогично имеем
S 3 = 3 + 2 + 1 = 3 + S 2 . Обобщая, приходим к рекуррентной
формуле S i = i + S i −1 . Из формулы видно, что переменная i играет
двойную роль: 1) счетчик вычислений – об этом свидетельствует ее
вхождение в формулу в качестве индекса; 2) слагаемое в подкоренном
выражении. Об этом нужно помнить при программировании.
На основании установленного получаем следующий итерационный алгоритм:
function iter(n : integer) : real;
var i : integer; s : real;
begin s := 0;
for i := 1 to n do s := sqrt(i + s);
iter := s;
end;
Теперь установим рекурсию с вычислением на рекурсивном
подъеме. Рассуждая аналогично предыдущему, только рассматривая
исходное выражение слева направо, получаем рекуррентную формулу
S n = n + S n −1 или S (n) = n + S (n − 1) и S (1) = 1 . На основе полу-
ченной формулы строим рекурсию.
function f1(n : integer) : real;
begin if n = 1 then f1 := sqrt(1)
else f1 := sqrt(n + f1(n – 1))
end;
Для получения рекурсии, работающей на рекурсивном спуске,
необходимо организовать рекурсивное изменение счетчика.
function f2(n ,i : integer; s : real) : real;
begin if n = 1 then f2 := sqrt(i + s)
else f2 := f2(n – 1, i + 1, sqrt(i + s))
end;
92
Здесь n – рекурсивный счетчик, i – слагаемое, s – вычисляемая
величина.
Вычисление на рекурсивном спуске и подъеме может быть осуществлено следующим образом:
function f3(n : integer; i : integer) : real;
begin if n = 1 then f3 := sqrt(1)
else f3 := sqrt(i + f3(n – 1, i – 1))
end;
Таким образом, для работы рекурсии на спуске достаточно поместить вычисляемые значения в параметры рекурсивной функции.
Для работы рекурсии на подъеме достаточно записать вычисляемое
значение явно и заставить рекурсию отсчитывать количество повторений. Для работы рекурсии и на спуске, и на подъеме достаточно использовать параметр рекурсивной функции в выражении, вычисляющем нужное значение.
Установленные закономерности облегчат программирование
рекурсии и уменьшат количество ошибок в программе.
Получено 08.07.2009
93
Документ
Категория
Без категории
Просмотров
6
Размер файла
184 Кб
Теги
видов, рекурсия, программирование, разные
1/--страниц
Пожаловаться на содержимое документа