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

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

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

return

f (2)

f (1)

turn f(l) + f(0)

return 1

return 1

return 0

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

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

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

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

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

3.14. Рекурсии или итерации

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

Как итерации, так и рекурсии основаны на управляющей структуре: итерации используют структуру повторения, рекурсии используют структуру выбора.

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

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

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

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

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

Рекурсия имеет много недостатков. Повторный запуск рекурсивного механизма вызовов функции приводит к росту накладных расходов: к нарастающим затратам процессорного времени или требуемого объема памяти. Каждый рекурсивный вызов приводит к созданию новой копии функции (на самом деле копируются только переменные данной функции); для этого может потребоваться значительная память. Итерации обычно не связаны с функциями, так что в них отсутствуют накладные расходы на повторные вызовы функции и дополнительные затраты памяти. Тогда для чего же применять рекурсию?

Замечание по технике программирования 3.13

Любые задачи, которые можно решить рекурсивно, могут быть решены также и итеративно (нерекурсивно). Обычно рекурсивный подход предпочитают итеративному, если он более естественно отражает задачу и ее результаты, то есть более нагляден и легче отлаживается. Другая причина предпочтения рекурсивного решения состоит в том, что итеративное решение может не быть очевидным.

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

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

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

Случайный вызов нерекурсивной функции самой себя либо непосредственно, либо косвенно, через другую функцию.

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

Давайте посмотрим еще раз на многочисленные советы, которые мы даем в этой книге. Хорошая техника программирования важна. Часто важна и высокая производительность. К несчастью, эти цели часто не совместимы друг с другом. Хорошая техника программирования - это ключевой момент в вопросе управления созданием все более сложных и крупных программных систем. Высокая производительность этих систем - ключ к созданию систем будущего, которые предъявят еще большие требования к аппаратным средствам. Что же важнее?

Замечание по технике программирования 3.14

Функционализация программ в четком иерархическом стиле - свидетельство хорошей техники программирования. Но за все надо платить.