Esercizio 2 (12*)

Si indichi con $Call(n)$ il numero di calls alla function F eseguite dal seguente programma quando riceva il naturale $n$ come valore numerico in input.

#include<iostream.h>

long long int F(int n) {
  if(n <= 1) return n;
  return F(n-1) + F(n-2);
}

int main() {
  int n; cout << "Dammi n: "; cin >> n;
  cout << "F[" << n << "] = "  << F(n) << endl;
}

(*) Scrivere una ricorrenza e delle condizioni al contorno che definiscano $Call(n)$.
(***) Individure il nesso con un'altra ricorrenza famosa, esaminata durante il corso.
(***) Avvalersi di tale nesso per caratterizzare l'andamento asintotico di $Call(n)$, avvalendosi di quanto già noto per la ricorrenza famosa di riferimento.
(*****) Dimostrare la validità dei bounds asintotici utilizzati.