Cum urmărești o funcție recursivă la BAC: metoda arborelui de apeluri

La Subiectul I de la BAC informatică, grilele cu funcții recursive cer de obicei unul din trei lucruri: valoarea returnată de un apel, ce se afișează sau de câte ori se apelează funcția. Toate trei se rezolvă sigur cu aceeași unealtă: arborele de apeluri. Îl desenezi pe ciornă în două minute și elimini ghicitul. Dacă nu ești încă sigur pe ideea de condiție de oprire și stivă, citește întâi articolul despre recursivitate.

Metoda arborelui de apeluri

1. Scrie apelul inițial, de exemplu f(5), ca rădăcină.
2. Sub fiecare apel, scrie apelurile pe care le face, în ordinea în care apar în cod, cu valorile concrete ale parametrilor.
3. Oprește-te pe fiecare ramură când ajungi la condiția de oprire și scrie lângă ea valoarea returnată.
4. Urcă de jos în sus și calculează valoarea fiecărui nod din valorile fiilor.
5. Dacă funcția afișează, parcurge arborele în ordinea execuției și notează ce se scrie înainte și ce se scrie după fiecare apel.

Când funcția face un singur apel recursiv, arborele e de fapt un lanț. Când face două, devine un arbore adevărat, și acolo metoda contează cel mai mult.

Exemplul 1: valoare returnată, un singur apel

int f(int n)
{
    if (n == 0) return 0;
    if (n % 10 % 2 == 0) return f(n / 10) * 10 + n % 10;
    return f(n / 10);
}

Ce valoare are f(123456)? Lanțul de apeluri:

Răspunsul este 246: funcția păstrează cifrele pare, în ordinea inițială. Coloana „se returnează” se completează de sus în jos, iar coloana „valoare” de jos în sus. Abia după ce ai rezultatul poți generaliza ce face funcția — util dacă grila te întreabă despre alt apel.

Exemplul 2: două apeluri recursive și numărul de apeluri

int f(int n)
{
    if (n <= 1) return 1;
    return f(n - 1) + f(n - 2);
}

Arborele pentru f(5):

                    f(5)
            /                  \
         f(4)                  f(3)
        /     \               /    \
     f(3)     f(2)         f(2)    f(1)
    /   \     /   \        /   \
  f(2) f(1) f(1) f(0)   f(1) f(0)
  /  \
f(1) f(0)

Frunzele (f(1) și f(0)) valorează 1. Urcând: f(2) = 2, f(3) = 3, f(4) = 5, f(5) = 8. Numărul total de apeluri e numărul de noduri din arbore: 15.

Nu e nevoie să desenezi tot arborele pentru n mai mare. Notează cu A(n) numărul de apeluri făcute de f(n), inclusiv el însuși: A(0) = A(1) = 1 și A(n) = 1 + A(n−1) + A(n−2). Rezultă A(2) = 3, A(3) = 5, A(4) = 9, A(5) = 15. Același tabel îți dă și valorile: calculezi de jos în sus, nu de sus în jos.

Exemplul 3: afișare la dus și la întors

void f(int n)
{
    if (n > 0)
    {
        cout << n;
        f(n - 2);
        cout << n;
    }
}

Ce afișează f(5)? Lanțul de apeluri e f(5) → f(3) → f(1) → f(−1), iar f(−1) nu face nimic. La dus, fiecare apel scrie n înainte să coboare: 5, 3, 1. La întors, fiecare scrie din nou n, dar în ordine inversă: 1, 3, 5. Rezultat: 531135. Funcțiile de acest tip produc mereu un „palindrom”: ce s-a scris la dus se scrie oglindit la întors.

Exemplul 4: afișare între două apeluri

void g(int n)
{
    if (n > 0)
    {
        g(n - 1);
        cout << n;
        g(n - 1);
    }
}

Aici arborele e binar, iar afișarea se face între cei doi fii. Cel mai simplu e să construiești rezultatul de jos în sus, ca text:

• g(0) nu afișează nimic;
• g(1) = g(0) + „1” + g(0) = 1;
• g(2) = g(1) + „2” + g(1) = 121;
• g(3) = g(2) + „3” + g(2) = 1213121.

Deci g(3) afișează 1213121 — 7 cifre. Lungimea se dublează plus unu la fiecare nivel, așa că g(4) ar afișa 15 cifre. Dacă grila îți dă variante de răspuns, lungimea singură elimină adesea jumătate dintre ele.

Capcane frecvente

• Ordinea apelurilor: în f(n - 1) + f(n - 2) apelurile se fac pe rând; la funcțiile care afișează, contează ordinea scrisă în cod.
• Parametri prin referință sau variabile globale: dacă funcția modifică o variabilă globală, valoarea ei se transmite între apeluri — ține-o separat pe ciornă.
• Condiția de oprire cu <= sau <: verifică exact pentru ce valori se oprește (de exemplu, la n - 2 se poate sări peste 0, ca în exemplul 3).
• Return pe ramuri diferite: citește toate if-urile înainte de a decide pe ce ramură intră un apel.