Контрольные вопросы

1. Как рекомендуется организовать внутреннюю работу пользовательских функций по отношению к другим функциям в программах на языке С? Перечислите основные правила организации внутренней работы функций и достоинства этих правил.

2. В чем заключается основное назначение заголовочных файлов (h-файлов) в проектах языка С?

3. Как следует объявить функцию, чтобы доступ к ней был невозможен за пределами файла, где она была определена?

4. Как следует объявить функцию, чтобы к ней можно было обращаться из других функций проекта?

5. Какие классификаторы классов памяти поддерживает стандарт языка С?

6. Какой классификатор памяти используется по умолчанию в программах на языке С?

7. Какие расширения можно применить к файлам, содержащим пользовательские функции?

8. Как осуществляется компиляция файлов с пользовательскими функциями в программной среде Visual Studio?

9. Как осуществляется подключение файлов с пользовательскими функциями, которые расположены на различных логических дисках компьютера?

Библиографический список

1. Прата С. Язык программирования С. Лекции и упражнения : пер. с англ. / С. Прата. – 5-е изд. – М.: Вильямс, 2006. – 960 с.

2. Шилдт Г. Полный справочник по С : пер. с англ./Г. Шилдт. – 4-е изд. – М.: Вильямс, 2007. – 704 с.

3. Дейтл Х.М. Как программировать на С : пер. с англ./Х.М. Дейтл, П.Дж. Дейтл. – 4-е изд. – М. : Бином-Пресс, 2006. – 912 с.

4. Керниган Б. У. Язык программирования С : пер. с англ./Б. У.Керниган, Д. М.Ритчи. – 2-е изд. – М.: Вильямс, 2007. – 304 с.

5. Хусаинов Б.С. Структуры и алгоритмы обработки данных. Примеры на языке Си (+CD)  : учеб. пособие / Б.С. Хусаинов. – М.: Финансы и статистика, 2004. – 464 с.

6. Математический энциклопедический словарь / гл. ред. Ю. В. Прохоров ; ред. кол.  : С. И. Адян, Н. С. Бахвалов, В. И. Битюцков [и др.]. – М. : Сов. энцикл., 1988. – 847 с.

Тема 18 Рекурсивные алгоритмы и функции

Ставится задача изучить различные виды рекурсии и применения рекурсивных алгоритмов, получить навыки программирования на языке С с использованием рекурсивных функций.

ТЕОРЕТИЧЕСКАЯ ЧАСТЬ

Рекурсивные функции (лат. recursio – возвращение) – в вычислительной математике – функции, определенные на множестве натуральных чисел и принимающие значения того же множества [1].

Рекурсивный алгоритм – это алгоритм, решающий задачу путем решения одного или нескольких более простых вариантов той же задачи [2]. Функция называется рекурсивной, если в ее определении содержится вызов этой же функции [3]. Рекурсивная функция может вызывать саму се6я или непосредственно, или косвенно через другую функцию [4]. Рекурсии целесообразно применять в задачах, которые можно разбить на множество меньших подобных задач [5]. Рекурсия в программировании может быть определена как сведение задачи к такой же задаче, но манипулирующей более простыми данными.

Рекурсивную программу всегда можно преобразовать в итеративную, использующую циклы и выполняющую те же вычисления. И наоборот, используя рекурсию, можно реализовать итеративную программу, не прибегая к циклам.

Рекурсивный подход обычно предпочитается итеративному в тех случаях, когда рекурсия более полно и последовательно отражает математическую сторону задачи и приводит к программе, которая проще для понимания и отладки. Другой причиной для выбора рекурсивного решения является то, что итеративное может не быть очевидным [4].

Наличие в задаче рекуррентного соотношения позволяет использовать рекурсию. Например, арифметическая прогрессия – последовательность чисел, в которой разность между последующими и предыдущими членами остается неизменной и называется разностью прогрессии [1]. То есть каждый следующий член прогрессии равен предыдущему, увеличенному на разность прогрессии.

Различают прямую и косвенную рекурсию. Прямой (непосредственной) рекурсией является вызов функции внутри ее тела, косвенной – рекурсия, осуществляющая рекурсивный вызов функции посредством цепочки вызова других функций [6]. Все функции, входящие в цепочку, тоже считаются рекурсивными.

