Ce vei învăța astăzi?
După această lecție vei aplica recursivitatea pe șiruri de caractere și pe vectori: afișarea inversă a unui șir, parcurgerea și suma elementelor unui vector.
Afișarea inversă a unui șir
Pentru un șir de caractere s, afișarea inversă se face recursiv: afișăm mai întâi restul șirului (fără primul caracter), apoi primul caracter.
Astfel, pentru „bac", se afișează întâi inversul lui „ac", apoi „b": rezultatul este „cab".
#include <iostream>
#include <cstring>
using namespace std;
void invers(char s[], int i)
{
if (s[i] == '\0')
return;
invers(s, i + 1);
cout << s[i];
}
int main()
{
char s[101];
cin.get(s, 101);
invers(s, 0);
return 0;
}
Observă: afișarea caracterului are loc după apelul recursiv, deci caracterele apar în ordine inversă. Cazul de bază este întâlnirea terminatorului de șir '\0' (caracterul special care marchează sfârșitul textului).
Suma elementelor unui vector recursiv
Suma elementelor unui vector se calculează recursiv: suma(v, i) = v[i] + suma(v, i + 1), cu cazul de bază când am depășit ultimul element (întoarcem 0).
#include <iostream>
using namespace std;
int suma(int v[], int i, int n)
{
if (i == n)
return 0;
return v[i] + suma(v, i + 1, n);
}
int main()
{
int n, v[1001];
cin >> n;
for (int i = 0; i < n; i++)
cin >> v[i];
cout << suma(v, 0, n);
return 0;
}
Exemplu: v = {1, 2, 3, 4}
Alte aplicații pe vectori
Ce mai putem calcula recursiv pe un vector?
- Maximul elementelor:
max(v, i) = max(v[i], max(v, i+1)) - Numărul de elemente pare: adunăm 1 dacă v[i] este par, la rezultatul apelului următor
- Afișarea elementelor în ordine inversă: parcurgere cu afișare după apel
Exercițiu de completare
Completează enunțul despre recursivitatea pe structuri de date cu cuvintele potrivite:
Pentru afișarea ______ a unui șir, afișăm caracterul după apelul ______. Cazul de bază pentru un șir de caractere este întâlnirea terminatorului ______. Suma elementelor unui vector se calculează cu relația suma(v, i) = v[i] + suma(v, i + 1), iar cazul de bază întoarce ______ când am ajuns la final.
Bancă de cuvinte:
Exercițiu de completare
Completează funcția suma pentru vectori:
Bancă de cuvinte:
Test de înțelegere
Test rapid - șiruri și vectori:
1. Inversul șirului „bac" este:
2. Cazul de bază pentru afișarea inversă a unui șir este:
3. Pentru vectorul v = {1, 2, 3, 4}, suma(v, 0, 4) este:
Aprofundare
Parcurgerea în ambele sensuri. Poziționând afișarea înaintea apelului recursiv, șirul apare în ordine naturală; plasând-o după apel, șirul apare inversat. Același principiu se aplică și la vectori: elementele pot fi prelucrate „la coborâre" sau „la urcare" pe stivă, în funcție de poziția instrucțiunii față de apel.
Verificarea proprietăților pe vectori. Parcurgerea recursivă permite verificarea simplă a unor proprietăți globale: numărarea elementelor pare, verificarea dacă toate elementele sunt pozitive sau dacă vectorul este sortat. Funcția întoarce un rezultat parțial, apoi combină rezultatul curent cu cel al apelului pentru restul vectorului.
Divide et impera. O variantă mai avansată împarte vectorul în două jumătăți egale și rezolvă recursiv fiecare jumătate (de exemplu, suma elementelor pe jumătăți). Complexitatea rămâne O(n), iar adâncimea stivei devine log₂(n), mult mai sigură pentru vectori mari decât parcurgerea liniară recursivă.
Cazul șirurilor de caractere. Pentru șiruri cu terminator '\0', cazul de bază este atins când s[i] == '\0'; aceasta elimină necesitatea transmiterii lungimii ca parametru, funcția oprindu-se la finalul natural al șirului.
PbInfo - Inversarea unui șir
Enunț:
Cerință: Se citește un șir de caractere. Să se afișeze șirul inversat, folosind un subprogram recursiv.
Date de intrare:
Programul citește de la tastatură un șir de caractere (fără spații).
Date de ieșire:
Programul va afișa pe ecran șirul inversat.
Restricții și precizări:
Lungimea șirului nu depășește 100 de caractere.
Exemplu:
Intrare:
informatica
Ieșire:
acitamrofni
Cum gândim soluția:
- Definim funcția
invers(s, i)care afișează șirul de la poziția i înapoi - Cazul de bază: dacă
s[i] == '\0', ne oprim - Afișăm inversul restului, apoi caracterul curent
Scrie soluția în C++:
Soluție corectă:
#include <iostream>
#include <cstring>
using namespace std;
void invers(char s[], int i)
{
if (s[i] == '\0')
return;
invers(s, i + 1);
cout << s[i];
}
int main()
{
char s[101];
cin.get(s, 101);
invers(s, 0);
return 0;
}
Ce învățăm: afișarea după apelul recursiv produce inversul șirului.
PbInfo - Suma elementelor unui vector
Enunț:
Cerință: Se citește n și apoi n numere naturale. Să se afișeze suma lor, folosind un subprogram recursiv de parcurgere a vectorului.
Date de intrare:
Programul citește de la tastatură numărul n, apoi n numere naturale.
Date de ieșire:
Programul va afișa pe ecran suma elementelor.
Restricții și precizări:
1 ≤ n ≤ 1000, elementele sunt numere naturale.
Exemplu:
Intrare:
4 1 2 3 4
Ieșire:
10
Cum gândim soluția:
- Definim funcția
suma(v, i, n) - Cazul de bază: dacă
i == n, întoarcem 0 - Altfel întoarcem
v[i] + suma(v, i + 1, n) - În main citim vectorul și afișăm suma(v, 0, n)
Scrie soluția în C++:
Soluție corectă:
#include <iostream>
using namespace std;
int suma(int v[], int i, int n)
{
if (i == n)
return 0;
return v[i] + suma(v, i + 1, n);
}
int main()
{
int n, v[1001];
cin >> n;
for (int i = 0; i < n; i++)
cin >> v[i];
cout << suma(v, 0, n);
return 0;
}
Ce învățăm: vectorul este transmis ca parametru, iar parcurgerea se face prin indicele i, incrementat la fiecare apel.
Exercițiul Practic: Șiruri și vectori recursivi
Sarcini de lucru
Rezolvă sarcinile următoare despre recursivitatea pe șiruri și vectori
Sarcina 1: Maximul din vector recursiv
Cerință: Scrie un program C++ care afișează maximul elementelor unui vector, folosind o funcție recursivă. Pentru v = {3, 8, 2, 9}, maximul este 9.
Soluție pentru Sarcina 1:
#include <iostream>
using namespace std;
int maxim(int v[], int i, int n)
{
if (i == n - 1)
return v[i];
int m = maxim(v, i + 1, n);
if (v[i] > m)
return v[i];
return m;
}
int main()
{
int n, v[1001];
cin >> n;
for (int i = 0; i < n; i++)
cin >> v[i];
cout << maxim(v, 0, n);
return 0;
}
Sarcina 2: Numărul de elemente pare
Cerință: Scrie un program C++ care afișează numărul de elemente pare dintr-un vector, folosind o funcție recursivă. Pentru v = {1, 4, 3, 8}, rezultatul este 2.
Soluție pentru Sarcina 2:
#include <iostream>
using namespace std;
int numara_pare(int v[], int i, int n)
{
if (i == n)
return 0;
int c = numara_pare(v, i + 1, n);
if (v[i] % 2 == 0)
c++;
return c;
}
int main()
{
int n, v[1001];
cin >> n;
for (int i = 0; i < n; i++)
cin >> v[i];
cout << numara_pare(v, 0, n);
return 0;
}