Școala Româno-Britanică
Modulul 5 Clasa a X-a | C++

Ora 2: Factorialul recursiv

Ce vei învăța astăzi: Ce este factorialul (produsul numerelor de la 1 la n), definiția sa recursivă (n! = n · (n - 1)!) și mecanismul stivei de apeluri (zona de memorie în care se salvează apelurile în curs de executare), comparat cu varianta iterativă (varianta care folosește o buclă repetitivă în loc de apeluri recursive)

Rezultat practic: Scrii și explici funcția recursivă a factorialului în C++, urmărind executarea pe stivă (Competența 2.5)

Competența 2.5 Săptămâna 25

Înainte de a începe

De ce contează? Factorialul este exemplul clasic de funcție recursivă din programa de BAC și se folosește în combinatorică (aranjamente, combinări), unde apare des în problemele de test.

Ce știi deja?

Din ora 1, poți explica ce este cazul de bază și pasul recursiv? Poți scrie factorialul cu o buclă for și știi de ce 0! = 1?

Ideea-cheie: Definiția recursivă a factorialului este n! = n · (n - 1)!, cu cazul de bază 0! = 1.
SINTEZĂ TEORETICĂ ȘI EXEMPLE GHIDATE

Ce vei învăța astăzi?

După această lecție vei scrie funcția recursivă a factorialului, vei explica mecanismul de executare prin stiva apelurilor și vei compara varianta recursivă cu cea iterativă.

Definiția recursivă: n! = n · (n-1)!
Cazul de bază: 0! = 1
Stiva apelurilor pentru factorial(4)
Comparație cu varianta iterativă

Definiția factorialului

Definiție: Factorialul unui număr natural n, notat n!, este produsul numerelor de la 1 la n. Prin convenție, 0! = 1.

Definiția recursivă: factorial(n) = n * factorial(n - 1), cu cazul de bază factorial(0) = 1.

n n! Calcul recursiv
0 1 cazul de bază
1 1 1 · factorial(0) = 1 · 1
2 2 2 · factorial(1) = 2 · 1
3 6 3 · factorial(2) = 3 · 2
4 24 4 · factorial(3) = 4 · 6

Funcția factorial recursivă în C++

Algoritm factorial(n): dacă n == 0 atunci returnează 1 altfel returnează n * factorial(n - 1)
Program C++ - factorial recursiv
#include <iostream>
using namespace std;

long long factorial(int n)
{
    if (n == 0)
        return 1;
    return n * factorial(n - 1);
}

int main()
{
    int n;
    cout << "n = ";
    cin >> n;
    cout << factorial(n);
    return 0;
}
Stiva apelurilor pentru factorial(4)
Coborârefactorial(4) = 4 · factorial(3)
Coborârefactorial(3) = 3 · factorial(2)
Coborârefactorial(2) = 2 · factorial(1)
Coborârefactorial(1) = 1 · factorial(0)
Bazăfactorial(0) = 1 (cazul de bază, ne oprim)
Urcarefactorial(1) = 1 · 1 = 1
Urcarefactorial(2) = 2 · 1 = 2
Urcarefactorial(3) = 3 · 2 = 6
Urcarefactorial(4) = 4 · 6 = 24

Comparație cu varianta iterativă

Program C++ - factorial iterativ (buclă for)
#include <iostream>
using namespace std;

int main()
{
    int n;
    long long f = 1;
    cin >> n;
    for (int i = 2; i <= n; i++)
        f = f * i;
    cout << f;
    return 0;
}

De reținut

  • Ambele variante dau același rezultat; recursivitatea folosește stiva, iar iterația folosește o variabilă.
  • Pentru n mare, factorialul crește foarte repede; folosim long long.
  • Cazul de bază este esențial: fără el, funcția se apelează la nesfârșit.

Exercițiu de completare

Completează enunțul despre factorial cu cuvintele potrivite:

Factorialul unui număr natural n, notat ______, este produsul numerelor de la 1 la n. Prin convenție, ______ = 1, care reprezintă ______. Pentru n > 0, n! = n · ______, numit pas ______.

Bancă de cuvinte:
n! 0! cazul de bază (n-1)! recursiv

Exercițiu de completare

Completează funcția factorial din codul C++ de mai jos:
______ factorial(int n)
{
    ______ (n == 0)
        ______ 1;
    ______ n * factorial(n - 1);
}
Bancă de cuvinte:
long long if return

Test de înțelegere

Test rapid - factorial:

1. Cazul de bază pentru factorial este:

2. factorial(3) are valoarea:

3. În stiva apelurilor, primul apel efectuat este:

Ai grijă la: tipul de return - pentru n ≥ 13 factorialul depășește domeniul int, deci folosește long long.

Aprofundare

Creșterea rapidă și depășirea tipului de date. Factorialul crește extrem de repede: 10! = 3.628.800, 13! = 6.227.020.800 (depășește int), iar 20! ≈ 2,43 × 10⁸, valoare care depășește și long long. Din acest motiv, funcția factorial trebuie declarată cu tipul de return long long și folosită cu prudență pentru valori mari ale lui n.

Adâncimea recursivității. Pentru n mic (de exemplu 20), stiva suportă fără probleme cei 20 de apeluri impuse. Pentru valori foarte mari, însă, numărul de apeluri poate umple stiva; varianta iterativă cu buclă for nu are această problemă și este de preferat când performanța și siguranța sunt importante.

Cazuri particulare.

  • factorial(0) = 1 prin convenție matematică: produsul gol este 1, exact cazul de bază.
  • factorial(1) = 1; pentru n = 1 funcția poate returna direct 1, dar apelul factorial(0) este și el corect.
  • Ordinea înmulțirii n * factorial(n - 1) este identică cu factorial(n - 1) * n, dar prima formă este mai ușor de urmărit pe stivă.
  • Pentru n negativ, funcția ar intra în recursie infinită; validarea intrării evită această problemă.