В рекурсии простейшей формы рекурсивный вызов расположен в конце функции, непосредственно перед оператором возврата из функции (или возвращаемого значения). Такая рекурсия называется хвостовой или концевой и является простейшей формой рекурсии, поскольку действует подобно циклу [7]. Если в программе имеется хвостовая рекурсия, то ее лучше преобразовать к итерации.

Отметим особенности работы рекурсивных функций, характерные для тех языков программирования, которые поддерживают рекурсию. К этим языкам относится и С.

Когда функция вызывает сама себя (когда имеем дело с рекурсивной функцией), новый набор локальных переменных и параметров размещается в памяти в стеке, а код функции выполняется с самого своего начала, причем используются именно эти новые переменные. При рекурсивном вызове функции новая копия ее кода не создается. Новыми являются только значения, которые использует данная функция. При каждом возвращении из рекурсивного вызова старые локальные переменные и параметры извлекаются из стека, и сразу за рекурсивным вызовом возобновляется работа функции с «внутренней» точки ее вызова [8].

Общая схема определения рекурсивной функции

• Существует условие, при котором функция выполняет свою задачу с использованием рекурсивных вызовов, соответствующих одной или нескольким «уменьшенным» версиям задачи.

• Существует также условие, которое будет удовлетворено и при котором функция выполняет свою задачу без рекурсивных вызовов. Оно называется базовым или условием останова [2; 4–6].

Рассмотрим некоторые определения, относящиеся к рекурсии. Максимальное число рекурсивных вызовов без возвратов, которые происходят во время выполнения программы, называется глубиной рекурсии. Число рекурсивных вызовов в каждый конкретный момент времени, – это текущий уровень рекурсии. В практических приложениях важно убедиться, что максимальная глубина рекурсий не только конечна, но и достаточно мала [11].

Существуют три разные формы рекурсивных программ:

1. форма с выполнением действий до рекурсивного вызова (на рекурсивном спуске).

2. фома с выполнением действий после рекурсивного вызова (на рекурсивном возврате);

3. форма с выполнением действий как до, так и после рекурсивного вызова (как на рекурсивном спуске, так и на рекурсивном возврате).

Понятие рекурсии сходно с понятием математической индукции. У нее, как и у последней, есть база – аргументы, для которых значения функции определены (элементарные задачи), и шаг – способ сведения задачи к более простым задачам.

Одно из преимуществ рекурсии состоит в том, что она предлагает простейшее решение некоторых задач программирования. Недостаток ее заключается в том, что некоторые рекурсивные алгоритмы могут довольно быстро исчерпать ресурс памяти компьютера. Наряду с этим, рекурсию трудно документировать и поддерживать [7].

Главное при оформлении рекурсивной функции – это правильное задание условия выхода из рекурсивных вызовов. Если при зацикливании программы на операторе цикла компьютер может выполнять его, не реагируя на любые действия пользователя, то при зацикливании из-за неправильного оформления рекурсивной функции неизбежно происходит аварийный останов, когда будет исчерпан объем оперативной памяти, которая выделяется при каждом рекурсивном вызове. Следует всегда помнить, что даже при правильном оформлении рекурсивной функции необходимо учитывать объем вычислительной работы.Так, расчет факториала целого положительного числа – трудоемкая операция. В математической постановке задачи нет ничего сложного, но при программировании этого процесса для различных систем и компьютеров имеются свои ограничения, например трудности рекурсивного вычисления факториала.

Для некоторых задач рекурсивные функции вполне оправданы. В частности, динамические информационные структуры включают рекурсивность в само определение обрабатываемых данных. Именно для таких данных применение рекурсивных алгоритмов не имеет конкуренции со стороны итерационных методов [6].

Рекурсивная задача в общем случае разбивается на ряд этапов. Вызывается рекурсивная функция, с помощью которой можно решать только простейшую часть задачи – так называемую базовую задачу (или несколько таких задач). Если эта функция вызывается для решения базовой задачи, она просто возвращает результат. Если функция вызывается для решения более сложной задачи, она делит эту задачу на две части: одну, которую умеет решать, и другую, которую не умеет. Чтобы сделать рекурсию выполнимой, последняя часть должна быть похожа на исходную задачу, но быть по сравнению с ней несколько проще или меньше. Поскольку эта новая задача подобна исходной, функция вызывает новую копию самой себя, чтобы начать работать над меньшей проблемой – это называется рекурсивным вызовом, или шагом рекурсии. Шаг рекурсии включает ключевое слово return, так как в дальнейшем его результат будет объединен с той частью задачи, которую функция умеет решать, и сформируется конечный результат, который будет передан обратно в исходное место вызова.

