Recursivitate pe șiruri de caractere

Șirurile de caractere (string-urile) sunt, în esență, vectori de caractere. Tot ce am văzut la recursivitate pe vectori se aplică, cu câteva particularități pentru tratarea caracterelor.

Cum citim șirurile cu indexare de la 1

În acest manual folosim indexare de la 1 pentru consecvență cu ceilalți vectori. Trucul standard în C++ e să citim în s + 1 (adică începând de la poziția 1):

char s[102];
fin >> (s + 1);           // citim incepand de la s[1]
int n = strlen(s + 1);    // lungimea, ignorand s[0]

Acum s[1] e primul caracter, s[2] al doilea, …, s[n] ultimul. La s[n+1] avem terminatorul '\0'.

Varianta cu `string` (STL)

#include <string>
string s;
fin >> s;
s = " " + s;              // adaugam un spatiu la inceput pentru a shifta
int n = s.length() - 1;

Mai simplu, dar mai puțin uzual. În exemplele de mai jos folosim char s[] cu indexare de la 1.

1. Lungimea unui șir

Varianta recursivă care parcurge de la poziția 1:

int lungime(int i = 1) {
    if (s[i] == '\0') return 0;
    return 1 + lungime(i + 1);
}

// Apel initial: lungime(1)

Pentru s = "hello" (citit în s+1, deci s[1..5] = "hello", s[6] = '\0'):

lungime(1) = 1 + lungime(2) = 1 + 4 = 5
lungime(2) = 1 + lungime(3) = 1 + 3 = 4
lungime(3) = 1 + lungime(4) = 1 + 2 = 3
lungime(4) = 1 + lungime(5) = 1 + 1 = 2
lungime(5) = 1 + lungime(6) = 1 + 0 = 1
lungime(6) = s[6] = '\0' → 0

2. Inversarea unui șir

Inversăm “pe loc”, între indicii st și dr:

void inverseaza(int st, int dr) {
    if (st >= dr) return;
    char tmp = s[st]; s[st] = s[dr]; s[dr] = tmp;
    inverseaza(st + 1, dr - 1);
}

// Apel: inverseaza(1, strlen(s + 1));

Pentru s+1 = "hello":

Start: " hello" (s[0]=spatiu, s[1..5]="hello")
(1, 5): swap s[1]='h' si s[5]='o' → " oellh"
(2, 4): swap s[2]='e' si s[4]='l' → " olleh"
(3, 3): st == dr, return
Rezultat: "olleh"

3. Verificare palindrom

Un șir e palindrom dacă e identic cu el însuși citit invers.

bool palindrom(int st, int dr) {
    if (st >= dr) return true;
    if (s[st] != s[dr]) return false;
    return palindrom(st + 1, dr - 1);
}

// Apel: palindrom(1, n)

Pentru s+1 = "kayak" (lungime 5):

palindrom(1, 5): s[1]='k' == s[5]='k' → palindrom(2, 4)
palindrom(2, 4): s[2]='a' == s[4]='a' → palindrom(3, 3)
palindrom(3, 3): st == dr → true

4. Numărul de apariții ale unui caracter

int nrAparitii(char c, int i = 1) {
    if (s[i] == '\0') return 0;
    return (s[i] == c ? 1 : 0) + nrAparitii(c, i + 1);
}

// Apel: nrAparitii('i')

Pentru s+1 = "mississippi", c = 'i':

nrAparitii('i', 1): s[1]='m' → 0 + nrAparitii('i', 2)
nrAparitii('i', 2): s[2]='i' → 1 + nrAparitii('i', 3)
...
Rezultat: 4

5. Copierea unui șir

void copiaza(char *sursa, char *dest, int i = 1) {
    dest[i] = sursa[i];
    if (sursa[i] == '\0') return;
    copiaza(sursa, dest, i + 1);
}

Atenție: dest trebuie să aibă loc suficient!

6. Compararea a două șiruri

Returnează 0 dacă sunt identice, diferit de 0 altfel (similar cu strcmp).

int compara(const char *a, const char *b, int i = 1) {
    if (a[i] == '\0' && b[i] == '\0') return 0;
    if (a[i] != b[i]) return a[i] - b[i];
    return compara(a, b, i + 1);
}

7. Transformare majuscule

Convertim toate caracterele mici în mari.

void toUpper(int i = 1) {
    if (s[i] == '\0') return;
    if (s[i] >= 'a' && s[i] <= 'z')
        s[i] = s[i] - 'a' + 'A';
    toUpper(i + 1);
}

