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

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

Рис. 9.4. Переменные рекурсии

344 Глава 9

Переход сразу же к первоначальному вызову внутри main() не происходит. Вместо этого управление должно пройти через каждый уровень рекурсии, возвращаясь с одного уровня up and down() на уровень функции up_and_down(), которая ее вызвала.

В-третьих, операторы в рекурсивной функции, которые предшествуют рекурсивному вызову, выполняются в том же самом порядке, в каком эти функции вызывались. Например, в листинге 9.6 первый оператор вывода находится перед рекурсивным вызовом. Он был выполнен четыре раза в порядке следования рекурсивных вызовов: уровень 1, уровень 2, уровень 3 и уровень 4.

В-четвертых, операторы в рекурсивной функции, которые находятся после рекур сивного вызова, выполняются в порядке, обратном тому, в каком эти функции вызывались. Например, второй оператор вывода располагается после рекурсивного вызова, и он выполнялся в следующем порядке: уровень 4, уровень 3, уровень 2, уровень 1. Это свойство рекурсии полезно при программировании задач, предусматривающих изменение порядка на противоположный. Вскоре вы увидите пример.

В-пятых, хотя каждый уровень [>екурсии обладает собственным набором переменных, сам код не дублируется. Код — это последовательность инструкций, а вызов функции представляет собой команду перехода на начало этой последовательности инструкций. Рекурсивный вызов затем возвращает программу в начало упомянутой последовательности инструкций. Если не обращать внимания на то, что рекурсивные вызовы создают новые переменные при каждом вызове, они во многом напоминают цикл. На самом деле временами рекурсия может быть использована вместо цикла и наоборот.

Наконец, в-щестых, очень важно, чтобы рекурсивная функция содержала код, который мог бы остановить последовательность рекурсивных вызовов. Обычно в рекурсивной функции применяется проверка if или ее эквивалент для прекращения рекурсии, когда какой-то параметр функции достигает определенного значения. Чтобы это работало, в каждом вызове должно использоваться отличающееся значение для этого параметра. В последнем примере функция up and down (n) вызывает up and down (n+1). В итоге фактический аргумент достигает значения 4 и проверка условия if (n < 4) не проходит.

Хвостовая рекурсия

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

Давайте рассмотрим версии с циклом и хвостовой рекурсией для функции вычисления факториала. Факториал целого числа — это результат произведения всех целых чисел, начиная с 1 и заканчивая заданным числом. Например, факториал 3 (записывается как 3!) соответствует произведению 1*2*3. Кроме того, 0 ! принимается равным 1, а для отрицательных чисел факториалы не определены. В листинге 9.7 в одной функции для вычисления факториала применяется цикл for, а во второй функции — рекурсия.

Листинг 9.7. Программа factor.с

Функции 345

Программа тестового драйвера ограничивает входные данные целыми значениями в диапазоне от 0 до 12. Оказывается, что значение 12 ! немного меньше полумиллиарда, поэтому результат 13! занимает значительно больше памяти, чем тип long в нашей системе. Для вычисления факториалов, превосходящих 12 !, придется использовать тип большего размера, такой как double или long long.

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

Эта программа вычисляет факториалы.

Введите значение в диапазоне 0-12 (q для завершения):

5

цикл: факториал 5 = 120

рекурсия: факториал 5 = 120

Введите значение в диапазоне 0-12 (q для завершения) :

10

цикл: факториал 10 = 3628800

рекурсия: факториал 10 = 3628800

Введите значение в диапазоне 0-12 (q для завершения) :

q

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

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.