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

Функция 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() может вызывать саму себя рекурсивно или быть вызванной из других функций, хотя подобное встречается редко.