Функции в С++ для начинающих. Рекурсия. Числа Фибоначчи

К сведению:

  • Ряд Фибоначчи: 0 1 1 2 3 5 8 13 21 …
  • Ряд Фибоначчи начинается с 0 и 1 и обладает тем свойством, что каждое последующее число Фибоначчи представляет собой сумму двух предыдущих.
Один из классических примеров рекурсии — программа, вычисляющая ряд Фибоначчи. В этой статье как раз показывается код программы, вычисляющей числа Фибоначчи.
Ряд Фибоначчи можно рекурсивно определить следующим образом:
fibonacci( 0 ) = 0
fibonacci( 1 ) = 1
fibonacci( n ) = fibonacci( n — 1 ) + fibonacci( n — 2 )
Пример кода:

Внутри main использован обычный цикл. Он используется для того, чтобы посмотреть числа Фибоначчи по нескольким значениям сразу. Первый вызов функции fibo(int) не считается рекурсивным (что на самом деле логично, ведь не fibo(int) вызвало fibo(int)). А дальше идут проверки и при необходимости новые вызовы. Внутри функции задействуются два результата вычислений, которые складываются между собой. При этом каждое из двух вычислений происходит рекурсивным образом.
ВНИМАНИЕ!

  • В отличие от обычных способов сложения, в показанном коде в качестве слагаемых используются вызовы функций.
    Первым может сработать как вызов fibo(n — 1), так и вызов fibo(n-2). Ни в коем случае не полагайтесь на порядок выполнения (слева-направо или справа-налево) в таких случаях.
Неправильная оценка вами порядка выполнения может поспособствовать неправильному написанию программы, ошибку которой тяжело заметить.
На заметку:

  • Слева-направо гарантировано только для четырёх операций: || && ?:. И это при условии, что эти операции применяются не к пользовательскому классу, а к фундаментальным типам данных.
У операции ?: первым всегда оценивается самый левый операнд; если результат его оценки ненулевой (истинный), то следующим оценивается средний операнд, а последний операнд игнорируется; если же результат оценки самого левого операнда равен нулю (ложный), то следующим оценивается третий операнд, а средний игнорируется.
Немножко я отвлёкся. Но вы обязательно должны принять тот факт, что нельзя полагаться на порядок выполнения вызовов функций в кодах, похожих на показанный.
  • Написание программ, которые предполагают определенный порядок оценки операндов операций, отличных от && || , ?:, может приводить к логическим ошибкам.
  • Программы, предполагающие определенный порядок оценки операндов операций, отличных от && || , ?:, могут работать по-разному на системах с различными компиляторами.
Вернёмся к коду. Смотрим на код, вспоминаем, что там такое написано. Поскольку мы используем, так сказать, двойную рекурсию, то каждый новый рекурсивный шаг удваивает число экземпляров функции в памяти. А это обозначает, что память очень быстро забивается. Число рекурсивных вызовов, необходимых для вычисления n-го числа Фибоначчи, оказывается порядка 2n. Объем работы нарастает слишком быстро. Вычисление только 20-го числа Фибоначчи требует порядка 220, или около миллиона вызовов, вычисление 30-го числа Фибоначчи требует порядка 230, или около миллиарда вызовов и т. д. В теории численных методов это называется экспоненциальной сложностью. Проблемы такого рода не под силу даже самым мощным компьютерам в мире! Вопросы сложности вообще, и экспоненциальной сложности в частности, детально рассматриваются в специальных курсах, обычно называемых "Алгоритмы".
  • Избегайте рекурсивных программ, подобных программе для чисел Фибоначчи, которые приводят к "экспоненциальному взрыву" вызовов.
Использованные материалы:

Все комментарии на сайте проверяются, поэтому ваш комментарий может появиться не сразу. Для вставки кода в комментарий используйте теги: [php]ВАШ_КОД[/php]

4 комментария: Функции в С++ для начинающих. Рекурсия. Числа Фибоначчи

  • Anonymous говорит:

    Не работает




    0



    0
  • Gen говорит:

    Все работает!По крайней мере до 40,но ведь это же пример!В кодеблок хедер #include надо заменить на #include подключить пространство имен using namespace std; ну и заменить void main() на int main() и все работает.
    Краткость сестра таланта.Спасибо.

    Аня говорит:
    16.10.2013 в 6:15

    все равно не работает, даже с исправлением указанных ошибок

    Автор сайта отвечает:
    Здесь ошибок нет.
    Меня никто ни о чем здесь не спрашивал.

    Это вам, Аня




    0



    0
  • Неизвестный говорит:

    Вы КАКАШКА!!!!!




    0



    0
  • Аноним говорит:

    Вы КАКАШКА!!!!!




    0



    0

Добавить комментарий

Ваш e-mail не будет опубликован.

Поиск

 
     

Случайная книга в электронном формате

Яндекс.Метрика
НАГРАДИ АВТОРА САЙТА
WEBMONEY
R375024497470
U251140483387
Z301246203264
E149319127674

Демотиватор

Выражаю свою признательность

  • Максиму очень признателен за указание на мои ошибки и неточности.
  • Sergio ===> за оказание помощи в исправлении моих ошибок
  • Gen ===> за правильное стремление помочь другим новичкам и выявления моих ошибок