Recursivitate

Mediul de lucru: compilarea și rularea

Pentru exemple simple, e convenabil să folosim interpretorul: le putem rula direct, și ne prezintă rezultatul, fără a fi nevoie să mai folosim funcții de tipărire.

Pentru a scrie programe care pot fi utilizate independent (cum e desenarea de fractali scrisă la curs), vom folosi compilatorul.
În primul rând, trebuie să ne structurăm programul în mod corespunzător:

să folosim explicit funcții de tipărire (print_int, print_float, print_string, printf, etc.) acolo unde dorim să apară scris ceva, întrucât rezultatele nu vor mai fi explicit tipărite de interpretor.
să punem în ordine codul pe care îl dorim executat. Prin compilare, se produce un program care evaluează, în ordine, toate expresiile din fișierul sursă. E însă o practică bună să definim întâi toate funcțiile necesare, și apoi să explicităm ce se dorește evaluat la rulare:
expresie1; expresie2; ...; expresieN (punând ;; înaintea lor pentru a le separa de restul definițiilor), sau
```
let _ = (
  expresie1;
  expresie2;
  ...
  expresieN
)
```
Liniuța de subliniere e un nume special, cu înțelesul "nu contează", nu se dorește folosirea lui ulterioară, ci doar uniformitatea sintaxei let ... = ...

Compilarea și rularea programului

Compilăm programul din terminal cu comanda

ocamlc program.ml

Compilatorul va produce un fișier executabil cu numele implicit a.out . Putem să specificăm și un alt nume dorit: ocamlc -o nume program.ml.

Programul executabil poate fi rulat din terminal, specificând numele lui, precedat de ./ (explicitând numele complet, inclusiv catalogul curent). Rulăm deci:

./a.out

dacă am compilat cu numele implicit, sau ./nume dacă am specificat alt nume pentru executabil.

Exerciții propuse

Șiruri recurente

Având ca exemplu progresia aritmetică discutată la curs, scrieți pentru progresia geometrică:

o funcție recursivă, folosind valori constante pentru primul termen și rație
o funcție care are ca parametri și aceste două valori. Folosiți let ... in și o funcție auxiliară cu un parametru.
definiți o funcție pentru progresia de la punctul 1 dând parametri funcției scrise la punctul 2

Expresii numerice

Folosind definiția tipului expresie de la curs, scrieți în ML reprezentarea pentru expresiile: 2 * (3 - 8) + 4 și 2 + 4 - 5 * 3 .

Cel mai mare divizor comun

Știind că cmmdc(a, b) = cmmdc(b, a mod b) dacă b ≠ 0, scrieți o funcție recursivă pentru cel mai mare divizor comun. Care e cazul de bază ?

Aplicarea repetată a unei funcții

în laboratorul trecut am scris funcții de ordin superior (funcționale) care aplicau o funcție de 2, 3, 4 ori. Definiți (recursiv) o funcție care ia ca parametru un întreg n și o funcție, și returnează funcția compusă cu ea însăși de n ori.

Lucrul cu cifrele unui număr

Un număr e reprezentat uzual în scris ca un șir de cifre în baza 10.
Un șir e o noțiune recursivă (un element, sau un șir urmat de un element).
Putem spune atunci că un număr n e fie o singură cifră, fie ultima cifră (n mod 10) precedată de alt număr (n / 10).
Folosind această definiție scrieți funcții recursive care calculează: suma cifrelor unui număr, numărul de cifre, produsul lor, cifra maximă / minimă, etc.

Resturi modulo p

În matematică știm că dacă p e un număr prim, și a nu se divide cu p, atunci șirul a, a², a³, ... va ajunge la 1, luând numerele modulo p (adică resturile la împărțirea cu p.
De exemplu, fie p = 7 și a = 4. Atunci a² = 16 ≡ 2 (mod 7), și a³ = a² * a ≡ 2 * 4 ≡ 1 (mod 7).
(Se spune că mulțimea resturilor nenule modulo p prim formează un grup multiplicativ.)
Scrieți o funcție care ia ca parametru un număr întreg a și un număr p (presupus prim) și returnează cea mai mică putere n pentru care aⁿ ≡ 1 mod p (sau returnează 0 dacă a se divide cu p).
Indicație: scrieți o funcție auxiliară care mai are ca parametri și exponentul k respectiv valoarea a^k (mod p), și care se apelează recursiv până când a^k ≡ 1 (mod p).

Fractali

Adaptând programul de la curs, generați alți fractali, cum ar fi triunghiul lui Sierpiński sau curba lui Koch.
Triunghiul poate fi scris după același tipar; diferă doar desenul propriu-zis, și faptul că apar și linii oblice (folosiți comanda l în formatul SVG).
Curba lui Koch se observă că poate fi desenată fără a ridica creionul de pe hârtie, deci e suficientă o singură poziționare inițială cu M. Figura e caracterizată acum prin dimensiune și orientare (unghi); unghiul pentru o sub-figură poate varia cu ± π/3 față de cel al figurii mari.

Marius Minea

Last modified: Wed Oct 5 11:20:00 EEST 2016