Exerciții rezolvate: recursivitate

Exercițiul 1. Un număr natural n scris în baza 10 poate fi văzut recursiv ca fiind fie o cifră (dacă e < 10), fie un număr (n / 10) urmat de o cifră (n mod 10). Funcții care prelucrează cifrele unui număr se pot scrie natural folosind această definiție recursivă.

Scrieți o funcție care returnează câte cifre dintr-un număr sunt egale cu o anumită cifră, c dată și ea ca parametru.

Soluție Va trebui să numărăm 1 pentru fiecare cifră din număr egală cu cifra dată, și să nu numărăm (sau să numărăm 0) altfel. Comparația returnează o valoare booleană (false sau true), deci e utilă o funcție simplă care să convertească un boolean la întreg.

let int_of_bool = function
  | false -> 0
  | true -> 1

val int_of_bool : bool -> int = <fun>  (* tipul funcției, dedus de OCaml; nu se scrie în program *)

Mai departe, ultima cifră din n e n mod 10, și putem converti rezultatul comparației n mod 10 = c din boolean în 1 sau 0. Dacă numărul e mai mic ca 10, acesta e și răspunsul; altfel, mai trebuie să apelăm recursiv funcția pentru a număra cifrele din restul numărului (partea de la cifra zecilor în față, deci n/10), și să adunăm acest număr.

let rec nrcif c n = 
  int_of_bool (n mod 10 = c) + if n < 10 then 0 else nrcif c (n/10)

val nrcif : int -> int -> int = <fun>

În ML, if ... then ... else ... e o expresie, deci dacă rezultatul de pe cele două ramuri e un întreg, ca aici, putem s-o folosim direct în calcul ca orice întreg (de exemplu, în adunare).
Am preferat să scoatem ca termen comun în adunare calculul pentru ultima cifră, care se face pentru ambele cazuri, și abia apoi să începem cu decizia pentru numere de o cifră (nu mai trebuie adunat nimic, deci 0) sau de mai multe cifre. S-ar fi putut scrie și:

let rec nrcif c n = 
  if n < 10 then int_of_bool (n = c)
  else int_of_bool (n mod 10 = c) + nrcif c (n/10)

De fapt, variantele scrise funcționează corect pentru numere nenegative. Pentru numere negative, s-ar intra pe ramura n < 10, indiferent de numărul de cifre. Deci, în funcție de comportamentul dorit, ar trebui fie semnalată o eroare, fie ar trebui definit ca soluție:

let nrcif_int n = nrcif (abs n)

unde abs e funcția predefinită de valoare absolută pentru întregi.

Exercițiul 2. Funcția putere pentru exponent natural (și bază număr întreg) se poate scrie recursiv în felul următor:

let rec putere x n = if n = 0 then 1 else x * putere x (n-1)

Similar cu cele de mai sus, definiți recursiv o funcție care ia ca parametru un întreg n și o funcție f, și returnează compunerea funcției f cu ea însăși de n ori: f _°f _° ... _°f. Verificați rezultatul cu valori concrete pentru f, n și valoarea în care se aplică funcția.

Soluție Putem defini întâi obișnuita compunere a două funcții:

let comp f g x = f (g x)

val comp : ('a -> 'b) -> ('c -> 'a) -> 'c -> 'b = <fun>

Apoi trebuie să definim cazul de bază. Elementul identitate în raport cu operația de compunere e funcția identitate f(x) = x, adică fun x -> x . Apoi, definim recursiv f ⁿ = f _°f ^n-1 pentru n > 0 .

let rec apply f n = if n = 0 then fun x -> x else comp f (apply f (n-1))

val apply : ('a -> 'a) -> int -> 'a -> 'a = <fun>

Deoarece primul parametru, funcția f, e același la fiecare apel recursiv, putem defini în interior o funcție ajutătoare apply1, care are acces la parametrul lui apply și nu mai trebuie să-l transmită de fiecare dată:

let apply f =
  let rec apply1 n = if n = 0 then fun x -> x else comp f (apply1 (n-1))
  in apply1

Construcția let definitie = expr1 in expr2 (sau la fel, cu let rec) e la rândul ei o expresie, și poate fi folosită oriunde e nevoie de o expresie. Valoarea ei este expr2, în care definiție e folosită cu înțelesul din expr1 (substituită cu expr1). Definiția e făcută local, și poate fi folosită doar în expr2, nefiind vizibilă altundeva.

Atenție, f e un parametru al funcției apply, și deci nu trebuie să definim înainte o funcție let f = ..., tot după cum dacă definim let g x = x * x + 1 nu îl definim înainte pe x, ci furnizăm argumentul dorit la apel: g 1 (care, evaluat, dă 2).
Putem scrie deci direct apply (fun x -> x * x + 1) 3 0 care calculează ((x² + 1)² + 1)² + 1 în punctul 0, deci 5.
Desigur, putem scrie și din aproape în aproape:

let g x = x * x + 1
let h = apply g 3

și apela în final h 0 cu același rezultat.

Cum în OCaml nu există un tip număr natural, parametrul numeric al funcției apply e de fapt un întreg; pentru un număr negativ, ea se va apela continuu cu n-1 până la depășirea stivei. Completăm funcția, semnalând printr-o excepție când primește un argument negativ:

let apply f n =
  let rec apply1 n = if n = 0 then fun x -> x else comp f (apply1 (n-1))
  in if n < 0 then raise (Invalid_argument "apply") else apply1 n

Cuvântul cheie raise semnalează (produce) o excepție. Invalid_argument e o excepție predefinită, cu un parametru șir (de regulă numele funcției care a produs excepția sau un alt mesaj explicativ).

Marius Minea

Last modified: Sat Oct 19 11:30:00 EEST 2013