Pentru s+1 = "Hello World":

'H' deja mare → neschimbat
'e' → 'E'
'l' → 'L'
...
Rezultat: "HELLO WORLD"

8. Eliminarea unui caracter

Eliminăm toate aparițiile unui caracter dintr-un șir.

void elimina(char c, int i = 1) {
    if (s[i] == '\0') return;
    if (s[i] == c) {
        // Shiftam tot cu o pozitie la stanga
        int j = i;
        while (s[j] != '\0') { s[j] = s[j + 1]; j++; }
        elimina(c, i); // reverificam pozitia i (un nou caracter e acolo)
    } else {
        elimina(c, i + 1);
    }
}

Pentru s+1 = "banana", c = 'a':

"banana" → elimina 'a' la poz 2 → "bnana"
"bnana"  → elimina 'a' la poz 3 → "bnna"
"bnna"   → elimina 'a' la poz 4 → "bnn"
"bnn"    → gata

9. Verificare anagramă

Doi șiruri sunt anagrame dacă au aceleași litere, dar în altă ordine.

int fr1[256], fr2[256]; // globale initializate cu 0

void freqSir(const char *s, int *fr, int i = 1) {
    if (s[i] == '\0') return;
    fr[(unsigned char)s[i]]++;
    freqSir(s, fr, i + 1);
}

bool anagrame(const char *a, const char *b) {
    for (int i = 0; i < 256; i++) fr1[i] = fr2[i] = 0;
    freqSir(a, fr1);
    freqSir(b, fr2);
    for (int i = 0; i < 256; i++)
        if (fr1[i] != fr2[i]) return false;
    return true;
}

Cod complet

#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");

char s[1002];
int n;

int lungime(int i = 1) {
    if (s[i] == '\0') return 0;
    return 1 + lungime(i + 1);
}

bool palindrom(int st, int dr) {
    if (st >= dr) return true;
    if (s[st] != s[dr]) return false;
    return palindrom(st + 1, dr - 1);
}

int nrAparitii(char c, int i = 1) {
    if (s[i] == '\0') return 0;
    return (s[i] == c ? 1 : 0) + nrAparitii(c, i + 1);
}

int main() {
    fin >> (s + 1);
    n = lungime();

    fout << "Lungime: " << n << "\n";
    fout << "Palindrom: " << (palindrom(1, n) ? "DA" : "NU") << "\n";
    fout << "Nr 'a': " << nrAparitii('a') << "\n";

    return 0;
}

date.in:

amanaplanacanalpanama

date.out:

Lungime: 21
Palindrom: DA
Nr 'a': 10

(“A man a plan a canal Panama” e palindrom faimos!)

Greșeli frecvente

1. Lipsa null terminator pentru `char`

char s[] = {'a', 'b', 'c'}; // GRESIT - nu se termina cu '\0'
// lungime(s) intra in bucla infinita sau da rezultat aiurea

Folosește:

char s[] = "abc";     // automat '\0' la sfarsit

2. Citirea fără shift

fin >> s;         // s[0] = primul caracter
lungime(1);       // GRESIT - sare peste primul caracter!

// CORECT:
fin >> (s + 1);   // s[1] = primul caracter
lungime(1);       // pornim de la primul caracter real

3. Buffer overflow la `copiaza`

char dest[5];
copiaza("hello world", dest); // dest prea mic!

Verifică dimensiunea destinației (minim strlen(sursa) + 2 pentru s[0] și '\0' la final).

4. Palindrom case-sensitive

"Aba" nu e palindrom dacă compari strict 'A' != 'a'. Dacă vrei case-insensitive, transformă în lowercase mai întâi.

5. Șir gol

palindrom(1, 0); // st > dr de la inceput → true (corect: sir gol e palindrom)

Cazul de bază st >= dr acoperă și situația asta.

6. Modificare șir constant

const char *s = "hello";
s[0] = 'H'; // EROARE - s e constant

Pentru modificare, folosește tablou modificabil: char s[] = "hello";.

Ce să reții

Șirurile sunt vectori de char - recursivitatea e similară cu cea pe vectori.
În acest manual folosim indexare de la 1: citim cu fin >> (s + 1), iar s[1] e primul caracter.
Caz de bază tipic: s[i] == '\0' (tablou C).
Operații clasice: lungime, inversare, palindrom, copiere, număr apariții, toUpper.
Șirurile mari (> 10^5) pot da stack overflow - folosește iterativ.
Atenție la buffer overflow și null terminator.