3. Нерекурсивное решение (динамическое программирование)
На самом деле несложно видеть, что значения рекурсивной функции в данном случае будут совпадать с числами Фибоначчи, так как
вычисляются по тем же рекуррентным соотношениям.
А для вычисления чисел Фибоначчи можно использовать цикл, а не рекурсию — следующее число Фибоначчи определяется, как сумма
двух предыдущих.
Пример на языке Python
F = [0] * (n + 1)
F[0] = 1
F[1] = 1
for i in range(2, n + 1):
F[i] = F[i - 2] + F[i — 1]
Пример на языке Pascal
var
F: array[0..100] of longint;
i, n: longint;
begin
readln(n);
for i := 1 to n do
F[i] := 0;
F[0] := 1;
F[1] := 1;
for i := 2 to n do
F[i] := F[i - 1] + F[i - 2];
writeln(F[n]);
end.
Сложность такого решения будет O(n).
Сложность вычисления уменьшается за счет того, что для каждого промежуточного i значение F(i) вычисляется один раз и сохраняется
в списке, чтобы впоследствии использовать это значение несколько раз для вычисления F(i + 1) и F(i + 2).
Такой прием называется динамическим программированием.
Динамическое программирование использует те же рекуррентные соотношения, что и рекурсивное решение, но в отличии от рекурсии в
динамическом программировании значения вычисляются в цикле и сохраняются в списке.
При этом заполнение списка идет от меньших значений к большим, в то время как в рекурсии — наоборот, рекурсивная функция вызывается
для больших значений, а затем вызывает сама себя для меньших значений.