Recursivitate C++: cazul de bază și stiva apelurilor

O funcție recursivă se apelează pe ea însăși pentru o problemă mai mică. Apelul curent rămâne în așteptare până când apelul nou întoarce un rezultat. Pentru a înțelege execuția trebuie urmărite atât coborârea spre cazul de bază, cât și revenirea către primul apel.

Ai nevoie de funcții și parametri. Recursivitatea nu este o instrucțiune nouă în limbaj: este un mod de a organiza apelurile unor funcții obișnuite.

Două condiții pentru oprire

Mai întâi definim un caz de bază, care poate fi rezolvat fără alt apel recursiv. Apoi ne asigurăm că fiecare apel nou se apropie de acel caz. O condiție de oprire scrisă în cod nu este suficientă dacă argumentele nu ajung niciodată să o îndeplinească.

Pentru factorialul unui număr natural folosim 0! = 1 și, pentru n > 0, relația n! = n * (n - 1)!. Cazul de bază este n == 0. La fiecare pas micșorăm argumentul cu unu, deci pornind de la un număr natural ajungem la zero după un număr finit de apeluri.

Dacă am apela funcția cu un număr negativ, această justificare nu ar mai fi valabilă. Contractul de intrare trebuie respectat. Nu adăuga mecanic n <= 0 doar ca să ascunzi o intrare pentru care factorialul din enunț nu este definit.

Fact(3): coborâre și revenire

Apelul pentru 3 are nevoie de rezultatul pentru 2; acesta are nevoie de rezultatul pentru 1, care îl cere pe cel pentru 0. La zero întoarcem 1. Abia apoi putem calcula, în ordine inversă, rezultatele 1, 2 și 6.

Apelurile coboară până la zero; înmulțirile se termină la revenire.Redă animațiaO singură rulare · 11 secunde

Fiecare apel are propriul parametru n. Valoarea 3 din primul apel nu se transformă în 2: se creează un alt apel cu alt parametru. Stiva de apeluri păstrează informațiile necesare pentru a continua apelurile suspendate. Ultimul apel început este primul care se încheie în acest lanț.

Programul recursiv

Programul citește n, cu 0 <= n <= 20, și afișează factorialul lui. Folosim long long, deoarece 20! = 2432902008176640000 încape într-un întreg cu semn de 64 de biți. 21! depășește acel interval, deci nu face parte din intrarea permisă.

#include <iostream>
long long factorial(int n) {
    if (n == 0) {
        return 1;
    }
    long long maiMic = factorial(n - 1);
    return n * maiMic;
}
int main() {
    int n = 0;
    std::cin >> n;
    std::cout << factorial(n) << '\n';
    return 0;
}

Pentru n = 3, rezultatul este 6. Pentru n = 0, rezultatul este 1, nu zero. Un acumulator sau un caz de bază egal cu zero ar anula toate înmulțirile și ar strica formula.

Am separat apelul recursiv de înmulțire prin variabila maiMic, astfel încât ordinea este vizibilă. Instrucțiunea de returnare a produsului se execută numai după ce apelul factorial(n - 1) s-a încheiat. Nu există o afișare intermediară în funcție, deci programul produce o singură linie.

Aceeași cerință, rezolvată iterativ

Factorialul poate fi calculat și cu o buclă. Programul următor acceptă exact aceleași intrări și produce aceleași rezultate. Pentru n = 0, bucla nu se execută și păstrăm valoarea inițială 1.

#include <iostream>
int main() {
    int n = 0;
    std::cin >> n;
    long long rezultat = 1;
    for (int i = 1; i <= n; ++i) {
        rezultat *= i;
    }
    std::cout << rezultat << '\n';
    return 0;
}

Ambele soluții fac un număr liniar de operații, deci au timp O(n). Varianta recursivă poate avea n + 1 apeluri active simultan și folosește O(n) spațiu de stivă. Varianta iterativă folosește un număr constant de variabile, deci O(1) spațiu suplimentar. Această comparație arată de ce recursivitatea nu este automat mai eficientă.

Greșeli care schimbă execuția

Dacă apelul ar fi factorial(n), argumentul nu s-ar micșora și execuția nu ar ajunge la cazul de bază pentru n > 0. Dacă am elimina cazul de bază, apelurile ar continua dincolo de zero. În ambele situații programul nu mai respectă raționamentul de terminare și poate epuiza stiva.

Chiar și o recursie corectă poate depăși resursele când adâncimea este foarte mare. Limita practică de stivă depinde de mediu și de mărimea fiecărui apel; nu presupune o valoare universală. Aici adâncimea maximă este 21, explicit limitată de enunț, iar costul poate fi urmărit pe exemple mici.

Exersează

1. Câte apeluri se fac pentru factorial(3), inclusiv cazul de bază?
2. Ce valoare întoarce apelul pentru 1?
3. De ce 21 nu este acceptat în programul prezentat?
4. Ce se întâmplă cu parametrul primului apel când începe apelul următor?

Răspunsuri: patru; 1; rezultatul nu încape într-un long long cu semn de 64 de biți; parametrul rămâne în apelul suspendat, iar noul apel primește propriul n.

Continuă cu divide et impera.