Рассмотрим пример вычисления факториала целого положительного числа, когда хвостовая рекурсия есть и когда ее нет. При этом покажем возможность исключения рекурсии. Пусть определена следующая рекурсивная функция:

int fact (int n) {   if (n == 0)     return 1;   else     return n * fact (n - 1); }

Исходная функция fact() не имеет хвостовой рекурсии, так как перемножение выполняется после рекурсивного вызова (умножение на n). Для исключения рекурсии сначала приведем fact() к виду с хвостовой рекурсией, например

int fact (int n) {   return fact_w (1,n); }

Вспомогательная функция fact_w() будет содержать хвостовую рекурсию. Ее программный код выглядет так:

int fact_w (int r, int n) {   if (n == 0)     return r;   else     return fact(r*n,n-1); }

В функции fact_w() хвостовая рекурсия присутствует в силу рекурсивного обращения только к самой функции в операторе return.

Обратимся к известному положению об исключении хвостовой рекурсии: если функция f(x) содержит в конце рекурсивный вызов в виде return f(y), то рекурсию можно исключить путем присваивания  x = y, и перехода goto на начало функции [14]. Программный код исключения хвостовой рекурсии будет следующим:

int fact_w (int r, int n) { met:   if (n == 0)     return r;   else {     r = r*n;     n = n-1;     goto met;   } }

Использование оператора goto нежелательно с точки зрения современных представлений и методов структурного программирования, преобразуем конструкцию с goto к циклу:

int fact_w (int r, int n) {   while (n != 0) {     r = r*n;     n = n-1;   }   return r; }

В качестве окончательной оптимизации можно исключить и вспомогательную функцию fact_w(), выполнив подстановку тела функции в точку ее вызова (inlining). В итоге получим следующий программный код функции, вычисляющей факториал числа:

/* * Оптимизация функции * вычисления факториала числа */ int fact (int n) {   int r = 1;   while (n != 0) {     r = r*n;     n = n-1;   }   return r; }

В приведенной функции нет ни рекурсивных вызовов, ни оператора goto.

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

Каждая функция в программе на языке С находится на одном уровне с остальными функциями, составляющими программный проект, может вызвать любую другую функцию или быть вызванной. Отсюда функция main() может вызывать сама себя в рамках некоторой рекурсии или быть вызвана из других функций, хотя подобное встречается достаточно редко [7]. Следует иметь в виду, что когда программа составляется из нескольких функций, ее выполнение начинается с первого оператора функции main().

ПРАКТИЧЕСКАЯ ЧАСТЬ

Пример 1. Написать рекурсивную функцию определения наибольшего общего делителя двух целых чисел.

Программный код решения примера

#include <stdio.h> #include <conio.h> #include <stdlib.h> // Прототип рекурсивной функции int gcd(int a, int b); int main (void) { int a = 0, b = 0, in; // Проверка ввода двух целых чисел do { printf("\n Enter the two different natural numbers, through the gap: "); in = scanf_s("%d%d", &a, &b); if (in != 2) { printf("\n Error input. Press any key to exit: "); _getch(); exit(1); } if ( (a != b) && (b != 0) ) break; if (b == 0) a = b; } while ( (a == b) ); // Вывод результата на консоль printf("\n a = %d, b = %d, GCD = %d; \n", a, b, gcd(a,b)); printf("\n\n Press any key: "); _getch(); return 0; } // Определение рекурсивной функции int gcd(int a, int b) { if ( (a % b) == 0) return b; else return gcd(b, a % b); }

Решение примера выполнено на основе простой хвостовой рекурсии, поскольку значения вызовов функции самой себя gcd(b, a % b) возвращаются оператором return. Известно, что если даны два числа А и В, то максимальный остаток от деления числа А на число В будет на единицу меньше числа В. В определении рекурсивной функции gcd() условием останова является то, что остаток от деления двух данных чисел равен нулю. Рекурсивные вызовы функции gcd() связаны с изменением расположения первоначально заданных аргументов, когда аргумент, стоящий на втором месте (b), будет на первом месте, а на втором месте определяется операция остатка от деления, т. е. a%b. И это происходит до тех пор, пока остаток от деления не станет равным нулю, т. е. выполнится условие останова (базовое условие).

