ТЕМА 2. ПРОГРАММИРОВАНИЕ С ИСПОЛЬЗОВАНИЕМ РЕКУРСИИ

Цель лабораторной работы: изучить способы программирования алго- ритмов с использованием рекурсии.

2.1. Понятие рекурсии	Р
	И

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

ется сама к себе. Классический пример программирования вычисления n-го члена
(n>0) рекуррентной последовательности xn=ϕ (xn-1) при x0=a:
			Г
double XR(int n)		Б		У
{
if (n==0) return a;		// Условие окончания рекурсии
		а
else return ϕ(XR(n-1)); // Рекурсивное обращение к функции
}	внюедовательнопосл
ции алгоритма к нижнему			, до тех пор пока наконец не
Здесь ϕ - функция, определяющая за он р		уррентности.
При выполнении правильно организованнойк			рекурсивной подпрограммы
	т
осуществляется многократный п р ход от некоторого текущего уровня организа-

будет получено тривиальн е решение задачи (в вышеприведенном примере n=0). Рекурсивная форма записи алгоритма обычно выглядит изящнее итераци-

ются в тех случаях, когда в структуре решаемой задачи рекурсия присутствует явноБ.

онной и дает более компактный текст программы, но при выполнении, как прави-
			уро
ло, медленнее и может вызвать переполнение программного стека. Это вызвано
тем, что при актива			каждого экземпляра вложенной подпрограммы порожда-
		ции
ется новое множество			окальных переменных и, кроме того, запоминается теку-
щее состоя	ленийвычис			. Поэтому рекурсивные алгоритмы обычно использу-
б
ние

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

PDF created with pdfFactory Pro trial version www.pdffactory.com