Recursivitate

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

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

Folosind definiția tipului expresie de la curs, scrieți în ML reprezentarea pentru expresiile: 2 * (3 - 8) + 4 și 2 + 4 - 5 * 3 . Verificați că puteți aplica funcția de evaluare și obțineți rezultatul corect.

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

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

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.

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

Adaptând programul pentru fractalul cruce, 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.

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.
Folosiți ca punct de plecare exercițiul rezolvat pentru rădăcina pătrată.

Scrieți o funcție care calculează valoarea lui e^x folosind dezvoltarea în serie Taylor: e^x = 1 + x/1! + x²/2! + ... + xⁿ/n! + ... , calculând până când termenul curent devine suficient de mic.
Evitați recalcularea inutilă a puterii și factorialului, găsind o relație de calcul pentru termenul curent al seriei pornind de la cel anterior, pe care îl transmiteți ca parametru la funcția pe care o scrieți.