Возможный результат выполнения программы приведен на рис. 18.1.

Р ис. 18.1. Наибольший общий делитель для чисел 123 и 45

Задание 1

1. В программе оператор if используйте для рекурсивных вызовов, а оператор else – как условие останова.

2. B программу включите определение количества рекурсивных вызовов.

3. Видоизмените программу для случая ошибочного ввода чисел, предусмотрите повторное приглашение на ввод чисел.

4. Напишите функцию вычисления наибольшего общего делителя на основе итерации (с использованием операторов цикла).

Пример 2. Написать рекурсивную функцию, которая выводит на консоль двоичный эквивалент целого десятичного числа, введенного пользователем с клавиатуры.

Для решения примера отметим, что в двоичной системе счисления числа представлены в виде суммы степеней 2. Подобно тому, как в десятичной системе счисления число 234 означает 210² + 310¹ + 410⁰, число 101 в двоичной системе означает 12² + 02¹ + 12⁰ [7]. В двоичных числах используются только цифры 0 и 1.

Очевидно, что за основу решения примера следует брать целочисленное деление. Если введено число n, то оно может быть либо четным, либо нечетным. Тогда остаток от деления на 2 будет равняться нулю для четных чисел и единице – для нечетных.

Программный код решения примера

#include <stdio.h> #include <conio.h> #include <locale.h> // Прототип рекурсивной функции void dec2bin(unsigned long int); int main (void) { unsigned long int n; setlocale(LC_ALL, "Russian"); // для русских шрифтов printf("\n\t Введите целое десятичное число\n \ (или нечисловой символ для завершения программы): "); while (scanf_s("%ul", &n) == 1) { printf("\n Двоичный эквивалент: "); dec2bin(n); printf("\n\n\t Введите целое десятичное число\n \ (или нечисловой символ для завершения программы): "); } printf("\n\n ... Нажмите любую клавишу: "); _getch(); return 0; // выход из программы } // Определение рекурсивной функции void dec2bin(unsigned long int n) { int r; r = n % 2; if (n >= 2 ) dec2bin(n/2); printf("%d", r); return; }

В программе шаги рекурсии осуществляются при условии, что аргумент рекурсивной функции больше или равен двум. Как только это условие нарушается, происходит распечатка результата и выход из функции. Например, при n = 10 остаток от целочисленного деления r = 10%2 = 0. В то же время аргумент функции dec2bin() будет равняться 5. Тогда остаток от целочисленного деления r = 5%2 = 1. Далее аргумент функции будет равняться 2 (5/2), так как аргумент функции определен через целое число. Остаток от целочисленного деления r = 2%2 = 0. Теперь аргумент рекурсивной функции будет равен 1, что прерывает рекурсивные вызовы функции (нарушается условие проверки оператором if). Остаток от деления r = 1%2 = 1. Вывод результата на консоль будет осуществляться из стека по дисциплине LIFO (Last Input First Output – последним вошел, первым вышел).

Пример выполнения программы показан на рис. 18.2.

Р ис. 18.2. Преобразование десятичных чисел в двоичные эквиваленты

Задание 2

1. Определите, какой тип рекурсии используется в приведенной программе.

2. В программу включите защиту от ввода отрицательных целых чисел.

3. Вывод результатов преобразования десятичных чисел в двоичные эквиваленты осуществите в текстовый файл с именем compX.txt, где Х – номер компьютера, на котором выполняется лабораторная работа. В текстовый файл занести также и преобразуемое десятичное число.

4. В программе вместо функции printf() как функции вывода результата примените функцию putchar().

5. В программу внесите изменения для подсчета количества рекурсивных вызовов.

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

7. Напишите программу с рекурсивной функцией вывода на консоль десятичного числа для введенного пользователем его двоичного эквивалента.

Пример 3. С использованием косвенной рекурсии написать программу по решению следующей задачи. Строка состоит из клеток, пронумерованных от 1 до n. Состояние клетки можно изменить: если она пуста, поставить в нее шашку (занять ее), иначе убрать из нее шашку (освободить ее). Вначале строка пуста.

Нужно занять все клетки, соблюдая правило: изменение клетки допустимо, если она имеет номер 1 или расположена непосредственно после занятой клетки, имеющей минимальный номер среди занятых клеток.

