Числа Фибоначчи

При работе с циклами итерации, нужно быть очень осторожным, чтобы не попасть в бесконечный цикл.

Точно так же для рекурсии, мы должны быть осторожны, чтобы не создавать бесконечную цепочку рекурсивных вызовов метода.

Вот несколько примеров, где вы можете попасть в неприятности.

Посмотрите на этот первый пример и подумайте о том, где тут может быть проблема.

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

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

Что об этом втором примере?

Это выглядит очень похоже на то, что мы видели в вычислении n факториала.

Проблема в том, что n+ 1 используется здесь по ошибке.

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

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

Последовательность Фибоначчи впервые появилась в 13 веке.

Когда наблюдался рост популяции кроликов, было установлено, что рост следует следующему шаблону:

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

– Каждая новая пара становится половозрелой через один месяц после рождения, и самка будет производить еще одну пару кроликов через месяц;

– И далее, предположим, что ни один из кроликов не умрет в этом году.

Вопрос в том, сколько пар кроликов будет через год.

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

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

Так что будет 3 пары кроликов в конце 2-го месяца.

В конце 3-го месяца, две пары взрослых кроликов каждая родит пару новорожденных, то есть будет 2 дополнительные пары или 5 пар вместе.

И пара, родившаяся во 2-й месяц, теперь стала половозрелой.

Такой рост популяции может быть показан на этом рисунке здесь, начиная от пары крольчат.

Числа Фибоначчи, как полагают, моделируют природу определенным образом, и есть другие природные феномены, которые напоминают последовательность Фибоначчи, например, наблюдение Кеплером листьев и цветов в 17 веке в его исследовании симметрии.

Вот некоторые из первых чисел Фибоначчи.

Если вы посмотрите на эту последовательность чисел более тщательно, вы можете найти, что каждое из этих чисел может быть получено как сумма двух чисел, предшествующих им.

Например, 2 получается путем сложения 1 и 1, 3 получают путем сложения 1 и 2, 5 получают путем сложения 2 и 3, 8, добавляя 3 к 5, и так далее.

В общем, энное число Фибоначчи можно определить рекурсивно, путем суммирования (n -1) и (n – 2) чисел Фибоначчи.

И базовый случай определен для n = 0 и n = 1 со значениями, равными 0 и 1 соответственно.

Вот реализация Java для числа Фибоначчи.

Фактический метод вычисления числа Фибоначчи является методом, который принимает один параметр n и возвращает целое число, представляющее число Фибоначчи.

Метод main реализован ниже, просто, чтобы позволить ввод различных значений n для проверки метода.

Обратите внимание, что метод объявлен статическим, так что нам не нужно создавать объект, прежде чем использовать этот метод.

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

График здесь показывает последовательность шагов в рекурсивных вызовах метода.

Хотя FIB(4) будет вызывать как FIB(3) так и FIB(2), так как каждый из них должен быть выполнен последовательно, FIB (3) должен быть вычислен в первую очередь.

FIB(2) будет затем вызвать FIB(1) и FIB(0), и так как оба представляют собой базовые случаи, будут возвращены целочисленные результаты.

Затем вычисление возвратится к FIB(3), который требует вычисления FIB(1), и так как это снова базовый вариант, значение для FIB(3) может быть определено.

И далее будет попытка завершить расчет для FIB(4) путем вычисления FIB(2).

Процесс будет продолжаться до тех пор, пока значения для FIB(3) и FIB(2) не будут получены для определения конечного значения для FIB(4).

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

Например, FIB(1) повторно вычисляется 3 раза, FIB(2) повторно вычисляется 2 раза и так далее.

Подобно задаче рукопожатия, есть также другая форма решения для вычисления чисел Фибоначчи.

Хотя это намного сложнее.

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

Давайте теперь откроем IDEA чтобы посмотреть на фактическое выполнение программы.

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

Давайте скомпилируем и запустим программу.

При попытке запустить программу, используя небольшое значение n = 4, вы сможете обнаружить, что четвертый номер Фибоначчи это 3.

Когда мы пытаемся ввести большее число, скажем, 42, и вы можете увидеть, что нужно немного подождать, прежде чем результат возвратится.

Вы должны ждать пару секунд, прежде чем возвратится результат.

Если вы посмотрите на результаты, можно увидеть, что число Фибоначчи для 42 это сумма числа Фибоначчи для 40, что составляет около 100 млн., и число Фибоначчи для 41, что будет примерно 165 млн.

Если сложить их, вы получите около 267 млн.

Когда вы захотите вычислить число Фибоначчи для n, равным 45, вы найдете, что это займет много времени, прежде чем вы увидите результат.