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

Пропуск базовой задачи или неправильная запись шага рекурсии, из-за чего процесс не сходится к базовой задаче, приводят к бесконечной рекурсии и существенным затратам памяти. Это аналог бесконечного цикла в итеративном (нерекурсивном) процессе. Бесконечная рекурсия может быть также вызвана вводом неправильной величины.