6) Значения, возвращаемые после каждого рекурсивного вызова
Рис. 3.13. Рекурсивное вычисление 5!
Программа на рис. 3.14 использует рекурсию для вычисления и печати факториалов целых чисел от 0 до 10 (выбор типа данных unsigned long будет вскоре объяснен). Рекурсивная функция factorial сначала проверяет, истинно ли условие завершения рекурсии, т.е. меньше или равно 1 значение number. Если действительно number меньше или равно 1, factorial возвращает 1, никаких дальнейших рекурсий не нужно и программа завершает свою работу. Если number больше 1, оператор
return number * factorial (number - 1);
Функции 207
представляет задачу как произведение number и рекурсивного вызова factorial, вычисляющего факториал величины number -1. Отметим, что factorial(num-ber - 1) является упрощенной задачей по сравнению с исходным вычислением factorial(number) .
В объявлении функции factorial указано, что она получает параметр типа unsigned long и возвращает результат типа unsigned long. Это является краткой записью типа unsigned long int. Описание языка С++ требует, чтобы переменная типа unsigned long int хранилась по крайней мере в 4 байтах (32 битах), и таким образом могла бы содержать значения в диапазоне по крайней мере от 0 до 4294967295. (Тип данных long int также хранится по крайней мере в 4 байтах и может содержать значения по крайней мере в диапазоне от 2147483647). Как можно видеть из рис. 3.14, значение факториала растет очень быстро. Мы выбрали тип данных unsigned long для того, чтобы программа могла рассчитать числа, большие чем 7!, на компьютерах с маленькими целыми числами (такими, как 2-байтовые). К несчастью, функция factorial начинает вырабатывать большие значения так быстро, что даже unsigned long не позволяет нам напечатать много значений факториала до того, как будет превышен допустимый предел переменной unsigned long.
// Рекурсивная функция факториала #include <iostream.h> #include <iomanip.h>
unsigned long factorial (unsigned long) ;
main () {
for (int i = 0; i <= 10; i++)
cout « setw(2) « i « "! = " « factorial(i) « endl;
return 0;
// Рекурсивное описание функции факториала unsigned long factorial (unsigned long number) {
if (number <= 1)
return 1 ; else
return number * factorial(number - 1);
0! = 1
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720
7! = 5040
8! = 40320
9! = 362880
10! = 3628800
Рис. 3.14. Вычисление факториалов с помощью рекурсивной функции
208 Глава 3
Как будет показано в упражнениях, пользователь, желающий вычислить факториалы больших чисел, может оказаться вынужденным использовать типы float и double. Это указывает на слабость большинства языков программирования, а именно, что эти языки нелегко расширить для удовлетворения уникальных требований различных приложений. Как мы увидим в разделе данной книги, посвященном объектно-ориентированному программированию, С++ является расширяемым языком, позволяющим, если мы пожелаем, создавать произвольно большие целые числа.
Типичная ошибка программирования 3.17
Забывают возвращать значение из рекурсивной функции, когда оно необходимо. Большинство компиляторов вырабатывает при этом предупреждающее сообщение.
Типичная ошибка программирования 3.18
Пропуск базовой задачи или неправильная запись шага рекурсии, из-за чего процесс не сходится к базовой задаче, приводят к бесконечной рекурсии и существенным затратам памяти. Это аналог бесконечного цикла в итеративном (нерекурсивном) процессе. Бесконечная рекурсия может быть также вызвана вводом неправильной величины.
- 116 Глава 2
- 2.13. Основы повторения, управляемого счетчиком
- 2.14. Структура повторения for (цикл)
- 120 Глава 2
- 122 Глава 2
- 2.15. Пример использования структуры for
- 124 Глава 2
- 126 Глава 2
- 2.16. Структура множественного выбора switch
- Глава 2
- 130 Глава 2
- 132 Глава 2
- 2.17. Структура повторения do/while
- 134 Глава 2
- 2.18. Операторы break и continue
- Глава 2
- 2.19. Логические операции
- 138 Глава 2
- Глава 2
- 2.21. Заключение по структурному программированию
- IfcrpyKTypa (единственный выбор)
- Глава 2
- Глава 2
- 148 Глава 2
- Глава 2
- Глава 2
- Глава 2
- 156 Глава 2
- 158 Глава 2
- 160 Глава 2
- 2.1. А) следование, выбор и повторение, b) if/else. С) управляемым счет чиком или определенным заранее, d) Метку, сигнал, флаг или лож ный сигнал.
- 162 Глава 2
- 164 Глава 2
- 166 Глава 2
- 168 Глава 2
- 170 Глава 2
- 172 Глава 2
- 174 Глава 2
- 176 Глава 2
- 178 Глава 3
- Глава 3
- 3.3. Математические библиотечные функции
- 3.4. Функции
- Глава 3
- 3.5 Определения функций
- 184 Глава 3
- 186 ГлаваЗ
- 3.6. Прототипы функций
- 188 Глава 3
- 3.7. Заголовочные файлы
- 3.8. Генерация случайных чисел
- Глава 3
- 192 Глава 3
- 194 Глава 3
- 3.9. Пример: азартная игра
- Глава 3
- 198 Глава 3
- 3.10. Классы памяти
- 200 Глава 3
- 3.11. Правила, определяющие область действия
- 202 Глава 3
- 204 Глава 3
- 3.12 Рекурсия
- Глава 3
- 6) Значения, возвращаемые после каждого рекурсивного вызова
- 3.13. Пример использования рекурсии: последовательность чисел Фибоначчи
- Глава 3
- 3.14. Рекурсии или итерации
- 212 Глава 3
- Глава 3
- Глава 4
- Глава 5
- Глава 6
- 3.15. Функции с пустыми списками параметров
- 214 Глава 3
- 3.16. Встраиваемые функции