© 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 раза, сводя, в конце концов весь процесс к линейному.
В данном случае все гораздо проще, чем переход к итеративному алгоритму задачи о Ханойских башнях, не использующему стек.
|