Recursivitate indirectă

Până acum, recursivitatea însemna: o funcție se apelează pe sine. Asta se numește recursivitate directă.

Există și recursivitate indirectă (sau mutuală): două sau mai multe funcții se apelează una pe alta, formând un ciclu.

Directă:   A → A → A → ... → A (caz de baza)

Indirectă: A → B → A → B → ... → caz de baza

Schemă generală

functie A(parametri):
    daca caz_de_baza: return ...
    apeleaza B(parametri_mai_mici)

functie B(parametri):
    daca caz_de_baza: return ...
    apeleaza A(parametri_mai_mici)

Fiecare funcție e “incompletă” fără cealaltă. Împreună formează un algoritm complet.

Problema declarării

În C++, ca să apelezi o funcție trebuie să fie declarată înainte. Dar dacă A apelează B și B apelează A, una dintre ele e definită după cealaltă → eroare de compilare.

Soluție: declarăm (doar semnătura, fără corp) funcția înainte de a o defini.

bool esteImpar(int n); // declaratie (forward declaration)

bool estePar(int n) {
    if (n == 0) return true;
    return esteImpar(n - 1); // OK - esteimpar e declarata
}

bool esteImpar(int n) {
    if (n == 0) return false;
    return estePar(n - 1);
}

Fără declarația lui esteImpar, compilatorul ar da eroare când întâlnește return esteImpar(n - 1) în estePar.

Exemplul 1: par/impar mutuali

Fără operații aritmetice (fără %), verificăm dacă un număr e par sau impar folosind doar recursivitate mutuală.

Ideea

0 e par (caz de bază).
n e par ⟺ n-1 e impar.
n e impar ⟺ n-1 e par.

Cod

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

bool esteImpar(int n); // forward declaration

bool estePar(int n) {
    if (n == 0) return true;
    return esteImpar(n - 1);
}

bool esteImpar(int n) {
    if (n == 0) return false;
    return estePar(n - 1);
}

int main() {
    int n;
    fin >> n;
    fout << (estePar(n) ? "par" : "impar");
    return 0;
}

date.in:

date.out:

impar

Pas cu pas pentru `estePar(4)`

estePar(4) = esteImpar(3)
esteImpar(3) = estePar(2)
estePar(2) = esteImpar(1)
esteImpar(1) = estePar(0)
estePar(0) = true    ← caz de bază!
esteImpar(1) = true → intoarce true, dar asta e "par" pentru 1... stai!

Atenție, întoarcerile merg invers: estePar(0) = true, deci esteImpar(1) = estePar(0) = true înseamnă că rezultatul lui esteImpar(1) = true. Nu valoarea se propagă, ci returnul logic.

Corect:

estePar(0) → true
  deci esteImpar(1) = estePar(0) = true
    deci estePar(2) = esteImpar(1) = true
      deci esteImpar(3) = estePar(2) = true
        deci estePar(4) = esteImpar(3) = true  ← 4 e par ✓

Observație: e un exemplu didactic - în practică folosim n % 2 == 0 care e O(1). Aici e O(n) și consumă stiva.

Exemplul 2: calcule pe expresii cu paranteze

Să presupunem că vrem să evaluăm o expresie simplă cu +, * și paranteze ( ).

Gramatică recursivă:

expresie  = termen (+ termen)*
termen    = factor (* factor)*
factor    = numar | (expresie)

Fiecare regulă folosește celelalte → recursivitate mutuală naturală.

Cod simplificat

#include <iostream>
using namespace std;

char s[1001];
int poz;

int expresie();
int termen();
int factor();

int factor() {
    if (s[poz] == '(') {
        poz++;                  // sarim '('
        int v = expresie();
        poz++;                  // sarim ')'
        return v;
    }
    int v = 0;
    while (s[poz] >= '0' && s[poz] <= '9') {
        v = v * 10 + (s[poz] - '0');
        poz++;
    }
    return v;
}

int termen() {
    int v = factor();
    while (s[poz] == '*') {
        poz++;
        v *= factor();
    }
    return v;
}

int expresie() {
    int v = termen();
    while (s[poz] == '+') {
        poz++;
        v += termen();
    }
    return v;
}

