ОБЪЕКТНО-ОРИЕНТИРОВАННОЕ ПРОГРАММИРОВАНИЕ В C++ (4-Е ИЗДАНИЕ) (часть 5) онлайн
Рекурсия
Существование функций делает возможным использование такого средства про- граммирования, как рекурсия. Рекурсия позволяет функции вызывать саму себя на выполнение. Это может показаться несколько неправдоподобным, и на самом деле зачастую обращение функции к самой себе вызывает ошибку, но при пра- вильном использовании механизм рекурсии может оказаться очень мощным ин- струментом в руках программиста.
Понять суть рекурсии проще из конкретного примера, чем из долгих про- странных объяснений, поэтому обратимся к программе FACTOR, которую мы соз- дали в главе 3 «Циклы и ветвления». В этой программе использовался цикл for для подсчета факториала числа (если вы не помните, что представляет собой факториал числа, прочитайте пояснения к примеру). Наша следующая програм- ма, FACTOR2, вместо цикла for использует рекурсию.
// factor2.cpp
// подсчет факториала числа с помощью рекурсии #include <iostream> using namespace std;
unsigned long factfunc(unsigned long); // прототип
int main() {
int n; // число, вводимое пользователем
unsigned long fact; // факториал этого числа
cout << "Введите целое число :"; cin >> n;
fact = factfunc(n);
cout << "Факториал числа " << n << "равен " << fact << endl; return 0;
}
//---------------- функция factfunc()--------
// рекурсивно подсчитывает факториал числа
unsigned long factfunc(unsigned long n) {
if(n > 1)
return n * factfunc(n-1); // вызов самой себя
else return 1;
}
Результат работы этой программы такой же, как и у программы FACTOR из главы 3.
Функция main() программы FACTOR2 не содержит ничего необычного: в ней производится вызов функции factfunc(), где в качестве аргумента используется значение, введенное пользователем. Функция factfunc() возвращает функции main() вычисленное значение факториала.
Совсем по-другому обстоит дело с содержимым функции factfunc(). В случае, если параметр n оказывается больше 1, происходит вызов функцией factfunc() самой себя, при этом используется значение аргумента на единицу меньшее, чем текущее значение параметра. Если функция main() вызвала функцию factfunc() с аргументом, равным 5, то сначала функция factfunc() вызовет себя с аргумен- том, равным 4, затем этот вызов обратится к функции factfunc() с аргументом, равным 3, и т. д. Обратите внимание на то, что каждый экземпляр функции хра- нит свое значение параметра n во время выполнения рекурсивного вызова.
После того как функция factfunc() вызовет себя четырежды, пятый вызов бу- дет производиться с аргументом, равным 1. Функция узнает об этом с помощью оператора if и, вместо рекурсивного вызова, возвратит четвертому вызову значе- ние, равное 1. Четвертый вызов хранит значение параметра, равное 2, поэтому, произведя умножение параметра на значение, возвращенное пятым вызовом, он получит число 2, которое будет возвращено третьему вызову. Третий вызов хра-
нит значение параметра, равное 3, поэтому второму вызову будет возвращено значение 3*2 = 6. Второй вызов хранит значение параметра, равное 4, поэтому, умножив 4 на 6, возвратит первому вызову значение, равное 24. Наконец, пер- вый вызов умножит 24 на значение параметра, равное 5, и вернет окончатель- ный результат, равный 120, в функцию main().
Таким образом, в этом примере мы имеем пять рекурсивных вызовов с пятью возвращаемыми значениями. Сведем процесс выполнения рекурсии в таблицу:
|
Версия |
Действие |
Аргумент или возвращаемое значение |
|
1 |
Вызов |
5 |
|
2 |
Вызов |
4 |
|
3 |
Вызов |
3 |
|
4 |
Вызов |
2 |
|
5 |
Вызов |
1 |
|
5 |
Возврат значения |
1 |
|
4 |
Возврат значения |
2 |
|
3 |
Возврат значения |
6 |
|
2 |
Возврат значения |
24 |
|
1 |
Возврат значения |
120 |
Каждая рекурсивная функция должна включать в себя условие окончания рекурсии. В противном случае рекурсия будет происходить бесконечно, что при- ведет к аварийному завершению программы. Ветвление if в функции factfunc() играет роль условия, прекращающего рекурсию, как только параметр достигнет значения, равного 1.
Будут ли все рекурсивные вызовы функции храниться в памяти? Это не со- всем так. В памяти будут находиться значения параметров для каждого из вызо- вов, однако тело функции будет присутствовать в памяти в единственном экзем- пляре. Но, даже несмотря на это, программа, использующая рекурсии с большим числом вложенных вызовов, может исчерпать все ресурсы оперативной памяти, что повлечет за собой сбой в работе операционной системы.
12 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39