Функция $F(n)$ определена так: $F(1)=1$, $F(2)=1$, $F(n) = F(n-1) + F(n-2)$ для $n > 2$. Найдите $F(10)$. Сколько раз будет вызвана функция $F$, если посчитать $F(5)$ «наивной» рекурсией?
F(10)=55, F(5) делает 9 вызовов
Это числа Фибоначчи. Вычислим итеративно:
$F(1)=1, F(2)=1, F(3)=2, F(4)=3, F(5)=5, F(6)=8, F(7)=13, F(8)=21, F(9)=34, F(10)=55$.
Количество вызовов при «наивной» рекурсии $F(n)$ растёт как сам $F(n)$ (точнее, $T(n) = 2 F(n) - 1$). Для $F(5)$:
F(5)
├ F(4)
│ ├ F(3)
│ │ ├ F(2) ← база
│ │ └ F(1) ← база
│ └ F(2) ← база
└ F(3)
├ F(2) ← база
└ F(1) ← база
Всего узлов в дереве: $1 + 2 + 4 + ... = 9$ вызовов.
Код на Python:
calls = 0
def F(n):
global calls
calls += 1
if n <= 2:
return 1
return F(n - 1) + F(n - 2)
print(F(10)) # 55
F.__name__
calls = 0
F(5)
print(calls) # 9
Razbery — про разбор, не про списывание. Объяснение обязательно.