int fact(int n)

{

int answer;

answer = 1;

for(int t=1; t<=n; t++) answer = answer*(t);

return(answer);

}

Действие нерекурсивного варианта fact() вполне очевидно. Он использует цикл, начинающийся с 1, в котором каждое следующее число умножается на последовательно увеличивающееся пpоизведение.

Действие рекурсивной функции factr() несколько сложнее. При вызове factr() с аргументом 1 функция возвращает 1; в противном случае она возвращает произведение factr(n-l)*n. Для вычисления этого выражения factr() вызывается с аргументом (n-1). Это происходит до тех пор, пока n не станет равным 1, и вызов функции приведет к возврату из нее. Например, когда вычисляется факториал 2, первый вызов factr() породит второй вызов с аргументом 1. Этот вызов вернет 1, которая умножится на 2 (первоначальное значение n). Переменная answer будет тогда равна 2. Вы можете ради любопытства включить в factr() предложения cout, которые покажут, на каком уровне находится вызов и каков промежуточный результат (переменная answer).

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

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

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

Составляя рекурсивную функцию, вы должны где-то в ней включить условное предложение, например, if, чтобы заставить функцию осуществить возврат без выполнения рекурсивного вызова. Если вы пренебрежете таким условным предложением, то вызвав однажды эту функцию, вы никогда из нее не вернетесь. Это, довольно распространенная ошибка. Разрабатывая программы с рекурсивными функциями, не стесняйтесь включать в них предложения cout, которые позволят вам наблюдать, что происходит в программе, и аварийно завершить выполнение, если вы обнаруживаете ошибку.

Ниже приведен другой пример рекурсивной функции, названной reverse(). Она выводит на экран строку задом наперед.

// demoRecurcia2.cpp: Defines the entry point for the console application.

//

// Вывод строки задом наперед посредством рекурсии.

#include "stdafx.h"

#include <iostream>

#include <conio.h>

using namespace std;

void reverse(char *s);

int main()

{

char str[] = "this is a test";

reverse (str);

getch();

return 0;

}

// Вывод строки задом наперед,

void reverse(char *s)

{

if(*s) reverse(s+1);

else return;

cout << *s;

}

Результат программы:

Функция reverse() прежде всего проверяет, не передан ли ей указатель на завершающий ноль строки. Если нет, то reverse() вызывает себя с передачей в качестве аргумента указателя на следующий символ строки. Когда наконец будет найден завершающий ноль, вызовы начинают "раскручиваться", и символы появляются на экране в обратном порядке.

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

Контрольные вопросы

1. Что такое функция? Как она объявляется?

2. Какой результат может возвращать функция?

3. Как функции передаются аргументы? Что такое передача аргумента по значению и по ссылке? Чем эти способы отличаются и как реа­лизуются?

4. Каким образом функции в качестве значения передаются указатели?

5. Каким образом функции в качестве аргумента передаются массивы?

6. Что такое рекурсия, и в каких случаях она используется?

7. Что такое перегрузка функции? В каких случаях применяется пере­грузка?

8. Что такое шаблоны функции? В каких случаях применяется шаблон функции?

9. Дан фрагмент программы:

int f(char &с, int *i);

//...

char ch = 'x';

int i = 10;

Покажите, как вызвать f() для операций над переменными ch и i.

10. Создайте void -функцию с именем round(), которая округляет значение своего аргумента типа double до ближайшего целого значения. Пусть round() использует параметр-ссылку и возвращает округленный результат через этот параметр. Продемонстрируйте вызов round() в программе. Для решения этой задачи вам понадобится функция modf() из стандартной библиотеки. Она имеет такой прототип:

double modf(double num, double * i);

Функция modf() разлагает num на целую и дробную части. Она воз­вращает дробную часть и помещает целую часть в переменную, на которую указывает i. Функция требует заголовок <cmath>.