Informatică Programare
Exercitii recursivitate C++ rezolvate
Exercițiile de recursivitate în C++ se rezolvă prin definirea unei funcții cu caz de bază și caz recursiv. Voi rezolva pas cu pas două exerciții comune: calculul sumei primelor n numere naturale și inversarea unui șir de caractere.
Exercițiu 1: Suma primelor n numere naturale
- 1 Definește problema Suma S(n) = 1 + 2 + ... + n. Caz de bază: S(0) = 0. Caz recursiv: S(n) = n + S(n-1).
- 2 Scrie funcția int suma(int n) { if (n == 0) return 0; else return n + suma(n-1); }
- 3 Testează cu exemplu Pentru n=3: suma(3) = 3 + suma(2) = 3 + (2 + suma(1)) = 3 + (2 + (1 + suma(0))) = 3 + (2 + (1 + 0)) = 6.
Exercițiu 2: Inversarea unui șir de caractere
- 1 Definește problema Pentru un șir s, inversul lui s. Caz de bază: șir gol sau un caracter. Caz recursiv: ia ultimul caracter și adaugă la inversul restului.
- 2 Scrie funcția string invers(string s) { if (s.length() <= 1) return s; else return s.back() + invers(s.substr(0, s.length()-1)); }
- 3 Testează cu exemplu Pentru s="abc": invers("abc") = 'c' + invers("ab") = 'c' + ('b' + invers("a")) = 'c' + ('b' + 'a') = "cba".
Exersează scriind mai multe exerciții pentru a înțelege modelul recursiv.