Recursivitate. Functii recursive – C++

Recursivitatea pleaca de la ideea ca o functie se poate apela pe ea insasi. Pentru a intelege mai bine este important sa ne uitam si la ce inseamna cuvantul recursiv, si anume, care se poate repeta in mod nelimitat sau repetitiv (conform dex.ro).

O functie recursiva este acea functie care contine in interiorul ei un autoapel. Putem vedea mai jos un exemplu de astfel de functie:

Problema cu functia pe care am scris-o mai sus este ca daca ar fi sa o apelam in main(), functia mesaj() ar intra intr-o bucla infinita afisand tot timpul pe ecran mesajul “Salut!” pana cand calculatorul nostru o va opri fortat.

Puteti sa intuiti ca nu ar avea sens sa scriem o functie recursiva (care se autoapeleaza) in acest fel. Dar daca nu asa, atunci cum? Pentru a evita buclele infinite corpul unui subprogram recursiv trebuie sa respecte o anumita structura, si anume trebuie sa contina o formula de recurenta (care contine autoapelul functiei) si o conditie de oprire (care determina programul sa se opreasca si sa afle solutia). Aceste 2 notiuni sunt cunoscute si ca cazul general al solutiei si cazul general al solutiei.

Cazul general al solutiei contine formula de recurenta prin care se realizeaza autoapelul. Spre exemplu: return n+suma(n-1); este o formula de recurenta pe care o putem folosi atunci cand calculam suma a n numere.

Cazul de baza al solutiei contine o operatie care rezolva un caz special al problemei fara sa foloseasca autoapelul. Spre exemplu: return 0 in cazul in care n este 0.

Cazul general si cazul de baza se imbina folosind o instructiune de tipul if…else. Puteti vedea mai jos un exemplu de functie recursiva care calculeaza suma primelor n numere si cum am imbinat cazul de baza si cazul general pentru a ajunge la solutie:

La sfarsitul articolului puteti gasi 2 videouri de pe canalul nostru de YouTube in care puteti vedea exemple de functii recursive.

Atunci cand definim o functie recursiva trebuie sa avem grija ca valoarea parametrului folosit in autoapel sa mearga spre cazul de baza. Aceasta conditie este cunoscuta drept conditia de consistenta. In cazul nostru de mai sus valoarea parametrului folosit la autoapelare este n-1 si respecta conditia de consistenta intrucat cu fiecare autoapel se apropie de cazul de baza n=0.

Inainte de a scrie o functie recursiva este recomandat sa gasim functia matematica recursiva pe care mai apoi sa o transpunem in cod.

Videouri de pe canalul nostru de YouTube in care discutam despre recursivitate:

Spor la lucru 🙂

Cmmdc (cel mai mare divizor comun) 3 numere – C++

Pentru a afla cmmdc pentru 3 numere trebuie mai intai sa aflam cmmdc a 2 dintre numerele respective si sa comparam acea valoare cu al 3-lea numar si sa gasim cmmdc pentru acele 2 valori. Mai jos puteti gasi o varianta de rezolvare cu ajutorul unui subprogram si o varianta fara subprograme.

Varianta fara subprogram:

Varianta cu subprogram:

Video YouTube in care discutam despre cum putem afla cmmdc pentru 3 numere in C++:

Spor la lucru 🙂