SoftCraft
разноликое программирование

Top.Mail.Ru

Яндекс.Метрика

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


© 2018
А.И. Легалов

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

Существует формула, определяющая числа Фибоначчи следующим образом:

F(0) = 1
F(1) = 0
F(n) = F(n-1) + F(n-2)

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

n = int(input('n = ? '))

F0 = 1
F1 = 1
for i in range(1, n):
    F0, F1 = F1, F0 + F1

print (F1)

Возникают вопросы:

  • Каким образом данное решение взаимосвязано с используемым рекурсивным определением?

  • Можно ли получить итеративное решение из рекурсивного формальным путем?

Попробуем рассуждать от противного. Глядя на исходную формулу, можно увидеть, что F(n-2) можно использовать для получения F(n-1):

F(n-1) = F(n-2) + F(n-3)

Тогда, можно осуществить подстановку:

F(n) = F(n-2) + F(n-3) + F(n-2) = 2*F(n-2) + F(n-3)

Эти подстановки можно продолжить до конца, получив в качестве последних значений F(1) и F(0), образуя, тем самым, последовательность итеративных преобразований. Весь ряд подстановок будет выглядеть следующим образом:

F(n) = F(n-1) + F(n-2) =
     = 2 * F(n-2) + F(n-3) =
     = 2 * (F(n-3) + F(n-4)) + F(n-3) = 3 * F(n-3) + 2 * F(n-4) =
     = 3 * (F(n-4) + F(n-5)) + F(n-4) = 5 * F(n-4) + 3 * F(n-5) = ...
...  = P * F(1) + Q * F(0)

Так как F(1) = F(0) = 1, то F(n) = P + Q.

Простой анализ показывает, что коэффициент перед первым слагаемым F(i) равен сумме коэффициентов предшествующей подстановки, стоящих перед F(i+1) и F(i), а коэффициент перед F(i-1) равен коэффициенту перед первым слагаемым F(i+1) предшествующей подстановки:

F(n) = ... = x * F(i+1) + y * F(i) =
     = x * (F(i) + F(i-1)) + y * F(i) =
     = x * F(i) + x * F(i-1) + y * F(i) =
     = (x + y) * F(i) + x * F(i-1)

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

n = int(input('n = ? '))

x = 1
y = 0
while n > 1:
    x, y = x+y, x
    n -= 1

print(x+y)

При n = 2: x+y = 2

При n = 3: x+y = 3

...

Замена цикла while на for и перебор от начального значения позволяет получить программу, эквивалентную уже написанному итеративному решению:

n = int(input('n = ? '))

x = 1
y = 0
for i in range(1, n):
    x, y = x+y, x

print(x+y)

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

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