Recursivitate

Tema pentru laborator

Exercițiul 1 Dacă șirul lui Fibonacci e calculat naiv, transcriind direct definiția:

let rec fib(n) = if n < 2 then n else fib(n-1) + fib(n-2)

se generează un număr foarte mare de apeluri recursive.

Desenați schema apelurilor care se fac pentru a calcula fib(5). (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 5).
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).

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:
```
let _ = (
  expresie1;
  expresie2;
  ...
  expresieN
)
```

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.

Ș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
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

Am amintit că mulțimea resturilor nenule modulo un număr prim p formează un grup multiplicativ. Scrieți o funcție care ia ca parametru un număr întreg a și calculează ordinul lui în acest grup (adică cea mai mică putere n pentru care aⁿ ≡ 1 mod p

Marius Minea

Last modified: Mon Sep 29 15:30:00 EEST 2014