Apeluri recursive la BAC: coborâre și revenire

Urmărirea unui subprogram recursiv cere să separi coborârea prin apeluri de revenirea din ele. La BAC, ordinea afișării depinde de locul instrucțiunii față de apelul recursiv. O afișare de dinaintea apelului se execută la coborâre; una de după apel așteaptă întoarcerea și se execută la revenire.

Lecția privește recursivitatea de la matematică-informatică. Vom urmări un subprogram care împarte argumentul la doi și afișează informații în ambele momente. Înainte de a scrie rezultatul unui exercițiu de BAC, notează condiția de oprire și valoarea argumentului fiecărui apel.

Fiecare apel are propria valoare a parametrului

Când o funcție se apelează pe ea însăși cu un argument mai mic, noul apel are propriul parametru local. Parametrul apelului anterior nu este înlocuit automat de cel nou dacă transmiterea este prin valoare.

Apelul anterior rămâne suspendat la locul apelului recursiv. După terminarea apelului mai adânc, execuția continuă cu instrucțiunea următoare, folosind valorile locale ale cadrului la care s-a revenit.

Această regulă explică de ce o variabilă poate avea valoarea unu într-un apel și valoarea trei în apelul care îl așteaptă. Nu există un singur parametru global care scade permanent și apoi trebuie refăcut manual.

Program C++ pentru urmărire

Programul citește un număr natural de cel mult un miliard. La coborâre afișează argumentul pozitiv al fiecărui apel. Cazul de bază afișează o bară verticală, iar la revenire sunt afișate resturile împărțirii la doi ale argumentelor locale.

#include <iostream>
using namespace std;

void urmareste(int n) {
    if (n == 0) {
        cout << "| ";
        return;
    }
    cout << n << ' ';
    urmareste(n / 2);
    cout << n % 2 << ' ';
}

int main() {
    int n;
    cin >> n;
    urmareste(n);
    return 0;
}

Instrucțiunea de întoarcere din cazul de bază împiedică executarea restului corpului pentru zero. Fără această oprire, un apel cu zero ar putea produce un nou apel cu zero și recursivitatea nu s-ar încheia.

Coborârea pentru argumentul treisprezece

Primul apel are argumentul treisprezece și îl afișează. Apoi apelează funcția cu șase, deoarece împărțirea întreagă la doi elimină partea fracționară. Apelul cu șase afișează șase și continuă cu trei.

Urmează apelul cu trei, apoi cel cu unu și, în final, cel cu zero. Până în acel moment s-au afișat argumentele pozitive în ordinea treisprezece, șase, trei, unu. Apelul cu zero afișează separatorul și se încheie.

Adâncime, de la zero	Argument	Apel următor	Rest care așteaptă revenirea
0	13	6	1
1	6	3	0
2	3	1	1
3	1	0	1
4	0	Niciunul	Niciunul

Ultima coloană nu este afișată în timpul coborârii. Ea arată ce operație rămâne de executat în fiecare apel după întoarcerea apelului următor.

Revenirea are ordinea inversă apelurilor

Primul apel reluat este cel cu argumentul unu. El afișează restul unu și se încheie. Apelul cu trei afișează apoi restul unu, cel cu șase afișează zero, iar apelul inițial afișează unu.

Rezultatul complet, ignorând spațiul final, este 13 6 3 1 | 1 1 0 1. Secvența de după separator este scrierea binară a lui treisprezece. Programul nostru afișează însă și urma de coborâre, deci nu este doar un convertor de bază.

Nu citi coloana resturilor de sus în jos pentru afișarea de după apel. Resturile sunt produse în ordinea revenirii, de la cel mai adânc apel pozitiv către primul. Aceasta este diferența centrală a exercițiului.

Ce se schimbă dacă muți afișarea

Dacă afișarea restului ar fi pusă înaintea apelului recursiv, resturile ar apărea în ordinea extragerii, de la cifra binară mai puțin semnificativă către cea mai semnificativă. Pentru treisprezece, această ordine ar fi unu, zero, unu, unu.

Afișarea după apel inversează ordinea temporală a acestor rezultate fără să construiască un vector explicit. Stiva apelurilor păstrează implicit informațiile necesare revenirii.

Mutarea unei singure instrucțiuni poate schimba rezultatul, chiar dacă argumentele apelurilor rămân aceleași. De aceea, nu este suficient să identifici o formulă recursivă familiară; trebuie să urmărești corpul exact al subprogramului.

Cazul zero și numărul apelurilor

Pentru intrarea zero, programul afișează doar separatorul. Acesta este comportamentul definit de codul de urmărire. Un convertor obișnuit care trebuie să afișeze reprezentarea binară a lui zero ar avea nevoie de o convenție de ieșire diferită.

Pentru o intrare pozitivă, există câte un apel pozitiv pentru fiecare cifră binară, plus apelul de bază cu zero. La treisprezece avem patru apeluri pozitive și unul de bază, deci cinci apeluri în total.

Numărul afișărilor este diferit de numărul apelurilor. Fiecare apel pozitiv afișează de două ori, iar cazul de bază o singură dată. Pentru exemplul dat apar nouă elemente de ieșire: patru argumente, separatorul și patru resturi.

Cum demonstrezi că recursivitatea se termină

Pentru un argument întreg pozitiv, împărțirea întreagă la doi produce un număr natural strict mai mic. Repetarea operației ajunge la zero. Cazul de bază este astfel accesibil din orice intrare pozitivă admisă.

Nu este suficient să existe o condiție de oprire în textul funcției. Argumentele trebuie să se apropie de ea. Un apel care ar transmite aceeași valoare ar repeta aceeași stare și nu ar ajunge la bază pentru un argument pozitiv.

Restricția la numere naturale simplifică demonstrația. Dacă domeniul ar include alte tipuri sau valori, ar trebui analizată din nou evoluția argumentului și sensul operațiilor folosite.

Timp și memorie

Adâncimea crește proporțional cu numărul de împărțiri la doi necesare pentru a ajunge la zero. Pentru un număr pozitiv, aceasta este de ordin logaritmic în valoarea numărului. La fiecare nivel se execută un număr constant de operații în modelul obișnuit pentru întregii limitați ai problemei.

Memoria apelurilor crește cu aceeași adâncime, deoarece apelurile anterioare așteaptă revenirea. Nu spune că memoria este constantă doar pentru că nu ai declarat un vector: stiva de apeluri ocupă și ea memorie.

Această analiză este un bun exercițiu de înțelegere a execuției, dincolo de memorarea codului. Numără stările active, nu numai variabilele scrise într-un singur corp de funcție.

Exerciții cu răspunsuri

Intrarea este unu. Se afișează 1 | 1. Există un apel pozitiv și un apel de bază.

Intrarea este doi. Se afișează 2 1 | 1 0. Restul lui doi apare ultimul, după revenirea din apelul cu unu.

Intrarea este opt. Se afișează 8 4 2 1 | 1 0 0 0. Sunt cinci apeluri, incluzând zero.

Întrebări frecvente

Parametrul apelului anterior devine zero?

Nu. Fiecare apel are propria copie a parametrului. La revenire se reia execuția cu valoarea locală a acelui apel.

Returnarea din cazul de bază încheie tot programul?

Nu. Încheie apelul curent și întoarce controlul către apelul care îl aștepta. Acesta poate avea instrucțiuni rămase de executat.

Cum verific rapid ordinea afișării?

Scrie apelurile pe verticală și notează separat afișările de la coborâre și cele de la revenire. Pentru o explicație pe un cod propriu, poți consulta un profesor de informatică.