Curs
Exercițiul 1: Dacă șirul lui Fibonacci e calculat naiv, transcriind direct definiția: F0 = 0, F1 = 1, Fn = Fn-1 + Fn-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).