43

7. Рекурсивные алгоритмы

Вид занятия – лабораторная работа Цель – исследование и сравнительная оценка рекурсивных и итерационных алгоритмов

Продолжительность – 4 часа

Рекурсия – фундаментальное понятие в математике и компьютерных науках. В языках программирования рекурсивной программой называется программа, которая обращается сама к себе (подобно тому, как в математике рекурсивная функция определяется через понятия самой этой функции).

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

Как следствие, рекурсивная программа должна иметь как минимум два пути выполнения, один из которых предполагает рекурсивный вызов (случай «сложных» данных), а второй – без рекурсивного вызова (случай «простых» данных).

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

Если некоторая процедура Р содержит явную ссылку на саму себя, то ее называют прямо рекурсивной. Если же Р ссылается на другую процедуру Q, содержащую вызов Р (возможно, не напрямую, а через цепочку вызовов других процедур), то Р называют косвенно рекурсивной. Поэтому по тексту программы рекурсивность не всегда явно определима.

В ряде случаев рекурсивную подпрограмму можно построить непосредственно из формального математического описания задачи.

Факториал

{			Function	Fact(n:byte):longint;
			begin
	n! = n * (n-1)!, при n>0		if n=0	Fact:=1
	1, n=0		then
			else	Fact:=n*Fact(n-1)
			end;
		Числа Фибоначчи
{			Function	Fib(n:byte):longint;
			begin
	Фn = Фn-1 + Фn-2, при n>1		if n <= 1
	Ф0 = 1, Ф1 = 1		then	Fib:=1
			else	Fib:= Fib(n-1)+ Fib(n-2)
			end;

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

К примеру, вычисление факториала и чисел Фибоначчи можно реализовать без рекурсии:

Факториал

44

Function Fact(n:byte):longint;	Function	Fact(n:byte):longint;
var F, i : byte;	begin
begin	if n=0	Fact:=1
F:=1;	then
for i:=1 to n do F:=F*i;	else	Fact:=n*Fact(n-1)
Fact:=F	end;
end;

При относительной простоте написания, у рекурсивных подпрограмм часто встречается существенный недостаток – неэффективность. Так, сравнивая скорость вычисления чисел Фибоначчи с помощью итеративной и рекурсивной функции можно заметить, что итеративная функция выполняется почти «мгновенно», не зависимо от значения n. При использовании же рекурсивной функции уже при n=40 заметна задержка при вычислении, а при больших n результат появляется весьма не скоро.

	Числа Фибоначчи
Function F(n:byte):longint;		Function F(n:byte):longint;
var F0, F1, F2 : longint; i : byte;		begin
begin		if n <= 1
F0:=1; F1:=1;		then F:=1
for i:=2 to n do		else F:= F(n-1)+F(n-2)
begin		end;
F2:=F1+F0; F0:=F1; F1:=F2;
end;
F:=F1
end;

Сравнение рекурсии и итерации

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

чисто итеративную. Напомним, что это также следует из тезиса об эквивалентности понятий рекурсивности и вычислимости.

Операторный и рекурсивный методы программирования имеют свои достоинства и недостатки.

К достоинствам операторного метода следует отнести его ориентацию на архитектуру вычислительных машин, привычность способа описания любых алгоритмов в виде последовательности

действий, существование большого количества уже описанных и проверенных алгоритмов.

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

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

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

переменных, в стеке сохраняется текущее состояние вычислений, т.е. адрес той команды, на которую нужно вернуться, чтобы закончить вычисления, прерванные вызовом подпрограммы. Очевидно, что при большой глубине рекурсии может возникнуть проблема нехватки памяти (переполнение стека рекурсивных вызовов). В итеративных алгоритмах такие проблемы, как правило, не возникают.

45

Задание

1.Описать рекурсивные функции Fact(N) и Fact2(N) вещественного типа, вычисляющие значения факториала N! и двойного факториала N!! соответственно (N > 0 — параметр целого типа). С помощью этих функций вычислить факториалы и двойные факториалы пяти данных чисел.

2.Описать рекурсивную функцию PowerN(x,n) вещественного типа, находящую значение n-й

степени числа x по формуле: x0 = 1, xn = x·xn–1 при n > 0, xn = 1 / x–n при n < 0 (x >= 0 — веще-

ственное число, n — целое). С помощью этой функции найти значения XN при 5 различных значениях N для данного X.

3.Описать рекурсивную функцию SqrtK(x,k,n) вещественного типа, находящую приближенное значение корня k-й степени из числа x по формуле: y(0) = 1, y(n+1) = y(n) – (y(n) – x / y(n)k–1) / k,

где y(n) обозначает SqrtK(x,k,n) (x — вещественный параметр, k и n — целые; x > 0, k > 1, n > 0).

Спомощью этой функции найти приближенные значения корня K-й степени из X при 6 различных значениях N для данных X и K.

4.Описать рекурсивную функцию C(m,n) целого типа, находящую число сочетаний из n элемен-

тов по m, используя формулу: C(0,n) = C(n,n) = 1, C(m,n) = C(m,n–1) + C(m–1,n–1) при 0 < m < n (m и n — целые параметры; n > 0, 0 <= m <= n). Дано число N и пять различных значений M. Вывести числа C(M,N) вместе с количеством рекурсивных вызовов функции C, потребовавшихся для их нахождения.

5.Описать рекурсивную функцию NOD(A,B) целого типа, находящую наибольший общий делитель двух натуральных чисел A и B, используя алгоритм Евклида: NOD(A,B) = NOD(B mod A,A), если A <> 0; NOD(0,B) = B. С помощью этой функции найти наибольшие общие делители пар A и B, A и C, A и D, если даны числа A, B, C, D.

6.Описать рекурсивную функцию MinRec(A,N)1|MaxRec(A,N)2 вещественного типа, которая находит минимальный1|максимальный2 элемент вещественного массива A размера N, не используя оператор цикла. С помощью функции MinRec1|MaxRec2 найти минимальные1|максимальные2 элементы массивов A, B, C размера NA, NB, NC соответственно.

7.Описать рекурсивную функцию Digits(S) целого типа, находящую количество цифр в строке S без использования оператора цикла. С помощью этой функции найти количество цифр в данных пяти строках.

8.Описать рекурсивную функцию Simm(S) логического типа, проверяющую, является ли симметричной строка S, без использования оператора цикла. С помощью этой функции проверить данные пяти строк.