Subprograme recursive

Recursivitatea este un mecanism general de elaborare a algoritmilor.

Recursivitate directă și indirectă

Forma generală cuprinde întotdeauna o condiție de oprire și o ramură pe care se face autoapelul.

tip_returnat nume_functie(lista de parametri) {
    if (conditie_de_oprire)
        instructiune;
    else
        nume_functie(lista de parametri);
}

def nume_functie(lista de parametri):
    if conditie_de_oprire:
        instructiune
    else:
        nume_functie(lista de parametri)

bool impar(int n);              // prototipul, fara corp

bool par(int n) {
    if (n == 0) return true;
    else        return impar(n - 1);
}

bool impar(int n) {
    if (n == 0) return false;
    else        return par(n - 1);
}

def par(n):
    if n == 0:
        return True
    else:
        return impar(n - 1)

def impar(n):
    if n == 0:
        return False
    else:
        return par(n - 1)

Mecanismul recursivității

Pe segmentul de stivă se păstrează, la fiecare apel:

• variabilele locale ale subprogramului;
• parametrii formali, adică valorile sau referințele transmise la apel;
• adresa de revenire, adică locul din program unde execuția se întoarce după ce subprogramul se încheie.

Ce se întâmplă la fiecare apel

De câte ori se autoapelează subprogramul, se creează un nivel nou. Așa se explică de ce toate activările lui se află deodată în stivă.

Fiecare autoapel primește o zonă nouă de memorie, deci și o definire nouă a variabilelor locale: variabila locală este unică pentru un apel. Dacă subprogramul se apelează recursiv de n ori, există n imagini ale aceleiași variabile, câte una pentru fiecare apel, fiecare cu conținutul ei.

La calculul lui 5! sunt 6 apeluri: pentru 5, 4, 3, 2, 1 și 0.

Subprogram-funcție: factorialul

Un subprogram-funcție recursiv întoarce o valoare prin return. Factorialul se calculează după formula:

factorial(x) = 1,                       dacă x = 0
factorial(x) = x · factorial(x − 1),    dacă x ≥ 1

long long factorial(int x) {
    if (x == 0)
        return 1;               // conditia de oprire
    else
        return x * factorial(x - 1);   // autoapelul
}

int main() {
    int n;
    cin >> n;
    cout << "Factorial " << factorial(n);
    return 0;
}

def factorial(x):
    if x == 0:
        return 1                       # conditia de oprire
    else:
        return x * factorial(x - 1)    # autoapelul

n = int(input())
print('Factorial', factorial(n))

Evoluția parametrului la coborâre și la revenire

La coborâre se rețin pe fiecare nivel valorile 5, 4, 3, 2, 1, 0. Înmulțirile se fac abia la revenire, de la baza stivei spre vârf:

Desfășurat, calculul arată așa:

factorial(5) = 5 · factorial(4)
             = 5 · 4 · factorial(3)
             = 5 · 4 · 3 · factorial(2)
             = 5 · 4 · 3 · 2 · factorial(1)
             = 5 · 4 · 3 · 2 · 1 · factorial(0)
             = 5 · 4 · 3 · 2 · 1 · 1 = 120

Niciun rezultat nu se obține la coborâre. Toate se obțin la revenire, iar valoarea este întoarsă prin return din apel în apel, până la programul principal.

Subprogram-procedură: afișarea cifrelor

Un subprogram-procedură recursiv nu întoarce nimic; el afișează. Aici nu mai contează valoarea întoarsă prin return, ci unde este scrisă afișarea față de autoapel.

void cifre(int n) {
    if (n > 9)
        cifre(n / 10);
    cout << n % 10 << " ";
}

int main() {
    cifre(357);
    return 0;
}

def cifre(n):
    if n > 9:
        cifre(n // 10)
    print(n % 10, end=' ')

cifre(357)

Evoluția parametrului

Fiecare apel are copia lui de n. La coborâre se rețin, prin împărțiri succesive la 10, valorile 357, 35, 3. La revenire, fiecare nivel afișează n % 10 din copia lui:

Se afișează 3 5 7, adică cifrele în ordinea firească, deși împărțirile le-au dat de la ultima spre prima. Ordinea se inversează fiindcă afișarea este scrisă după autoapel. Mutată înaintea lui, s-ar afișa 7 5 3.