Long fact ( long n )

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

Обмен данными между функциями

If (prostoe(a))

printf("Da!");

else printf("Net!");

getch();

}

int prostoe (long int a) // реализация функции

{ if (a<=1) return 0;

for (long int i=2;i<=a/2; i++)

if (a%i==0) return 0;

return 1;

}

Функции могут обмениваться данными тремя способами:

1. Используя глобальные переменные.

2. Передавая копии данных.

3. Передавая адреса, по которым записаны данные.

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

Если же внутри функций будут объявлены локальные переменные с таким же именем, что и глобальные, то приоритет отдается локальным.

Использование глобальных переменных внутри функций не рекомендуется. Следует все данные передавать, используя список параметров.

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

Для того, чтобы из функции можно было возвратить несколько значений, используются указатели (функция меняет местами значения переменных A и B):

void Swap (int &A; int &B) {int C=A; A=B; B=C;};

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

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

С помощью рекурсии определяются многие понятия. Например, понятие натурального числа можно определить так:

a) 1 есть натуральное число;

b) число, следующее за натуральным, также есть натуральное число.

Известно, что факториал числа n равен произведению всех натуральных чисел от 1 до n.

Таким же образом можно определить функцию факториал:

В этом примере функция определяется через саму себя, т.е. рекурсивно.

a) 0! = 1;

b) n! = (n-1)! * n.

Приведем реализацию функции:

{ if (n==0) return 1;

return n*fact(n-1);

}

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

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

Рассмотрим более подробно процессы, происходящие в стеке локальных переменных, при вызове рекурсивных функций.

Известно, что при вызове функции в стеке создаются локальные переменные, связанные со списком передаваемых параметров и с именем функции.

	fact		Уровень	3*fact(2)
	n
	fact		Уровень	2*fact(1)
	n
	fact		Уровень	1*fact(0)
	n
	fact		Уровень
	n			рекурсивный подъем рекурсивный спуск

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

В качестве примера приведем еще две рекурсивные функции:

// -------------------------------------------------

// Функция kcc возвращает колич.цифр числа n.

int kcc(long n)

{if (n<10) return 1; return kcc(n/10)+1;}

// -------------------------------------------------

// Функция scc возвращает сумму цифр числа n.

int scc(long n)

{if (n<10) return 1; return scc(n/10)+n%10;}

Дата добавления: 2014-11-29