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

346 Глава 9

Версия с циклом инициализирует переменную ans значением 1, а затем умножает ее на целые числа от n до 2. Формально следовало бы умножить также и на 1, но результат от этого не изменится.

Теперь взглянем на рекурсивную версию. Ключевым моментом является уравнение n! = n * (n-1) !. Оно следует из того факта, что (n-1) ! представляет собой произведение всех положительных целых чисел до n-1. Таким образом, умножение его на n дает произведение целых чисел вплоть до n. Это хорошо вписывается в рекурсивный подход. Если вы назовете функцию rfact(), то rfact (n) соответствует n * rf act (n-1). Следовательно, вычислить значение rfact (n) можно, вызвав в ней rfact (n-1), как делается в листинге 9.7. Разумеется, вы должны прервать рекурсию в какой-то точке, и это можно сделать, установив возвращаемое значение в 1, когда n равно 0.

Рекурсивная версия программы в листинге 9.7 дает гот же самый результат, что и версия с циклом. Обратите внимание, что хотя вызов rfact() не является последней строкой в функции, это последний оператор, выполняемый, когда n > 0, т.е. мы имеем дело с хвостовой рекурсией.

Учитывая возможность применения в коде функции либо цикла, либо рекурсии, какому подходу должно отдаваться предпочтение? Обычно цикл является более удачным выбором. Во-первых, из-за того, что каждый рекурсивный вызов создает собственный набор переменных, вариант с рекурсией использует больше памяти; каждый рекурсивный вызов помещает в стек новый набор переменных. При этом ограниченный объем стека может устанавливать предел количества рекурсивных вызовов. Во-вторых, рекурсия выполняется медленнее, т.к. каждый вызов функции занимает определенное время. Для чего тогда демонстрировался этот пример? Причина в том, что хвостовая рекурсия является самой простой формой рекурсии для ее понимания, а рекурсия заслуживает освоения, поскольку в ряде случаев простая альтернатива в виде цикла отсутствует.

Рекурсия и изменение порядка на противоположный

Давайте теперь рассмотрим задачу, для которой способность рекурсии изменять порядок на противоположный оказывается полезной. (Это случай, когда рекурсия проще, чем применение цикла.) Задача заключается в написании функции, которая выводит двоичный эквивалент целого числа. В двоичной записи числа представляются степенями 2. Подобно тому, как 234 в десятичном виде означает 2 х 10 2+ 3 х 10 1+ 4 х 10°, число 101 в двоичном виде 1 х 2 2+ 0 х 2 1+ 1 х 2°. В двоичных числах используются только цифры 0 и 1.

Для решения задачи необходим некоторый метод, или алгоритм. Скажем, каким образом можно найти двоичный эквивалент 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.с