C++: базовый курс

Классическим примером рекурсии является вычисление факториала числа с помощью функции factr(). Факториал числа N представляет собой произведение всех целых чисел от 1 до N. Например, факториал числа 3 равен 1x2x3, или 6. Рекурсивный способ вычисления факториала числа демонстрируется в следующей программе. Для сравнения сюда же включен и его нерекурсивный (итеративный) эквивалент.

#include

using namespace std;

int factr(int n);

int fact(int n);

int main()

{

　// Использование рекурсивной версии.

　cout << "Факториал числа 4 равен " << factr(4);

　cout << '\n';

　// Использование итеративной версии.

　cout << "Факториал числа 4 равен " << fact(4);

　cout << '\n';

　return 0;

}

// Рекурсивная версия.

int factr(int n)

{

　int answer;

　if(n==1) return(1);

　answer = factr(n-1)*n;

　return(answer);

}

// Итеративная версия.

int fact(int n)

{

　int t, answer;

　answer =1;

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

　return (answer);

}

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

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

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

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

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

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