Logică și structuri discrete - Tema 2

Exercițiul 1: Dacă șirul lui Fibonacci e calculat naiv, transcriind direct definiția: F₀ = 0, F₁ = 1, F_n = F_n-1 + F_n-2. se generează un număr foarte mare de apeluri recursive.

• Desenați schema apelurilor care se fac pentru a calcula fib(4). (Puteți să urmăriți apelurile și în interpretorul OCaml, dând directiva de trasare a apelurilor
  # #trace fib;;
  înainte de o evaluare (de exemplu fib 4).
• Scrieți o relație de recurență pentru numărul de apeluri necesare pentru a calcula fib(n). Ce remarcați comparând cu recurența Fibonacci?
• Opțional, scrieți o funcție care calculează fib(n) mai eficient. (Funcția va lua ca parametri ultimii doi termeni anteriori din șir).