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

Последовательность чисел Фибоначчи

0, 1, 1, 2, 3, 5, 8, 13, 21, ...

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

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

fibonacci(0) = 0 fibonacci(l) = 1 fibonacci(n) = fibonacci(n - 1) + fibonacci(n - 2)

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

функции 209

// Рекурсивная функция вычисления числа Фибоначчи

#include <iostream.h>

unsigned long fibonacci(unsigned long);

main ()

unsigned long result, number;

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

cin » number;

result = fibonacci(number);

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

return 0;

// Рекурсивное описание функции fibonacci unsigned long fibonacci(unsigned long n)

if (n == 0 || n == 1)

return n; else

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

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

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

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

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

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

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

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

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

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

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

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

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

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

210