книги / Технологии разработки объектно-ориентированных программ на язык C++. Основы структурного программирования на алгоритмическом языке C++
.pdfПри определении указатель на функцию может быть сразу проинициализирован:
void (*ptrf1)()=f1;
Указатели на функции удобно использовать в тех случаях, когда функцию надо передать в другую функцию как параметр.
Пример:
Необходимо разработать программу, которая в одномерном массиве вычисляет:
количество положительных элементов;
количество отрицательных элементов;
минимальный элемент в массиве;
максимальный элемент в массиве.
Во всех этих задачах нужно перебрать массив и каким-то образом обработать его каждый элемент, например сравнить с нулем или с другой переменной. Обработку элемента можно оформить как функцию и передавать в виде указателя на функцию в другую функцию, которая будет выполнять перебор элементов массива.
//проверка, является ли элемент отрицательным void is_negative(int a, int&k)
{
if (a < 0)k++;
}
//проверка, является ли элемент положительным void is_positive(int a, int&k)
{
if (a >= 0)k++;
}
//поиск минимального из двух чисел void is_min(int a, int&min)
91
{
if (a < min)min = a;
}
//поиск максимального из двух чисел void is_max(int a, int&max)
{
if (a > max)max = a;
}
/*функция для перебора элементов массива, способ обработки элемета передается как указатель на функцию*/
void for_each(int*mas, int size, void ptr(int x,int&y), int&res)
{
for (int i = 0; i < size; i++)
ptr(mas[i], res);//вызов функции через
указатель
}
void main()
{
setlocale(0, "");
int*mas |
=new int[10] { 1,2,-3,4,5,-6,-7,8,9,-10 }; |
cout << |
"вычисляем количество отрицательных чисел в |
массиве:"; |
|
int res |
= 0; |
for_each(mas, 10, is_negative, res); |
|
cout << |
res << "\n"; |
cout << |
"вычисляем количество положительных чисел в |
массиве:"; |
|
92
res = 0;
for_each(mas, 10, is_positive, res);
cout << |
res << "\n"; |
cout << |
"вычисляем минимальный элемент в массиве:"; |
int min |
= mas[0]; |
for_each(mas, 10, is_min, min); |
|
cout << |
min << "\n"; |
cout << |
"вычисляем максимальный элемент в массиве:"; |
int max |
= mas[0]; |
for_each(mas, 10, is_max, max); |
|
cout << |
max << "\n"; |
}
93
Глава 11. РЕКУРСИВНЫЕ ФУНКЦИИ
11.1. Понятие рекурсии
Рекурсивные функции – это процесс повторения элементов внутри этого элемента. Далее для удобства будет использоваться слово «рекурсия». Данный термин употребляют программисты. Например, если два зеркала установить друг напротив друга, то возникающее в них изображение есть бесконечная рекурсия. Математики применяют ее в комбинаторике. Рекурсия – это важный инструмент для решения вычислительных и математических задач в умелых руках [6].
Алгоритм определен рекурсивно, если состоит:
из одного или нескольких условий выхода из рекурсии;
шага рекурсии, который в конечном итоге должен приводить к условиям выхода из рекурсии.
Рассмотрим пример, в котором числа от 1 до m (где m >= 1) выводятся в обратном порядке.
Создается функция fun. Ее параметром является число m, которое выводится на экран.
void fun(int m) { cout << m;
}
Учитывая, что по условию задачи m <= 1, выполним проверку на попадание числа m в заданное ограничение:
void fun(int m) { if (m > 0)
cout << m;
}
Организуем вызов функции fun в рекурсивном формате. Перед каждым вызовом выводим на экран начальное значение m, затем из m вычитается 1 и функция fun вызывается с новым значением m.
94
Действия продолжаются до тех пор, пока не будет нарушено усло-
вие m >= 1.
void |
fun(int |
m) { |
if (m > 0) |
{ |
|
|
cout << |
m-- << " "; // Выводим m, а затем из m вычитаем 1 |
|
fun(m); |
// Вызываем функцию fun с новым значением |
} |
|
|
} |
|
|
Например, результат выполнения fun(10) выглядит следующим образом:
10 9 8 7 6 5 4 3 2 1
11.2. Когда рекурсия не используется
Важно понимать, что любой рекурсивный алгоритм может быть переписан без использования рекурсии. Быстродействие алгоритмов без рекурсии по сравнению с рекурсивными алгоритмами при решении одной и той же задачи, как правило, выше.
Причиной отказа от рекурсии является ограничение на объем хранимых программой локальных переменных и значений параметров одновременно выполняющихся функций. При очень глубокой рекурсии этот объем возрастает, и программа перестает работать, выдавая ошибку «stack overflow» (переполнение стека).
Яркий пример рекурсии по вычислению факториала положительного числа (n!) является также примером, когда рекурсию можно не использовать, поскольку рекурсивный алгоритм приводит к большой глубине рекурсии и имеет очевидную реализацию в виде обычного циклического алгоритма.
Вопрос о желательности использования рекурсивных функций
впрограммировании неоднозначен: с одной стороны, рекурсивная форма может быть структурно проще и нагляднее, в особенности, когда сам реализуемый алгоритм, по сути, рекурсивен. Кроме того,
внекоторых декларативных или функциональных языках (таких как Пролог или Haskell) просто нет синтаксических средств для организации циклов, и рекурсия в них – единственный доступный меха-
95
низм организации повторяющихся вычислений. С другой стороны, обычно рекомендуется избегать рекурсивных программ, которые приводят (или в некоторых условиях могут приводить) к слишком большой глубине рекурсии.
11.3. Виды рекурсии
Простая рекурсия
Примером простой рекурсии является вычисление факториала положительного числа n (n! = n*(n – 1)*(n – 2)*…*1). Условием выхода из рекурсии является n = 0, и так как 0! = 1, то в программе необходимо добавить условие, при истине которого будет возвращаться 1.
При вводе числа от 13 и больше возвратятся неверные значения вследствие нехватки размера типа данных.
Визуальная схема приведена на рис. 11.1.
Рис. 11.1. Алгоритм нахождения факториала числа
На последнем шаге срабатывает условие выхода из рекурсии, и она прекращается. Количество вложенных вызовов функции называется глубиной рекурсии.
#include <iostream> using namespace std; int factorial(int n) { /*
Рекурсивная функция, параметром которой является число, факториал которого нужно найти
*/
int result; /* Переменная, в которой будет
96
храниться результат вычисления факториала */
if (n == 0) // Условие выхода из рекурсии return 1;
// Так как 0! = 1, то возвращается единица
else result = n * factorial(n – 1); // Шаг рекурсии return result;
// Возвращается результат вычисления факториала
}
int main() {
setlocale(LC_ALL, "Rus"); int n;
cout << "Введите n: "; cin >> n;
// Ввод значения для вычисления факториала
cout << n << "!" << " = " << factorial(n) << endl; /*
Вызов рекурсивной функции одновременно с выводом
ее
значения на экран
*/
system("pause");
}
В данном случае алгоритм построен рекурсивно:
так как условием выхода из рекурсии является n = 0;
шагом рекурсии является вычисление n * factorial(n – 1). Подробнее: в теле функции main() вызывается функция factorial
спараметром n, введенным пользователем. Значение n сверяется
сусловием выхода из рекурсии, при n! = 0 переменной result при-
сваивается произведение n и функции factorial с параметром на 1 меньше. Иными словами, функция каждый раз передает в саму себя параметр на 1 меньше, чем получила сама.
Результат для n = 6:
Введите n: 6 6! = 720
97
Сложная рекурсия
Сложная рекурсия – это процесс, в котором одна функция вызывает другую, а та, в свою очередь, вызывает первую. При этом описываемая первой функция должна вызвать еще не описанную другую. Чтобы это было возможно, требуется использовать прототип функции.
#include <iostream> |
|
using namespace std; |
|
int fb(int); |
// Прототип второй функции |
int fa(int n) { |
|
/* |
|
Первая функция, параметром которой является число, которое выводится на экран
*/
cout << "A : " << n << endl; return fb(n – 1);
// Обращение к функции fb с параметром n – 1
}
int fb(int n) { // Вторая функция cout << "B : " << n << endl; if (n < 10) return fa(n + 2); /*
По рекурсивной ветви идет обращение к функции fa с
параметром n + 2 |
|
*/ |
|
else return 0; |
// По терминальной ветви возвращается |
0 |
|
} |
|
int main() { |
|
cout << fa(7) << endl; |
// Вызывается функция fa с |
|
параметром 7 |
} |
|
В данном случае функция main вызывает функцию fa с параметром 7. Та, в свою очередь, вызывает fb с параметром n – 1. Условием выхода из рекурсии является достижение значения n > 10, тогда рекурсия прекращает cвое выполнение.
98
Результат при fa(7) выглядит следующим образом:
A : 7 B : 6 A : 8 B : 7 A : 9 B : 8 A : 10 B : 9 A : 11 B : 10 0
Хвостовая рекурсия
Хвостовая рекурсия – частный случай рекурсии, при котором любой рекурсивный вызов является последней операцией перед возвратом из функции.
Пример нахождения числа Фибоначчи с помощью хвостовой рекурсии:
#include <iostream> using namespace std; int fib(int n) {
if (n == 1 || n == 2) return 1;
// Числа Фибоначчи под номерами 1 и 2 – это 1
if (n == 0) return 0; /* Если элементов нет, то рекурсия заканчивается и возвращает 0 */
return fib(n – 1) + fib(n – 2); /* Последним действием в функции является рекурсивный вызов
*/
}
int main() {
cout << fib(15) << endl;
99
return 0;
}
Результат при fib(15)
610
11.4. Рекурсивные функции работы со стеком
Стек (stack) – абстрактный тип данных, представляющий собой список элементов, организованных по принципу «последним пришел – первым вышел». Чаще всего принцип работы стека сравнивают со стопкой тарелок: чтобы взять вторую сверху, нужно снять верхнюю.
Рекурсивный стек – область памяти, которая хранит все промежуточные вычисления рекурсии. Завершаются вычисления путем восстановления сохраненных значений в порядке, который обратен рекурсивным обращениям. При заполнении всей области памяти последующая попытка вызова рекурсии приводит к ошибке (stack overflow).
Причины переполнения стека
Бесконечная рекурсия:
int foo() { return foo();
}
Функция будет вызывать сама себя, расходуя пространство
встеке, пока стек не переполнится.
Не сработало условие выхода из рекурсии:
if (n == 0) |
// Условие выхода из |
|
рекурсии |
return 1; |
|
else result = n * factorial(n – 1); |
// Шаг рекурсии |
return result; |
|
Условие выхода из рекурсии не сработает при отрицательном n, так как программа уйдет в бесконечную рекурсию.
Ненамеренное использование рекурсии:
100