и рекурсивная часть. Согласно определению, факториал 6 вычисляется следующим
образом:
6! = 6*5! = 6*5*4! = 6*5*4*3! = 6*5*4*3*2! = 6*5*4*3*2*1! = 6*5*4*3*2*1*1 = 720
2. Простой пример рекурсии
Рассмотрим рекурсивную функцию "print_backwards()" из программы 2.1. Эта
функция предназначена для ввода с клавиатуры последовательности символов. Для
прекращения ввода пользователь должен напечатать специальный символ (точку).
После этого функция печатает введенные символы в обратном порядке.
#include<iostream.h>
void print_backwards();
int main()
{
print_backwards();
cout << "\n";
return 0;
}
void print_backwards()
{
char character;
cout << "Введите символ (или '.' для завершения ввода): ";
cin >> character;
if ( character != '.' )
{
90
print_backwards();
cout << character;
}
}
Программа 2.1.
Программа 2.1 печатает на экране подобные сообщения:
Введите символ (или '.' для завершения ввода): H
Введите символ (или '.' для завершения ввода): i
Введите символ (или '.' для завершения ввода): .
iH
Порядок выполнения функции "print_backwards()" подробно описан в сле-
дующем параграфе. Пока обратите внимание на то, что вызов "print_backwards()" (в
ее собственном определении) находится внутри оператора "if".
В определениях рекурсивных функций обычно есть некоторый оператор ветв-
ления, у которого, как минимум, одна нерекурсивная ветвь, реализующая "базовое
утверждение" определения функции. Если такой ветви нет, то функция будет вызы-
вать себя бесконечно (в действительности, до тех пор, пока не будет занята вся па-
мять).
В программе 2.1 базовое утверждение реализовано неявно –это возврат из
функции, если был введен символ "." (точка).
3. Как выполняется рекурсивный вызов
Порядок выполнения программы 2.1 легко понять с помощью нескольких схем.
Главная функция начинается с вызова "print_backwards()". Для выполнения вы-
зова функции в памяти компьютера выделяется некоторое количество памяти (необ-
ходимое для запоминания адреса возврата, для создания копий параметров по значе-
нию и для передачи параметров-указателей). Свободная область памяти в момент
первого вызова "print_backwards()" на рис. 1 изображена в виде пустого прямо-
угольника. Внутри прямоугольника показано содержимое экрана в соответствующие
моменты времени (на схемах считается, что направление "сверху-вниз" соответствует
увеличению времени, прошедшему с момента запуска программы).
Рис. 1.. Свободная область памяти перед
первым вызовом "print_backwards()"
Рис. 2. Свободная область памяти перед
вторым вызовом "print_backwards()".
Выполнение функции "print_backwards()" начинается со ввода символа, а за-
тем происходит второй вызов "print_backwards()" (в этот момент программа еще не
91
начинала обратную печать символов). Для второго вызова также выделяется некото-
рое количество памяти, поэтому объем свободной памяти уменьшается (рис. 2).
Далее процесс повторяется, но, допустим, при третьем вызове
"print_backwards()" пользователь ввел завершающий символ (точку). Поэтому после
третьего вызова происходит возврат в вызывающую функцию (т.е. во второй экземп-
ляр "print_backwards()"), см. рис. 3.
Рис. 3. Возврат из 3-го экземпляра функции
"print_backwards()" во второй.
Рис. 4.. Завершение выполнения программы.
Второй экземпляр "print_backwards()" завершается, но перед завершением вы-
водит на экран символ "i". В свою очередь, первый экземпляр функции перед завер-
шением работы напечатает на экране символ "H" (рис. 4).
Для организации вызовов функций и создания автоматических переменных в
программах на Си++ отводится специальная область памяти –стек. Память, необхо-
димая для очередного вызова функции, выделяется в верхней части стека (в старших
адресах). При завершении функции размер стека уменьшается на соответствующую
величину. Изменение состояния программного стека для рассмотренного выше при-
мера показано на рис. 5.
Рис. 5.. Последовательность состояний стека программы 2.1 применительно к
тестовому примеру.
Стек в программах на Си++ используется при вызове всех функций, а не только
рекурсивных. Стек, как и связный список, является одной из разновидностей абст-
рактных типов данных. Характерная особенность стека –соответствие принципу "по-
следним прибыл –первым обслужен" (в отличие от стека, очередь является примером
абстрактного типа данных, действующего по принципу "последним прибыл –послед-
ним обслужен").
92
4. Еще три примера рекурсии
В этом параграфе приводятся три примера рекурсивных функций. В 3-й лекции
рассматривалась функция для вычисления факториала целого положительного числа
(лекция 3, программа 3.1). Ниже приведен рекурсивный аналог этой функции:
int factorial( int number )
{
if ( number < 0 )
{
cout << "\nОшибка - отрицательный аргумент факториала\n";
exit(1);
}
else if ( number == 0 )
return 1;
return number*factorial( number - 1 );
}
Фрагмент программы 4.1.
В качестве второго примера (фрагмент программы 4.2) дана функция, возводя-
щая свой первый параметр (типа "double") в степень с показателем, который переда-
ется в качестве второго параметра (неотрицательное целое число).
double raised_to_power( double number, int power )
{
if ( power < 0 )
{
cout << "\nОшибка - отрицательный показатель степени\n";
exit(1);
}
else if ( power == 0 )
return 1.0;
return number*raised_to_power( number, power - 1 );
}
Фрагмент программы 4.2.
В рекурсивных функциях из программ 4.1 и 4.2 особое внимание уделено за-
щите от "бесконечного вызова ". Эта защита основана на проверке параметров, обес-
печивающей выполнение вычислений только для корректных значений переданных
параметров. Т.о. гарантируется, что будут произведены корректные вычисления и в
конечном счете произойдет возврат из функции. При недопустимых значениях пара-
метров выдается сообщение об ошибке и выполняется возврат из функций или завер-
шение работы программы.
Третий пример (фрагмент программы 4.3) –это рекурсивная функция для вы-
числения суммы первых n элементов целочисленного массива "a[]".
int sum_of( int a[], int n )
{
if ( n < 1 || n > MAXIMUM_NO_OF_ELEMENTS )
{
93
cout << "\nОшибка - допускается суммирование от 1 до ";
cout << MAXIMUM_NO_OF_ELEMENTS << " элементов\n";
exit(1);
}
else if ( n == 1 )
return a[0];
return a[n-1]+sum_of( a, n-1 );
}
Фрагмент программы 4.3.
5. Рекурсия и циклы
При программировании на Си++ рекурсию применять совсем не обязательно, и
на практике она используется довольно редко. Любую рекурсивную функцию можно
реализовать итеративно, т.е. с помощью циклов "for", "while" или "do...while". В
некотором смысле, какое определение функции выбрать (рекурсивное или итераци-
онное) –вопрос пристрастий программиста. Исходный текст рекурсивных функций
иногда легче для понимания, но итерационные функции практически всегда работают
быстрее. Далее приводятся итерационные аналоги двух рекурсивных функций, кото-
рые ранее рассматривались в данной лекции.
void print_backwards()
{
char chars[MAX_ARRAY_LENGTH];
int no_of_chars_input = 0;
do {
cout << "Введите символ (или '.' для завершения ввода): ";
cin >> chars[no_of_chars_input];
no_of_chars_input++;
} while ( chars[no_of_chars_input - 1] != '.'
&& no_of_chars_input < MAX_ARRAY_LENGTH );
for ( int count = no_of_chars_input - 2; count >= 0; count-- )
cout << chars[count];
}
Фрагмент программы 2.1b.
int factorial( int number )
{
int product = 1;
if ( number < 0 )
{
cout << "\nОшибка - отрицательный аргумент факториала\n";
exit(1);
}