Листинг 5.10. Пример использования рекурсии для нахождения члена ряда Фибоначчи

1: #include < iostream.h>

2:

3: int fib (int n);

4:

5: int main()

6: {

7:

8: int n, answer;

9: cout < < " Enter number to find: "; 10: cin > > n;

10:

11: cout < < " \n\n";

12:

13: answer = fib(n);

14:

15: cout < < answer < < " is the " < < n < < " th Fibonacci number\n"; 17: return 0,

16: }

17:

18: int fib (int n)

19: {

20: cout < < " Processing fib(" < < n < < ")... "; 23:

21: if (n < 3)

22: {

23: cout < < " Return 1! \n";

24: return (1);

25: }

26: else

27: {

28: cout < < " Call fib(" < < n-2 < < ") and fib(" < < n-1 < < ").\n";

29: return(fib(n-2) + fib(n-l));

30: }

31: }

Результат:

Enter number lo find: 6

Processing fib(6)... Call fib(4) and fib{S)

Processing fib(4)... Call fit> (2) and fib(3)

Processing fib(2)... Return 1!

Processing fib(3)... Call fib(l) and fiO< 2)

Processing fib(D... Return 1!

Processi ng fib(2)... Return 1!

Processing fib(5)... Call fib(3) and fib{4)

Processing fib(3}... Call fib(1) and fib(2)

Processing flb(1)... Return 1!

Processi ng fib(2)... Return 1!

Processing fib(4)... Call fib(2) and fib(3)

Processing fib(2)... Return 1!

Processing fib(3)... Call fib(1) and fib(2)

Processing fib(l)... Return 1!

Processing fib(2)... Return 1!

8 is the 6th Fibonacci number

Примечание: Некоторые компиляторы испытывают затруднения с использованием операторов в выражениях с объектом cout. Если вы получите предупреждение в строке 28, заключите операцию вычитания в круглые скобки, чтобы строка 28 приняла следующий вид:

28: cout < < " Call fib(" < < (n-2) < < ") and fib(" < < n-1 < < ").\n";

Анализ: В строке 9 программа предлагает ввести номер искомого члена ряда и присваивает его переменной n. Затем вызывается функция fib() с аргументом n. Выполнение программы переходит к функции fib(), где в строке 20 этот аргумент выводится на экран.

В строке 21 проверяется, не меньше ли аргумент числа 3, и, если это так, функция fib() возвращает значение 1. В противном случае выводится сумма значений, возвращаемых при вызове функции fib() с аргументами n-2 и п-1. Таким образом, эту программу можно представить как циклический вызов функции fib(), повторяющийся до тех пор, пока при очередном вызове этой функции не будет возвращено некоторое значение. Единственными вызовами, которые немедленно возвращают значения, являются вызовы функций fib(1) и fib(2). Рекурсивное использование функции fib() проиллюстрировано на рис. 5.4 и 5.5.

В примере, изображенном на рисунках, переменная n равна значению 6, поэтому из функции main() вызывается функция fib(6). Выполнение программы переходит в тело функции fib(), и в строке 30 значение переданного аргумента сравнивается с числом 3. Поскольку число 6 больше числа 3, функция fib(6) возврашает сумму значений, возвращаемых функциями fib(4) и fib(5):

38: return(fib(n-2) + fib(n-1));

Это означает, что выполняется обращение к функциям fib(4) и fib(5) (поскольку переменная n равначислу 6, то fib(n-2) — это то же самое, что fib(4), а fib(n-1) — то же самое, что fib(5)). После этого функция fib(6), которой в текущий момент передано управление программой, ожидает, пока сделанные вызовы не возвратят какое-нибудь значение. Дождавшись возврата значений, эта функция возвратит результат суммирования этих двух значений.

Рис. 5.4. Использование рекурсии

Рис. 5.5. Возвращение из рекурсии

Поскольку при вызове функции fib(5) передается аргумент, который не меньше числа 3, функция fib() будет вызываться снова, на этот раз с аргументами 4 и 3. А функция flb(4) вызовет, в свою очередь, функции fib(3) и fib(2).

Результаты и промежуточные этапы работы программы, представленной в листинге 5.10, выводятся на экран. Скомпилируйте, скомпонуйте и выполните эту программу, введя сначала число 1, затем 2, 3, и так доберитесь до числа 6, внимательно наблюдая за отображаемой информацией.

Работа с этой программой предоставляет вам прекрасный шанс проверить возможности своего отладчика. Разместите точку останова в строке 20, а затем заходите в тело каждой вызываемой функции fib(), отслеживая значение переменной n при каждом рекурсивном вызове функции fib().

В программировании на языке C++ рекурсия не частый гость, но в определенных случаях она является мощным и весьма элегантным инструментом.

Примечание: Рекурсия относится к одной из самых сложных тем программирования. Данный раздел полезен для понимания основных идей ее реализации, однако не следует слишком расстраиваться, если вам не до конца ясны все детали работы рекурсии.