Фибоначчи ва чақирувлар сони

Фибоначчи сонлари: $F_1 = F_2 = 1$, $F_k = F_{k-1} + F_{k-2}$. Уларни қуйидаги рекурсив функция ҳисоблайди:

fib(n):
    if n <= 2: return 1
    return fib(n - 1) + fib(n - 2)

$F_n$ ни ва fib(n) ҳисоблангунча fib функцияси жами неча марта чақирилишини топинг (биринчи чақирув ҳам саналади).

Битта бутун сон $n$ ($1 \le n \le 30$).

Битта қаторда иккита сон: $F_n$ ва чақирувлар сони.

Функция ичида глобал ҳисоблагични $1$ га оширинг. $n = 5$ да: fib(5) → fib(4), fib(3); fib(4) → fib(3), fib(2); ҳар бир fib(3) → fib(2), fib(1). Жами $9$ та чақирув, $F_5 = 5$.

Бир хил қиймат қайта-қайта ҳисобланади, шунинг учун чақирувлар сони $n$ билан жуда тез ўсади: $n = 30$ да деярли $1.7$ миллион. Бу оддий рекурсиянинг нархи.