Fibonachchi va chaqiruvlar soni

Fibonachchi sonlari: $F_1 = F_2 = 1$, $F_k = F_{k-1} + F_{k-2}$. Ularni quyidagi rekursiv funksiya hisoblaydi:

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

$F_n$ ni va fib(n) hisoblanguncha fib funksiyasi jami necha marta chaqirilishini toping (birinchi chaqiruv ham sanaladi).

Bitta butun son $n$ ($1 \le n \le 30$).

Bitta qatorda ikkita son: $F_n$ va chaqiruvlar soni.

Funksiya ichida global hisoblagichni $1$ ga oshiring. $n = 5$ da: fib(5) → fib(4), fib(3); fib(4) → fib(3), fib(2); har bir fib(3) → fib(2), fib(1). Jami $9$ ta chaqiruv, $F_5 = 5$.

Bir xil qiymat qayta-qayta hisoblanadi, shuning uchun chaqiruvlar soni $n$ bilan juda tez o'sadi: $n = 30$ da deyarli $1.7$ million. Bu oddiy rekursiyaning narxi.