Глава 3

Вызов fibonacci из main не рекурсивный, но все последующие вызовы fibonacci рекурсивны. При каждом вызове fibonacci она сначала проверяет, не является ли задача базовой, для которой n равно 0 или 1. Если да, то возвращается n. Интересно, что при n большем 1, шаг рекурсии генерирует два рекурсивных вызова, каждый из которых представляет собой несколько упрощенную задачу по сравнению с исходным вызовом fibonacci. На рис. 3.16 показано, как функция fibonacci вычисляет fibonacci(3) — мы обозначаем fibonacci просто как f, чтобы рисунок легче читался.

Этот рисунок ставит некоторые интересные вопросы о последовательнос­ти, в которой компилятор С++ будет вычислять операнды заданных опера­ций. Это отличается от вопроса о последовательности выполнения операций, диктуемой правилами старшинства операций. Из рис. 3.16 видно, что для вычисления f(3) нужно выполнить два рекурсивных вызова, а именно, f(2) и f(l). Но в каком порядке должны быть сделаны эти вызовы?

Большинство программистов просто полагает, что операнды будут вы­числяться слева направо. Странно, но С++ не оговаривает порядок, в котором должны вычисляться операнды большинства операций, включая +. Поэтому программист не может делать каких-либо предположений о последователь­ности, в которой будут выполняться эти вызовы. Эти вызовы в действитель­ности могут выполняться в любом порядке: сначала f(2), а потом f(l), или наоборот — сначала f(l), а потом f(2). В этой и большинстве других программ результат не зависит от последовательности вычислений. Но в некоторых программах вычисления операндов могут иметь побочный эффект, который может повлиять на окончательный результат выражения. Язык С++ опре­деляет порядок вычисления операндов только для четырех операций — а именно, &&, ||, последования (,) и ?:. Для первых трех бинарных операций операнды гарантированно вычисляются слева направо. Последняя операция — единственная тернарная операция в С++. Ее самый левый операнд всегда выполняется первым; если результат его вычисления отличен от нуля, то следующим вычисляется средний операнд, а последний операнд игнорирует­ся; если же результат вычисления самого левого операнда равен нулю, то следующим вычисляется третий операнд, а средний операнд игнорируется.

Рис. 3.16. Последовательность рекурсивных вызовов функции fibonacci

функции 211

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

Написание программ, которые зависят от последовательности вычисления операндов каких-то операций, отличных от &&, ||, поспедования ( ,) и ?:, может привести к ошибкам, потому что компиляторы могут вычислять операнды не в той последова тельности, которую ожидает программист.

Замечание по мобильности 3.2

Программы, которые зависят от последовательности вычисления операндов опера ций, отличных от &&, ||, последования ( ,) и ?:, могут по-разному работать в системах с различными компиляторами.

Нужно учитывать одну особенность, характерную для рекурсивных про­грамм, подобных той, которую мы использовали для генерации чисел Фи­боначчи. Каждый уровень рекурсии в функции fibonacci удваивает количе­ство вызовов, так что количество рекурсивных вызовов, которое должно быть выполнено для вычисления n-ro числа Фибоначчи, оказывается порядка 2^П. Объем вычислений резко нарастает с увеличением n. Вычисление только 20-го числа Фибоначчи потребовало бы порядка 2 или около миллиона вызовов, вычисление 30-го числа Фибоначчи потребовало бы порядка 2 или около миллиарда вызовов и так далее. В методах вычислений это называется экс­поненциальной сложностью. Проблемы такого рода не по плечу даже самым мощным компьютерам в мире! Вопросы сложности в целом и экспоненци­альной сложности в частности детально рассматриваются на верхнем уровне обучения в курсах, обычно называемых «Алгоритмы».

Совет по повышению эффективности 3.4

Избегайте рекурсивных программ, подобных программе для вычисления чисел Фи­боначчи, которые приводят к экспоненциальному нарастанию количества вызовов.