Странная петля Фибоначчи: красота математического начала

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

Говоря об алгоритмах, нельзя не упомянуть о последовательности Фибоначчи. Она тесно связана с золотым сечением, которое мы снова и снова встречаем в природе, архитектуре, искусстве и даже романе Дэна Брауна. От раковин морских животных до сакральной геометрии, по-видимому, Золотое Сечение закодировано во многих аспектах нашей Вселенной.

Невозможно перечислить все места, где мы можем встретить эту удивительную последовательность, но самое невероятное – она появляется даже внутри самой себя. Рекурсия внутри рекурсии, математическое начало, то, что Хофштадтер мог бы назвать "странной петлей" (strange loop).

В информатике последовательность – и различные стратегии ее вычисления – это хорошие обучающие инструменты. Последовательность Фибоначчи может быть вычислена с помощью простой рекурсии:

def fib(n):
    if n <= 1:
        return 1

    return fib(n - 2) + fib(n - 1)

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

Последовательность была описана в 1202 году Леонардо Фибоначчи. Она начинается с двух единиц, а последующие члены вычисляются путем сложения двух предыдущих. Третий член 1 + 1 = 2, а четвертый 1 + 2 = 3, далее 2 + 3 = 5. Вот первые несколько цифр:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 …

Рекурсивный код выше означает следующее: если n равно 0 или 1, функция вернет единицу, иначе – результат сложения fib(n-1) и fib(n-2), то есть сумму двух предыдущих членов.

Ряд Фибоначчи и золотое сечение

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

Золотое сечение – иррациональное число. Как и ? (число Пи), оно имеет бесконечное количество цифр после запятой, которые никогда не образуют повторяющихся шаблонов. Большинство из нас помнят ? как 3.14, а золотое сечение можно запомнить как 1.618. Буквенное представление этой величины – ? (фи, Phi).

Если взять n-ный член последовательности Фибоначчи и разделить его на (n-1)-ный, то полученный результат будет приблизительно равен золотому сечению. Чем дальше от начала, тем точнее приближение:

5/3 = 1.666
8/5 = 1.6
13/8 = 1.625
21/13 = 1.61538461538

Ряд Фибоначчи как алгоритмическая сложность

Вероятно, вы знаете, что рекурсивный код работает медленно. А знаете ли вы, что он работает медленно таким образом, который тесно связан с числом ??

Смоделируем наш пример с помощью дерева (так можно представить практически все рекурсивные функции). Каждый вызов – это внутренний узел, а базовые случаи – листья. Дерево для fib(5) выглядит вот так:

Вы можете определить сложность этой функции как O(2ⁿ). Каждый вызов по существу приводит к еще двум вызовам – практически идеальный пример экспоненциального удвоения. Другими словами, дерево, представляющее наш код, имеет коэффициент ветвления 2, каждый узел имеет 2 дочерних элемента, поэтому на каждой глубине число узлов удваивается. Из одного узла получается 2, потом 4, потом 8...

Нотация "большое O" – это нечеткая линза, где оценка одновременно рекомендуется и требуется. Но действительно ли эта функция экспоненциально удваивается? Попробуем измерить время выполнения функции fib, определенной выше:

def time_fib(n):
    start = time.clock()
    digit = fib(n)
    stop = time.clock()

    return digit, (stop - start)


for i in range(1, 100):
    digit, time_elapsed = time_fib(i)
    print("{:3d} {:10d} {:5d}".format(i, digit, round(time_elapsed)))

Даже неуклюжий эмпирический анализ намекает на нашу странную петлю. После 32 итераций измерения приобретают знакомую форму…

n  fib(b)    time_elapsed
32 3524578   1
33 5702887   1
34 9227465   2
35 14930352  3
36 24157817  5
37 39088169  8
38 63245986  13
…

Компьютеры, часы и интерпретаторы неточны, и постепенно значение time_elapsed становится плохим приближением ряда Фибоначчи:

n  fib(b)     time_elapsed
39 102334155  24
40 165580141  37
41 267914296  59
42 433494437  95
43 701408733  155
44 1134903170 253

Тем не менее, даже грязная реализация выявила теоретическую истину. Рекурсивный метод вычисления n-ного члена последовательности Фибоначчи имеет алгоритмическую сложность, которая отражает эту последовательность. Если бы его сложность была O(2ⁿ), количество времени бы удваивалось, но этого не происходит.

Колония бактерий и ряд Фибоначчи

Можно смоделировать сложность этой функции, используя рекуррентное отношение – формальный математический язык для описания рекурсивных функций. Не пугайтесь этого определения, тут все просто:

f (n) = f (n-1) + f (n-2)

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

Возьмем конкретный пример:

f(5) = f(4) + f(3)
f(4) = f(3) + f(2)
f(3) = f(2) + f(1)
f(2) = f(1) + f(0)

И f(1), и f(0) в нашем случае постоянны, так как метод просто возвращает 1. Поэтому можно сказать, что:

f (1) = 1
f (0) = 1