Вход. Целое n, 1  n  15.

Выход. Последовательность элементов вида +i или –i, обозначающих соответственно занять клетку i и освободить клетку i [9]. Например, при n = 3 выход имеет вид +1+2–1+3+1.

Программный код решения примера [см. 9]

#include <stdio.h> #include <conio.h> // для getch(); #include <stdlib.h> // для exit(); // Прототипы функций void fillOnly(int); void free_n(int); void fill_n(int); int main (void) { int n = 1; // размер строки int in = 1; // контроль ввода n printf("\n Enter a length of string (naturel number): "); in = scanf_s("%i", &n); if (in != 1 || n < 1 || n > 15) { printf("\n Error input. Press any key to exit: "); _getch(); exit(0); } puts("\n\tResult:"); fill_n(n); printf("\n\n Press any key to exit: "); _getch(); return 0; } // Объявления функций // 1-я функция void fillOnly(int n) { if (n == 1) printf("\t%+3d\n", 1); else { fillOnly(n-1); printf("\t%+3d\n", n); free_n(n-1); } } // 2-я функция void free_n(int n) { if (n == 1) printf("\t%+3d\n", -1); else { fillOnly(n-1); printf("\t%+3d\n", -n); free_n(n-1); } } //3-я функция void fill_n(int n) { if (n == 1) printf("\t%+3d\n", 1); else { if (n == 2) printf("\t%+3d\n\t%+3d\n", 1, 2); else { fillOnly(n-1); printf("\t%+3d\n", n); fill_n(n-2); } } }

В программе вывод результата на консоль выполнен в виде столбца. Для этого используется эскейп-последовательность \t в функциях printf(). Форматный вывод значений в функциях printf() выполнен с помощью спецификации %+3d, что позволяет автоматически устанавливать знаки чисел, под которые отводятся 3 позиции.

Как видно из приведенного программного кода, в каждой из функций имеется вызов самой функции и других функций. Это указывает на косвенное обращение к функциям.

Результат выполнения программы представлен на рис. 18.3.

Р ис. 18.3. Пример заполнения и освобождения клеток

Задание 3

1. В программе укажите рекурсивные функции. Объясните их работу.

2. Проверьте работу программы при смене порядка объявлений функций.

3. Проверьте работу программы без использования прототипов функций.

4. Для случая, когда n  5, предусмотрите вывод результата в строку, а не в столбец.

5. В программу добавьте программный код для подсчета рекурсивных вызовов каждой из рекурсивных функций.

6. Постройте зависимость количества рекурсивных вызовов одной из функций от введенного числа n.

7. Постройте зависимость числа комбинаций заполнения и освобождения клеток от введенного числа n.

Пример 4. Написать программу по решению задачи «Ханойская башня». Имеется пирамида из n колец, лежащих на основании А (на стержне, на столбе) одно на другом в порядке убывания размеров. Кольца должны быть перемещены на основание В в том же порядке, в котором они были на основании А, при использовании промежуточного основания С. Единственными разрешенными перемещениями являются такие, при которых кольцо, взятое с вершины одной из пирамид, помещается на большее кольцо, либо на пустое основание. Осуществить выдачу на печать (на консоль, в текстовый файл) последовательности перемещений колец. Алгоритм решения этой задачи достаточно подробно описан в работе [10].

Решение задачи «Ханойская башня»

Для рекурсивного решения задачи следует пройти три этапа.

1-й этап – параметризация. Естественным параметром является n – число колец. В число параметров можно включить также три основания: А (исходное), В (конечное), С (промежуточное).

2-й этап – поиск тривиальных случаев. Здесь тривиальным случаем будет такой, при котором n = 0; тогда просто нечего делать.

3-й этап – редукция общего случая к более простому. Здесь надо отметить, что n колец могут быть перемещены с А на В следующим путем:

• переноса (рекурсивно) n – 1 колец с вершины А (исходное основание) на С (промежуточное основание) с учетом правил: основание В (конечная цель) используется как промежуточное;

• перемещения на В кольца наибольшего диаметра, оставшегося на А;

• переноса (рекурсивно) n – 1 других колец с С на В при соблюдении правил с А в качестве промежуточного основания.

Алгоритм решения задачи запишем в следующем виде:

hanoi(n–1, A, C, B);