Рекурсивное описание функции факториала unsigned long factorial (unsigned long number) {

if (number <= 1)

return 1; else

return number * factorial(number - 1);

10! = 3628800

Рис. 3.14. Вычисление факториалов с помощью рекурсивной функции

представляет задачу как произведение number и рекурсивного вызова factorial, вычисляющего факториал величины number -1. Отметим, что factorial(num-ber - 1) является упрощенной задачей по сравнению с исходным вычислением factorial(number).

В объявлении функции factorial указано, что она получает параметр типа unsigned long и возвращает результат типа unsigned long. Это является краткой записью типа unsigned long int. Описание языка С-Н- требует, чтобы переменная типа unsigned long int хранилась по крайней мере в 4 байтах (32 битах), и таким образом могла бы содержать значения в диапазоне по крайней мере от О до 4294967295. (Тип данных long int также хранится по крайней мере в 4 байтах и может содержать значения по крайней мере в диапазоне от 2147483647). Как можно видеть из рис. 3.14, значение факториала растет очень быстро. Мы выбрали тип данных unsigned long для того, чтобы программа могла рассчитать числа, большие чем 7!, на компьютерах с маленькими целыми числами (такими, как 2-байтовые). К несчастью, функция factorial начинает вырабатывать большие значения так быстро, что даже unsigned long не позволяет нам напечатать много значений факториала до того, как будет превышен допустимый предел переменной unsigned long.

Рекурсивная функция факториала #include <iostreain.h> iinclude <iomanip.h>

unsigned long factorial(unsigned long);

main() {

for (int i = 0; i <= 10; i++)

cout setw(2) i ! = factorial(i) endl;

return 0;

3.13. Пример использования рекурсии: последовательность чисел Фибоначчи

Последовательность чисел Фибоначчи О, 1, 1, 2, 3, 5, 8, 13, 21, ...

начинается с О и 1 и обладает тем свойством, что каждый последующий член последовательности представляет собой сумму двух предыдущих членов. Эта последовательность часто встречается в природе, в частности она описывает форму спирали. Отношение последовательных чисел Фибоначчи сходится к постоянному числу 1,618... Это число также часто встречается в природе и называется золотым сечением. Люди склонны рассматривать золотое сечение как источник эстетического наслаждения. Архитекторы часто проектируют окна, комнаты и здания так, что их длина и ширина находятся в отношении золотого сечения. В таком же отношении часто находятся длина и ширина почтовых открыток.

Последовательность Фибоначчи можно определить рекурсивно следующим образом:

fibonacci{0) = О fibonacci(1) =1

fibonacci(п) = fibonacci(n - 1) + fibonacci(n - 2)

В программе, приведенной на рис. 3.15, i-e число Фибоначчи вычисляется рекурсивно с помощью функции fibonacci. Заметим, что числа Фибоначчи имеют тенденцию к быстрому росту. Поэтому в функции fibonacci мы выбрали тип unsigned long и для параметра, и для возвращаемого результата. На рис. 3.15 в примере вывода каждая пара строк соответствует одному прогону программы.

Как будет показано в упражнениях, пользователь, желающий вычислить факториалы больших чисел, может оказаться вынужденным использовать типы float и double. Это указывает на слабость большинства языков программирования, а именно, что эти языки нелегко расширить для удовлетворения уникальных требований различных приложений. Как мы увидим в разделе данной книги, посвященном объектно-ориентированному программированию, С-Н- является расширяемым языком, позволяющим, если мы пожелаем, создавать произвольно большие целые числа.

Типичная ошибка программирования 3.17

Забывают возвращать значение из рекурсивной функции, когда оно необходимо. Большинство компиляторов вырабатывает при этом предупреждающее сообщение.

Типичная ошибка программирования 3.18

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

unsigned long result, number;

cout Введите целое число: ;

cin number;

result = f ibonacci (niutiier) ;

cout << Число Фибоначчи( number<< ) = << result endl; return 0;

. Рекурсивное описание функции f ibonacci . s unsigned long f ibonacci (unsigned long n)

if (n == 0 II n == 1)

return n; else

return fibonacci(n - 1) + fibonacci(n - 2);

Введите целое число: О Число Фибоначчи (0) =0

Введите целое число: 1 Число Фибоначчи (1) =1

- Введите целое число: 2 4ei Число Фибоначчи (2) =1

* Введите целое число: 3 Число Фибоначчи (3) = 2

Введите целое число: 4 Число Фибоначчи (4) =3

Введите целое число: 5 Число Фибоначчи (5) =5

V-

Введите целое число: 6 Число Фибоначчи (6) =8

Введите целое число: 10

Число Фибоначчи (10) = 55

- Введите целое число: 20

Число Фибоначчи (20) = 6765

Введите целое число: 30 Число Фибоначчи (30) = 832040

Введите целое число: 35

Число Фибоначчи (35) = 9227465

Рис. 3.15. Рекурсивная генерация чисел Фибоначчи

.li Рекурсивная функция вычисления числа Фибоначчи #include <iostream.h>

unsigned long fibonacci(unsigned long) ; main о