Logică și structuri discrete - Recursivitate: Exerciții

Exercițiul 1: Argumentați ce face funcția
Când scriem cod, trebuie să putem urmări ce face. Astfel putem arăta fie că el face ce trebuie, fie să găsim unde e greșeala.
Pentru următoarele două funcții (presupuse a lucra cu întregi nenegativi), argumentați cât mai riguros și convingător (ideal: prin inducție după numărul de cifre al lui n) ce rezultat produc.
a) let rec f1 n = if n < 10 then n else f1 (n/10)
b) let rec f2 n = if n < 10 then n else 10 * f2 (n/10) + n mod 10

Exercițiul 2: Limite și punct fix
Numim punct fix al unei funcții f o valoare x pentru care f(x) = x. De exemplu, f(x) = x2 are ca puncte fixe 0 și 1 (soluțiile ecuației x2 = x).
Pentru o funcție f și o valoare inițială x0, putem calcula șirul de valori x0, x1=f(x0), ..., xn+1=f(xn), .... Dacă la un moment dat obținem două valori consecutive egale, xn+1=xn, atunci xn e punct fix pentru f (aplicând definiția), și din acel moment termenul șirului nu se mai modifică (de ce? convingeți-vă prin inducție).
Dacă pornind de la valoarea xi, prin aplicare repetată a funcției f ajungem la un punct fix (al lui f), acesta poate fi calculat în OCaml cu funcția următoare (dacă însă nu ajungem la un punct fix, codul rulează la nesfârșit sau eșuează din lipsă de resurse). 

let rec fix f xi =
  let xn = f xi in
  if xn = xi then xi else fix f xn
a) Scrieți în OCaml funcția care calculează suma cifrelor unui număr nenegativ. Câte puncte fixe are și care sunt acestea? Ajungem la un punct fix prin aplicare repetată pornind de la orice număr? Verificați folosind funcția fix pentru câteva numere. Argumentați cât mai riguros.

b) Știm că în domeniul real (nu discret), un șir poate converge spre o limită fără să o atingă vreodată. Modificați funcția fix de mai sus astfel încât să calculeze limita șirului de reali x0, x1=f(x0), ..., xn+1=f(xn), .... (presupunând că există), oprindu-se când diferența în valoare absolută între doi termeni consecutivi este sub 10-6 (în OCaml ca și C dealtfel se poate scrie în notație științifică 1e-6). Pentru valoarea absolută există funcția standard abs_float (pentru întregi se cheamă abs).

c) Folosiți funcția scrisă la punctul b) pentru a calcula rădăcina pătrată a unui număr x cu metoda babiloniană (sau a lui Heron), șirul de aproximații fiind: a0 = 1, an+1 = (an + x/an)/2 .

d) (opțional): Pentru termenii √a+√a+ ...√a și 1/(a+1/(a+1/(... + 1/a))) găsiți relațiile de recurență care exprimă valoarea termenului cu n+1 apariții ale lui a în funcție de termenul cu n apariții. Apoi găsiți la limită valoarea termenilor cu număr infinit de apariții.

Marius Minea
Last modified: Sat Oct 10 11:20:00 EEST 2015