Если сложить все это снизу вверх, получится следующее:

f (2) = 1 + 1 = 2
f (3) = 2 + 1 = 3
f (4) = 3 + 2 = 5
f (5) = 5 + 3 = 8

Вы уже догадываетесь, к чему все это ведет?

Давайте попробуем развернуть формулу для f(5) вместо того, чтобы вставлять в нее реальные значения:

f(5) = f(4) + f(3)
f(5) = [f(3) + f(2)] + [f(2) + f(1)]
f(5) = {[f(2) + f(1)] + [f(1) + f(0)]} + {[f(1) + f(0)] + f(1)}
f(5) = {f(1) + f(0) + f(1) + f(1) + f(0)} + {f(1) + f(0) + f(1)}

Все эти f(0) и f(1) – это листовые узлы дерева, которые имеют константное значение 1.

Можно ли смоделировать это отношение лучшим способом, чем расширение? Возможно ли создать формулу, которая описывается, сколько f(0) и f(1) будет при разложении конкретного f(n)? Оказывается, возможно! Пристегнитесь, мы входим в зону математического анализа.

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

f (n) = 2*f(n-1)

В каждый момент времени каждая бактерия разделяется на две, поэтому популяция увеличивается вдвое по сравнению с предыдущим моментом. Если начать с одной бактерии, в следующий момент будет уже две, затем 4, 8, 16, 32 и так далее. Это экспоненциальная функция f(n) = 2^n.

Вспомним, что умножение – это просто повторяющееся сложение, и увидим, насколько это похоже на последовательность Фибоначчи:

f(n) = 2 * f(n-1) = f(n — 1) + f(n — 1)

И тогда:

f(n) = f(n — 1) + f(n — 1) = 2^n
f(n) = f(n — 1) + f(n — 2) = ???

Есть все основания полагать, что второе выражение также будет расти экспоненциально, но медленнее, чем 2ⁿ. С другой стороны, рекурсивное дерево для функции роста бактерий будет иметь больше узлов, чем дерево для fib, хотя в обоих деревьях у узла либо 2 ребенка, либо ни одного. Они похожи, но не идентичны.

Опять золотое сечение

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

Доказательство этого трюка, называемое "теоремой о различных корнях", можно найти здесь.

Мы знаем, что ряд растет по экспоненте, а этот трюк помогает найти "корни" экспоненциальной функции. Он довольно прост: нужно взять нижние индексы функции f и превратить их в экспоненты по переменной r (root – корень), для которой мы их затем решим.

Применим этот трюк для формулы роста бактерий:

f(n) = 2f(n-1)
r^n = 2r^n-1
r = 2

На последнем шаге мы делим каждую сторону на r^n-1.

Этот трюк приводит к тому же ответу, что был получен выше – экспоненциальный рост колонии 2ⁿ.

Теперь попробуем то же самое для ряда Фибоначчи:

f(n) = f(n-1) + f(n-2)
r^n = r^n-1 + r^n-2
r^2 = r + 1 ; [разделить обе стороны на r^n-2]
r^2 — r — 1 = 0

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

r = [1 +- sqrt(1 — (4*(-1)))] / 2
r = (1 + sqrt(5)) / 2
r = (1 — sqrt(5)) / 2

Произошло нечто удивительное, даже если вы этого не заметили. Посчитайте на калькуляторе 1 + sqrt(5) / 2. Вы получите ... 1.618: ?, золотое сечение. Поразительно.

Чтобы не потерять лес за деревьями, отметим, что это экспериментально демонстрирует экспоненциальный рост последовательности Фибоначчи с корнем экспоненты 1.618.  Если n-ный член, разделенный на (n-1)-ный член приблизительно равен ?, то умножение (n-1)-ного члена на ? будет равно n-ному члену.

Отметим также, что второй корень – это другое замечательное число ? (Psi, пси), которое похоже на золотое сечение и примерно равно -0.618.

Конечно, технически будет правильно сказать, что верхняя граница рекурсивной функции O(2ⁿ), все же гораздо более приятно знать, что более жесткая граница – O(?ⁿ).

Формула Бине

Следующая часть теоремы о корнях говорит о том, что если наша рекурсия является “линейными однородными рекуррентными отношениями с постоянными коэффициентами”, то мы можем не только установить верхнюю границу ее роста (как сделали только что), но и действительно найти короткое решение.

Вы можете самостоятельно доказать этот замечательный факт.

Это формула Бине, позволяющая определить n-ный член последовательности Фибоначчи:

f(n) = (?^n - ?^n) / sqrt(5)

Это невероятно!

Перевод статьи Fibonacci’s Strange Loop: the beauty of mathematical inception by Tyler Elliot Bettilyon

Больше материалов по алгоритмам:

• Наиболее полный видеокурс по алгоритмам и структурам данных
• Анализ алгоритмов для начинающих: вводное руководство
• ТОП-15 алгоритмических задач, реализованных на C++
• Алгоритмы и структуры данных: развернутый видеокурс
• Как научиться решать алгоритмические задачи?