2020-01-14
93
ляр "print_backwards()"), см. рис. 3.
Рис. 3. Возврат из 3-го экземпляра функции
"print_backwards()" во второй.
Рис. 4.. Завершение выполнения программы.
Второй экземпляр "print_backwards()" завершается, но перед завершением вы-
водит на экран символ "i". В свою очередь, первый экземпляр функции перед завер-
шением работы напечатает на экране символ "H" (рис. 4).
Для организации вызовов функций и создания автоматических переменных в
программах на Си++ отводится специальная область памяти – стек. Память, необхо-
Димая для очередного вызова функции, выделяется в верхней части стека (в старших
Адресах). При завершении функции размер стека уменьшается на соответствующую
Величину. Изменение состояния программного стека для рассмотренного выше при-
Мера показано на рис. 5.
Рис. 5.. Последовательность состояний стека программы 2.1 применительно к
Тестовому примеру.
Стек в программах на Си++ используется при вызове всех функций, а не только
|
|
|
Рекурсивных. Стек, как и связный список, является одной из разновидностей абст-
рактных типов данных. Характерная особенность стека – соответствие принципу "по-
следним прибыл – первым обслужен" (в отличие от стека, очередь является примером
абстрактного типа данных, действующего по принципу "последним прибыл – послед-
ним обслужен").
92
Еще три примера рекурсии
В этом параграфе приводятся три примера рекурсивных функций. В 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.
Рекурсия и циклы
При программировании на Си++ рекурсию применять совсем не обязательно, и
На практике она используется довольно редко. Любую рекурсивную функцию можно
реализовать итеративно, т.е. с помощью циклов "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);
}
else if (number == 0)
return 1;
for (; number > 0; number--)
product *= number;
return product;
}
94
Фрагмент программы 4.1b.
Конечно, вопрос о том, какая реализация конкретной функции более понятна,
Довольно спорный. Обычно в итерационную функцию приходится включать больше
Локальных переменных, например, в первом примере был добавлен массив
"chars[MAX_ARRAY_LENGTH]", а во втором примере – целочисленная переменная
"product". Другими словами, в итеративных функциях память тратится на локальные
Переменные, а рекурсивных функциях – на организацию вызовов.
Рекурсия в структурах данных
На практике рекурсия чаще встречается в структурных типах данных, а не в
Функциях. Рекурсивная структура данных уже использовалась в предыдущей лекции
для определения узла связного списка. В структуре "узел" хранится указатель струк-
туру такого же типа:
Struct node
{
char word[MAX_WORD_LENGTH];
node *ptr_to_next_node;
};
В последующих лекциях будут более подробно рассматриваться другие приме-
ры рекурсивных структур данных и особенности их описания на Си++.
Рекурсивная реализация алгоритма быстрой сортировки
В завершающей части этой лекции кратко рассмотрим известный пример ре-
курсивного алгоритма – алгоритм быстрой сортировки QuickSort. Этот рекурсивно
Определенный алгоритм предназначен для упорядочения значений, хранящихся в
Массиве, по возрастанию или по убыванию.
Предположим, что 11 элементов массива имеют следующие значения (рис. 6).
Рис. 6.. Начальное состояние массива.
Идея алгоритма основана на рекурсивном выполнении разбиения массива на
Две части и переупорядочении элементов в этих частях. Разбиение выполняется путем
выбора некоторого элемента, который будем называть граничным. После разбиения