APLICARE ȘI REZOLVARE DE PROBLEME

PbInfo - Factorial

Enunț:

Cerință: Se citește un număr natural n. Să se afișeze n! (factorialul lui n), folosind un subprogram recursiv.

Date de intrare:

Programul citește de la tastatură numărul natural n.

Date de ieșire:

Programul va afișa pe ecran valoarea n!.

Restricții și precizări:

0 ≤ n ≤ 20. Rezultatul încape într-un număr de tip long long.

Exemplu:

Intrare:

5

Ieșire:

120
Cum gândim soluția:
  1. Definim funcția factorial(n) care întoarce long long
  2. Cazul de bază: dacă n == 0, întoarcem 1
  3. Altfel întoarcem n * factorial(n - 1)
  4. În main citim n și afișăm factorial(n)
Scrie soluția în C++:
Soluție corectă:
#include <iostream>
using namespace std;

long long factorial(int n)
{
    if (n == 0)
        return 1;
    return n * factorial(n - 1);
}

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

Ce învățăm: cazul de bază 0! = 1 oprește recurența, iar rezultatul se construiește la urcarea pe stivă.

PbInfo - Suma factorialelor

Enunț:

Cerință: Se citește un număr natural n. Să se calculeze suma 1! + 2! + ... + n!, folosind un subprogram recursiv pentru factorial.

Date de intrare:

Programul citește de la tastatură numărul natural n.

Date de ieșire:

Programul va afișa pe ecran suma factorialelor.

Restricții și precizări:

1 ≤ n ≤ 20. Rezultatul poate fi mare, folosiți tipul long long.

Exemplu:

Intrare:

4

Ieșire:

33
Cum gândim soluția:
  1. Definim funcția recursivă factorial(n)
  2. În main parcurgem cu o buclă de la 1 la n
  3. Adunăm la suma s valoarea factorial(i)
  4. Afișăm suma
Scrie soluția în C++:
Soluție corectă:
#include <iostream>
using namespace std;

long long factorial(int n)
{
    if (n == 0)
        return 1;
    return n * factorial(n - 1);
}

int main()
{
    int n;
    long long s = 0;
    cin >> n;
    for (int i = 1; i <= n; i++)
        s = s + factorial(i);
    cout << s;
    return 0;
}

Ce învățăm: un subprogram recursiv poate fi apelat de mai multe ori, din interiorul unei bucle, pentru a calcula o sumă.

EXERCIȚII PRACTICE

Exercițiul Practic: Factorialul în practică

Sarcini de lucru

Rezolvă sarcinile următoare pentru a stăpâni factorialul recursiv

Sarcina 1: Program cu factorial

Cerință: Scrie un program C++ care citește n și afișează pe ecran valoarea n! folosind o funcție recursivă. Testează pentru n = 6 (rezultatul trebuie să fie 720).

Soluție pentru Sarcina 1:
#include <iostream>
using namespace std;

long long factorial(int n)
{
    if (n == 0)
        return 1;
    return n * factorial(n - 1);
}

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

Verifică: pentru n = 6, factorial(6) = 720.

Sarcina 2: Stiva apelurilor

Cerință: Scrie pe foaie (sau în căsuța de mai jos) secvența apelurilor pentru factorial(5), apoi valorile întoarse la fiecare urcare pe stivă.

Soluție pentru Sarcina 2:
Coborâre: factorial(5), factorial(4), factorial(3),
factorial(2), factorial(1), factorial(0) - caz de bază

Urcare:
factorial(0) = 1
factorial(1) = 1 * 1 = 1
factorial(2) = 2 * 1 = 2
factorial(3) = 3 * 2 = 6
factorial(4) = 4 * 6 = 24
factorial(5) = 5 * 24 = 120

Scrie pe caiet

Titlul lecției

Factorialul recursiv. A doua lecție din Modulul 5 îți arată cum se calculează factorialul cu o funcție recursivă.

Definiția lecției

Factorialul unui număr natural n, notat n!, este produsul numerelor de la 1 la n, cu convenția 0! = 1. Definiția recursivă este factorial(n) = n · factorial(n - 1), cu cazul de bază factorial(0) = 1. La fiecare apel, funcția se reapelează cu n - 1, coborând pe stiva apelurilor până la cazul de bază. La întoarcere, înmulțirile se efectuează în ordine inversă: factorial(1) = 1, factorial(2) = 2, factorial(3) = 6, factorial(4) = 24. Factorialul crește extrem de repede: pentru n ≥ 13 rezultatul depășește tipul int, deci se folosește long long. Varianta iterativă cu buclă for dă același rezultat fără a folosi stiva, fiind preferabilă pentru valori mari ale lui n.

Definiții esențiale

Algoritmul cheie - pseudocod

Algoritm factorial(n): dacă n == 0 atunci returnează 1 altfel returnează n * factorial(n - 1)

Algoritmul cheie - cod C++

Program C++ - factorial recursiv
#include <iostream>
using namespace std;

long long factorial(int n)
{
    if (n == 0)
        return 1;
    return n * factorial(n - 1);
}

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

Greșeli comune de evitat

Exemplu practic

Scenariu real: în câte moduri pot fi așezați 6 elevi pe un rând de bănci? Răspunsul este 6! = 720. Funcția recursivă rezolvă calculul imediat:

Program C++ - factorial (exemplu practic)
long long factorial(int n)
{
    if (n == 0)
        return 1;
    return n * factorial(n - 1);
}

Apelul factorial(6) întoarce 720 de posibilități.

Sfaturi practice și trucuri