Фибоначчи и число вызовов

Числа Фибоначчи: $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 при вычислении fib(n) (первый вызов тоже считается).

Одно целое число $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$ миллиона. Это цена наивной рекурсии.