Можно немного модифицировать этот алгоритм так, чтобы он работал по принципу динамического программирования за время O(N).
Для этого необходимо добавить запоминание тех подзадач, которые уже были решены.
Необходимо завести массив/список, назовем его dp, который изначально заполнен значениями [0,1]+[None]*(N-1).
Если dp[i] равно None, то значит задача для значения i ещё не была решена, и мы будем решать её,
как в рекурсивном случае, в противном случае сразу вернём значение dp[i], которое уже было найдено ранее и
сохранено в нашем массиве/списке. Код имеет следующий вид:
def F(n):
if dp[n] != None:
return dp[n]
dp[n] = F(n - 1) + F(n - 2)
return dp[n]
Такой подход к реализации алгоритма принято называть нисходящим (Top-Down), потому что решая задачу,
мы переходим к её подзадачам. Есть и восходящий (Bottom-Up)подход, который состоит в решении задач подряд
от меньших к большим с запоминанием результатов. Реализация такого алгоритма для n>0 имеет следующий вид:
n = int(input())
dp = [None] * (n + 1)
dp[0] = 0
dp[1] = 1
for i in range (2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
Для данного примера может показаться, что восходящий способ проще, чем нисходящий.
Но если задача зависит не от одного параметра, а от двух или трёх, то нисходящий способ, как правило, оказывается проще.