Urmărirea funcțiilor recursive cu afișări

Regula de aur

Într-o funcție recursivă, instrucțiunile de DINAINTEA autoapelului se execută la COBORÂRE (în ordinea apelurilor), iar cele de DUPĂ autoapel se execută la ÎNTOARCERE (în ordine INVERSĂ).

Exemplul canonic

#include <iostream>
using namespace std;

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

int main() {
    f(3);
    return 0;
}

Pentru f(3) se afișează: 3 2 1 1 2 3.

Coborâre (înainte de autoapel): 3, 2, 1; apoi f(0) nu face nimic; întoarcere (după autoapel): 1, 2, 3.

Variațiile care pică la BAC

1. Doar înainte → numerele descrescător: 3 2 1.

2. Doar după → crescător: 1 2 3 (afișarea "amânată" până la întoarcere).

3. Cu condiție de paritate:

#include <iostream>
using namespace std;

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

int main() {
    g(5);
    return 0;
}

Pentru g(4): coborâre afișează parele (4, 2), întoarcere afișează imparele în ordine inversă a coborârii (1, 3): rezultat 4 2 1 3.

Tehnica arborelui de apeluri (pentru două autoapeluri)

#include <iostream>
using namespace std;

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

int main() {
    for (int i = 0; i <= 10; i++)
        cout << fib(i) << " ";
    return 0;
}

fib(4): desenezi arborele: fib(4) → fib(3) + fib(2); fib(3) → fib(2)+fib(1); fib(2) → fib(1)+fib(0). Frunzele dau 1,0,1,1,0 → fib(4) = 3. Numărul de apeluri: 9 (inclusiv rădăcina): la subiectele "de câte ori se apelează", numeri NODURILE arborelui.

Greșeli frecvente

1. Afișările de după autoapel apar în ordine INVERSĂ: cel mai adânc apel se "întoarce" primul.
2. Condiția de oprire nu afișează nimic dacă e if (n > 0) {...} fără ramură else.
3. La două autoapeluri, ordinea e stânga complet, apoi dreapta: nu "în paralel".