Deprecated: mysql_connect(): The mysql extension is deprecated and will be removed in the future: use mysqli or PDO instead in /home/studb20/public_html/index.php on line 4
 Рекурсия - ОБЪЕКТНО-ОРИЕНТИРОВАННОЕ ПРОГРАММИРОВАНИЕ В C++ (4-Е ИЗДАНИЕ) (часть 5) онлайн - Studbook

ОБЪЕКТНО-ОРИЕНТИРОВАННОЕ ПРОГРАММИРОВАНИЕ В 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.

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

 

26