int main() {
    cin >> s;
    poz = 0;
    cout << expresie();
    return 0;
}

Pentru (2+3)*4:

expresie → termen → factor('(') → expresie (2+3) → 5 → return din factor 5
termen continuă: *4 → factor → 4
termen = 5 * 4 = 20
expresie = 20

Această tehnică se numește recursive descent parsing și e fundamentală pentru compilatoare și interpretoare.

Când apare recursivitatea indirectă?

1. Gramatici și parsere

Evaluarea expresiilor, analiza sintactică (parser recursive descent).

2. Grafuri bipartite

Două tipuri de noduri care se referă reciproc (ex: studenți ↔︎ cursuri, filme ↔︎ actori).

3. Automate cu stări multiple

Fiecare stare are propria funcție de tranziție care apelează alte stări.

4. Definiții matematice mutuale

Cum e Hofstadter F și M de mai sus, sau perechi de funcții din teoria numerelor.

5. Implementări didactice

Ca par/impar - utile pentru a învăța conceptul, chiar dacă nu sunt optime.

Comparație: directă vs indirectă

	Directă	Indirectă
Apel	`f → f → f`	`f → g → f → g`
Declarare	nu e nevoie	forward declaration necesară
Stiva	crește la fel	crește la fel
Exemple	factorial, Fibonacci	par/impar, parsere

Ambele consumă memorie în mod similar pe stivă. Conceptual sunt echivalente - orice recursivitate indirectă poate fi transformată în directă (combinând funcțiile într-una singură cu parametru de stare), dar uneori e mai clară în formă indirectă.

Transformarea indirectă → directă

Par/impar indirect:

bool estePar(int n) {
    if (n == 0) return true;
    return esteImpar(n - 1);
}
bool esteImpar(int n) {
    if (n == 0) return false;
    return estePar(n - 1);
}

Direct (o singură funcție cu parametru de paritate):

bool verifica(int n, bool parCautat) {
    if (n == 0) return parCautat;
    return verifica(n - 1, !parCautat);
}

// estePar(n) = verifica(n, true)
// esteImpar(n) = verifica(n, false)

Același comportament, o singură funcție.

Greșeli frecvente

1. Lipsa declarării înainte

bool estePar(int n) {
    return esteImpar(n - 1); // EROARE - esteImpar nu e declarata
}

bool esteImpar(int n) {
    return estePar(n - 1);
}

Scrie declarația funcției (prototype) înainte de prima utilizare:

bool esteImpar(int n);  // forward declaration
bool estePar(int n) { ... }
bool esteImpar(int n) { ... }

2. Ciclu fără caz de bază

void f() { g(); }
void g() { f(); }

Stack overflow imediat. Trebuie măcar una dintre funcții să aibă un caz de bază accesibil.

3. Condiții de bază inconsistente

bool estePar(int n) {
    if (n == 0) return true;
    return esteImpar(n - 1);
}
bool esteImpar(int n) {
    if (n == 1) return true; // GRESIT - pentru n par apelul cade
    return estePar(n - 1);
}

Aici, esteImpar(0) nu e tratat → apelează estePar(-1) → esteImpar(-2) → stack overflow.

Testează: toate cazurile posibile ajung la un caz de bază?

4. Uitarea că stiva se umple

Par/impar cu recursivitate indirectă pentru n = 10^5 → stack overflow. Folosește soluția directă (n % 2) în practică.

Ce să reții

Recursivitate indirectă (mutuală): două sau mai multe funcții se apelează una pe alta.
Necesită forward declaration pentru a permite compilarea.
Apare natural în: parsere (recursive descent), grafuri bipartite, gramatici, secvențe matematice mutual definite (Hofstadter).
Orice recursivitate indirectă poate fi transformată în directă, dar uneori e mai clară în formă indirectă.
Atenție: toate funcțiile din ciclu trebuie să aibă cazuri de bază accesibile pentru orice intrare validă.
Consumul de stivă e același ca la recursivitatea directă.
Exemple didactice: par/impar mutual; exemplu practic: evaluator de expresii.