Стивен Прата - Язык программирования 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

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