ратном порядке (первый вошел − последний вышел). При каждом вызове рекурсивной функции локальные данные сохраняются в стеке. После достижения дна рекурсии происходит последовательная выборка данных из стека.

13.2. Условие окончания рекурсивного алгоритма

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

Бесконечная рекурсия может возникать не только при отсутствии условия
							Р
прекращения рекурсивного вызова функции, но и при неполном учете всех
						И
					У
возможных путей движения рекурсии. Например, если факториал рассчитыва-
ется следующим образом:				Г
int fact(int n)
{
	if (n == 0) return 1;
				Б
	else return n*fact(n-1);
}			а
то при вводе числа, меньшего нуля, фун ция будет вызываться бесконечно.
		к
	13.3. Целесообразность использования рекурсии
	е
Рекурсивные алгори мы хорошо подходят для задач, допускающих ре-

курсивное разбиение на элемен арные подзадачи. Однако это не означает, что

для решения таких задач бесспорно использование рекурсивных программ. В
		т
большинстве случаев сп льз вание рекурсии абсолютно неэффективно.
	о
Недостатки рекурс .
1. Большой расход памяти и ресурсов. Это вызвано тем, что при каждом
	и
вызове подпрограммы система оставляет в памяти все локальные данные. Для
обработки сложнойлцепочки рекурсивных вызовов требуется выделение боль-
ших ресурсов системы.
б
2. Часто при использовании рекурсивной программы некоторые вычисле-
ния выполняютсяи	многократно, что существенно снижает быстродействие про-
граммы. Классический пример – вычисление чисел Фибоначчи.
Б3. Часто, несмотря на кажущуюся простоту, программы сложны для по-

нимания и для отладки.

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

77

13.4. Примеры рекурсивных алгоритмов

n

Пример 13.1. Найти сумму Sn ai

i 1

int sumr(int i)

{

if (i < 0) return 0;

else return a[i] + sumr(i-1);

}

	УИ
Пример 13.2. Найти наибольший общий делитель двух чисел. Эйлер об-
наружил следующее соотношение: если В делится на		А нацело, то
НОД(А, В) = А; иначе НОД(А, В) = НОД(B %А, A).		Р

int nodr(int a, int b)

{if( b%a == 0) return a;

				Г
				Б
else return nodr(b%a,a); }
Пример 13.3. Найти max (a1...an). Данную задачу можно разбить на сле-
дующие элементарные	подзадачи:		max (max (a1...an–1), an), и далее
int maxr2(int i)		кажд
max (max (max (a1...an–2), an–1) an),…,			я из которых решается выбором: ес-

ли (x > y), тогда mx=x, иначе mx=y. На последнема уровне окажется тривиальная задача max (a1) mx=a1, после ч го находится max(mx, a2) и т. д.

{					е
	if (i == 0) return a[0];
	else		{	т
	int mx = maxr2(i-1);
				о
	if (a[i] > mx) return a[i];
	}	иelse return mx;
}	л
	б
			Найти сумму элементов одномерного массива. При рекур-
Пр мер 13.4.
сивномиразбиении массив следует делить на две половины.
int sumr(int a[], int i, int j)
Б
{

if (i == j) return a[i]; else

return sumr(a,i,(j+i)/2) + sumr(a,(j+i)/2+1,j);

}

78

Пример 13.5. Вычисление чисел Фибоначчи, которые определяются следующим рекурсивным соотношением: b0 = 0; b1 = 1, bn = bn-1 + bn-2.

int fibr (int n)

{ if (n <= 1) return n;

else return fibr(n-1)+fibr(n-2); }

Программа fibr имеет изящный код, однако работает неэффективно. Каждое обращение к функции приводит к вызову еще двух функций. С увеличением n число вызовов возрастает как 2n–1. Например, при n = 5 дерево вызовов

программы будет иметь вид

Р

И

У

Г

Б

а

Видно, что при выполнении прогр ммы требуется стековая память для

к

хранения данных для 16 (24) функций. Большим недостатком алгоритма являет-

ека

ся могократный вызов функции с одина овыми параметрами.

Так как функция Фибоначчи раст т достаточно быстро, то для больших

значений n рекурсивный

алгоритм

буд т работать медленно или совсем пере-

станет работать из-за переполнения с

. Поэтому практического интереса та-

о

кая рекурсивная программа не предс авляет.

Рассмотренный выше пример показывает, что компактная и красивая

и

программа не всегда эффективна. Для вычисления чисел Фибоначчи удобно

{

л

терационный алгоритм или функцию с одним рекур-

использовать обычный

сивным вызовом:

б

int fibri (int x1, int x2, int n)

и

if (n == 1) return x2;

Б

else if (n == 0) return x1;

else

{

x2 += x1;

x1 = x2-x1;

return fibri(x1, x2, n-1);

}

}

Обращение к функции: fibri(0,1,n);

79

Пример 13.6. Задача о Ханойской башне. Даны три стержня, на один из которых нанизаны n колец. Кольца отличаются размером и расположены меньшее на большем. Необходимо перенести башню на другой стержень. За один раз разрешается переносить только одно кольцо, причем нельзя класть большее кольцо на меньшее. Для промежуточного хранения дисков можно использовать третий стержень.

Решение задачи для одного диска:

− переложить диск с первого стержня на второй стержень.

Решение задачи для двух дисков:

Р

− переложить диск с первого стержня на третий стержень;

− переложить диск с первого стержня на второй стержень;

− переложить диск с третьего стержня на второй стержень;

УИ

дис-

ков:

первый

распола-

гающиеся

дис-

ков

задача решается для n – 1 дисков.

Г

void hanoy(int n, int sterg1, int sterg2, int sterg3)

{

а

if (n > 0) {

Б

hanoy(n-1,sterg1,sterg3,sterg2);

}

к

cout << "perenesty disk s "<<sterg1<<" na "<<sterg2<<endl;

е

hanoy(n-1,sterg3,sterg2,sterg1);

}

т

по

Обращение к функции: hanoy(n,1,2,3);

и

Пример 13.7.

следующему алгоритму: y (xn/2)2 , если n четное;

л

Вычислить

y

xn

y x xn 1, ес и n нечетное.

double st(int n)

и

{ if (n == 0) return 1;

Б

elseб{

if (n%2 == 0)

{

double p = st(n/2);

return p * p;

}

else return x * st(n-1);

}

}

80