Стивен Прата - Язык программирования C. Лекции и упражнения (6-е изд.) 2015

Для решения задачи необходим некоторый метод, или алгоритм. Скажем, каким образом можно найти двоичный эквивалент 5? Ясно, что нечетные числа должны иметь двоичное представление, оканчивающееся цифрой 1. Четные числа оканчиваются цифрой 0, поэтому вы можете определить, является последняя цифра 1 или 0, вычислив значение 5 % 2. Если результат равен 1, то число 5 нечетное, и последней цифрой будет 1. В общем случае, если n — число, то последней цифрой будет n % 2, поэтому первая найденная цифра — это последняя цифра, которую нужно вывести. Эго предполагает применение рекурсивной функции, в которой выражение n % 2 вычисляется до рекурсивного вызова, но результат выводится после него. Таким образом, первое вычисленное значение является последним выводимым значением.

Чтобы получить следующую цифру, разделите исходное число на 2. Эго двоичный эквивалент сдвига десятичной точки на одну позицию влево, что позволит выяснить следующую двоичную цифру. Если получается четное значение, то следующей двоичной цифрой будет 0, а если нечетное — то 1. Например, 5/2 дает 2 (целочисленное деление), так что следующая цифра — 0. Теперь мы имеем 01. Далее повторим этот

Функции 347

процесс, разделив 2 на 2, чтобы получить 1. Вычисление 1 % 2 дает 1, поэтому следующей цифрой будет 1. В результате имеем 101. Когда вы должны остановиться? Вы останавливаетесь, когда результат деления на 2 оказывается меньше 2, поскольку пока он остается равным 2 или больше, существует еще одна двоичная цифра. Каждое деление на 2 сокращает на одну двоичную цифру, пока не будет достигнут конец. (Если это выглядит запутанным, обратитесь к десятичной аналогии. Остатком отделения 628 на 10 является 8, следовательно, 8 — последняя цифра. Целочисленное деление на 10 дает 62, а остаток от деления 62 на 10 равен 2, поэтому следующей цифрой будет 2 и т.д.) Описанный подход реализован в листинге 9.8.

Листинг 9.8. Программа binary.с

Функция to_binary() должна отображать символ ‘0’, если числовое значение переменной г равно 0, и ‘1', если оно равно 1. Условное выражение г == 0 ? 'С : ‘1' обеспечивает такое преобразование числовых значений в символьные.

Ниже показан результаты пробного запуска:

Введите целое число (q для завершения):

9

Двоичный эквивалент: 1001

Введите целое число (q для завершения):

255

Двоичный эквивалент: 11111111 Введите целое число (q для завершения):

1024

Двоичный эквивалент: 10000000000 Введите целое число (q для завершения):

q

Программа завершена.

348 Глава 9

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

преимущества и недостатки рекурсии

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

Числа Фибоначчи можно определить следующим образом: первое число Фибоначчи — это 1, второе число Фибоначчи — тоже 1, а каждое последующее число Фибоначчи представляет собой сумму двух предшествующих чисел. Таким образом, первые несколько чисел в последовательности выглядят так: 1, 1,2, 3, 5, 8, 13. Числа Фибоначчи пользуются особой любовью у математиков; издается даже специальный журнал, посвященный таким числам. Однако не будем углубляться в это. Давайте создадим функцию, которая для заданного положительного целого чис ла n возвращает соответствующее число Фибоначчи.

Вначале отметим преимущество рекурсии: она обеспечивает простое определение. Если мы назовем функцию Fibonacci() , то Fibonacci(n) должна возвращать значение 1, если n равно 1 или 2, и сумму Fibonacci (п-1) и Fibonacci (п—2) в противном случае:

unsigned long Fibonacci(unsigned n)

{

if (n > 2)

return Fibonacci(n-1) + Fibonacci(n — 2); else

return 1;

}

Рекурсивная функция С просто повторяет математическое определение рекурсии. В этой функции используется Двойная рекурсия, т.е. вызывает еебя дважды. Это обстоятельство является источником ее слабости.

Чтобы увидеть природу этой слабости, предположим, что имеется вызов Fibonacci (4 0). Это будет первый уровень рекурсии, и он выделяет память для переменной по имени n. Затем он вызывает функцию Fibonacci() два раза, создавая на втором уровне рекурсии еще две переменных n. Каждый из этих двух вызовов генерирует еще два вызова, которые, в свою очередь, требуют еще четырех переменных с именами n на третьем уровне рекурсии, что в сумме дает семь переменных. На каждом уровне количество переменных удваивается по сравнению с предыдущим уровнем, т.е. объем переменных возрастает по экспоненте! Как вы могли убедиться на примере с пшеничными зернами в главе 5, экспоненциальное возрастание быстро приводит к огромным значениям. В рассматриваемом случае экспоненциальное возрастание быстро приводит к тому, что компьютеру потребуется гигантский объем памяти, что, скорее всего, приведет к аварийному завершению программы.

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

Функции 349

Все функции С созданы равными друг другу

Каждая функция С в программе имеет равное положение с остальными функциями. Каждая из них может вызывать любую другую функцию или быть вызванной в других функциях. Это делает функции С несколько отличающимися от процедур в языках Pascal и Modula-2, поскольку упомянутые процедуры могут быть вложенными друг в друга. Процедурам в одном вложении ничего не известно о процедурах в другом вложении.

Не является ли функция main() особенной? Да, ее особенность в том, что когда программа, состоящая из нескольких функций, собирается вместе, выполнение начинается с первого оператора в main(), но этим ее отличие и ограничивается. Даже функция main() может вызывать саму себя рекурсивно или быть вызванной из других функций, хотя подобное встречается редко.

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

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