Setul 2

Exerciții propuse

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).

Rezolvare