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

Ora 1: Recursivitatea - concept și mecanism de executare

Ce vei învăța astăzi: Ce este o funcție recursivă (o funcție care se apelează pe ea însăși), care sunt cazul de bază (condiția care oprește apelurile) și pasul recursiv (apelul funcției cu un parametru mai mic) și cum funcționează stiva apelurilor (zona de memorie în care se salvează apelurile în curs de executare)

Rezultat practic: Înțelegi conceptul de recursivitate și scrii primul subprogram recursiv în C++, explicând mecanismul de executare al acestuia (Competența 1.5).

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

Înainte de a începe

De ce contează? Recursivitatea stă la baza tuturor algoritmilor din acest modul (factorial, Fibonacci, CMMDC, Hanoi) și apare frecvent atât la teorie, cât și la programare în evaluare.

Ce știi deja?

Poți defini și apela o funcție simplă în C++? Care este diferența dintre parametrii formali și cei efectivi?

Ideea-cheie: Orice funcție recursivă are două părți obligatorii: cazul de bază, care oprește apelurile, și pasul recursiv, care reduce problema.
SINTEZĂ TEORETICĂ ȘI EXEMPLE GHIDATE

Ce vei învăța astăzi?

După această lecție vei înțelege ce este o funcție recursivă, vei identifica cazul de bază și pasul recursiv și vei explica mecanismul stivei de apeluri.

Definiția funcției recursive
Cazul de bază și pasul recursiv
Stiva apelurilor
Primul subprogram recursiv în C++

Ce este o funcție recursivă?

Definiție: O funcție recursivă este o funcție care se apelează pe ea însăși, direct sau indirect, pentru a rezolva o problemă prin descompunerea ei în subprobleme mai mici, asemănătoare problemei inițiale.

O funcție recursivă este formată din două părți obligatorii: cazul de bază (condiția de oprire) și pasul recursiv (apelul funcției cu un parametru mai mic).

Analogia: păpușile rusești

Imaginează-ți o matrioșcă (păpușă rusească): înăuntru se află o păpușă mai mică, identică ca formă, în ea alta și mai mică, și tot așa, până la cea mai mică, care nu mai conține nimic.

Păpușa cea mai mică

Este cazul de bază: se oprește descompunerea

O păpușă mare

Rezolvă problema deschizând-o pe cea din interior

Deschiderea repetată

Este pasul recursiv: se repetă pentru o păpușă mai mică

Parte Rol Exemplu
Cazul de bază Oprește recurența if (n == 0) return;
Pasul recursiv Reducerea problemei numara(n - 1);

Mecanismul stivei de apeluri

Definiție: Stiva este o structură de date de tip LIFO (ultimul introdus, primul scos). La fiecare apel recursiv, valorile parametrilor și adresa de revenire sunt impuse pe stivă. La întoarcerea din apel, ele sunt eliminate de pe stivă.

Exemplu: numărare de la n la 1

Funcția numara(n) afișează valoarea lui n și apoi se apelează cu n - 1:

Algoritm numara(n): dacă n == 0 atunci returnează altfel afișează n numara(n - 1)
Program C++ - numărare descrescătoare recursivă
#include <iostream>
using namespace std;

void numara(int n)
{
    if (n == 0)
        return;
    cout << n << " ";
    numara(n - 1);
}

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

Observă: pentru numara(3) se afișează 3, apoi 2, apoi 1. Cazul de bază n == 0 oprește recurența și apelurile se „deapilează" în ordine inversă.

Stiva apelurilor pentru numara(3)
n = 3
1Apel numara(3): n != 0, afișăm 3
2Apel numara(2): n != 0, afișăm 2
3Apel numara(1): n != 0, afișăm 1
4Apel numara(0): cazul de bază, ne oprim

Numărare crescătoare: ordinea contează

Dacă mutăm afișarea după apelul recursiv, ordinea se inversează: afișarea se face la „deapilare", deci numerele apar crescător.

Program C++ - numărare crescătoare recursivă
#include <iostream>
using namespace std;

void numara(int n)
{
    if (n == 0)
        return;
    numara(n - 1);
    cout << n << " ";
}

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

De reținut

  • Fără caz de bază, funcția se apelează la nesfârșit și stiva se umple (eroare de depășire a stivei).
  • Instrucțiunile dinaintea apelului recursiv se execută la „coborâre" pe stivă.
  • Instrucțiunile de după apelul recursiv se execută la „urcare" (întoarcere) pe stivă.

Exercițiu de completare

Completează enunțul despre recursivitate cu cuvintele potrivite:

O funcție ______ este o funcție care se ______ pe ea însăși. Condiția care oprește recurența se numește caz de ______, iar apelul funcției cu un parametru mai mic se numește pas ______. Apelurile sunt memorate într-o structură de tip ______, numită stivă.

Bancă de cuvinte:
recursivă apelează bază recursiv LIFO

Exercițiu de completare

Completează fragmentul de cod C++ cu termenii potriviți:
______ numara(int n)
{
    ______ (n == 0)
        ______;
    cout << n << " ";
    numara(n - 1);
}
Bancă de cuvinte:
void if return

Test de înțelegere

Test rapid - recursivitate:

1. O funcție recursivă este o funcție care...

2. Condiția care oprește apelurile recursive se numește:

3. Dacă o funcție recursivă nu are caz de bază, programul:

Ai grijă la: să nu uiți cazul de bază - fără el funcția se apelează la nesfârșit și programul se blochează cu depășirea stivei.

Aprofundare

Recursivitate directă și indirectă. Recursivitatea este directă atunci când o funcție se apelează pe ea însăși, și indirectă atunci când două sau mai multe funcții se apelează una pe cealaltă într-un ciclu (de exemplu f() apelează g(), iar g() apelează f()). În ambele cazuri trebuie să existe cel puțin un caz de bază care oprește lanțul de apeluri, altfel programul se blochează cu depășirea stivei.

Adâncimea stivei și limita practică. La fiecare apel recursiv, sistemul de operare rezervă memorie pe stivă pentru parametri și adresa de revenire. Pentru valori mari ale lui n, numărul de apeluri impuse simultan poate depăși capacitatea stivei (de obicei câteva milioane de cadre pe un calculator obișnuit). Din acest motiv, pentru prelucrări cu multe iterații, varianta iterativă cu bucle for sau while este adesea preferabilă.

Cazuri particulare importante.

  • O funcție recursivă fără caz de bază produce recursie infinită, iar programul se termină cu eroarea „stack overflow".
  • Un caz de bază incorect (de exemplu n < 0 în loc de n == 0) poate produce rezultate greșite sau apeluri infinite.
  • Instrucțiunile aflate înaintea apelului recursiv se execută la coborârea pe stivă, iar cele aflate după apel se execută la întoarcere. Această ordine determină sensul afișării.
APLICARE ȘI REZOLVARE DE PROBLEME

PbInfo - Numere de la 1 la n

Enunț:

Cerință: Se citește un număr natural n. Să se afișeze, recursiv, numerele de la 1 la n, separate prin spații.

Date de intrare:

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

Date de ieșire:

Programul va afișa pe ecran numerele de la 1 la n, separate prin spații.

Restricții și precizări:

1 ≤ n ≤ 1000. Rezolvarea trebuie făcută cu un subprogram recursiv.

Exemplu:

Intrare:

5

Ieșire:

1 2 3 4 5
Cum gândim soluția:
  1. Definim funcția recursivă numara(n) care afișează de la 1 la n
  2. Cazul de bază: dacă n == 0, ne oprim
  3. Apelăm numara(n - 1) și abia apoi afișăm n (afișare la deapilare)
Scrie soluția în C++:
Soluție corectă:
#include <iostream>
using namespace std;

void numara(int n)
{
    if (n == 0)
        return;
    numara(n - 1);
    cout << n << " ";
}

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

Ce învățăm: afișarea plasată după apelul recursiv face ca numerele să apară crescător, deoarece are loc la întoarcerea din apeluri, pe stivă.

PbInfo - Numere de la n la 1

Enunț:

Cerință: Se citește un număr natural n. Să se afișeze, recursiv, numerele de la n la 1, separate prin spații.

Date de intrare:

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

Date de ieșire:

Programul va afișa pe ecran numerele de la n la 1, separate prin spații.

Restricții și precizări:

1 ≤ n ≤ 1000. Rezolvarea trebuie făcută cu un subprogram recursiv.

Exemplu:

Intrare:

5

Ieșire:

5 4 3 2 1
Cum gândim soluția:
  1. Definim funcția recursivă numara(n)
  2. Cazul de bază: dacă n == 0, ne oprim
  3. Afișăm n și apoi apelăm numara(n - 1) (afișare la coborâre)
Scrie soluția în C++:
Soluție corectă:
#include <iostream>
using namespace std;

void numara(int n)
{
    if (n == 0)
        return;
    cout << n << " ";
    numara(n - 1);
}

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

Ce învățăm: afișarea plasată înaintea apelului recursiv are loc la coborârea pe stivă, deci numerele apar descrescător.

EXERCIȚII PRACTICE

Exercițiul Practic: Primele subprograme recursive

Sarcini de lucru

Completează următoarele sarcini pentru a-ți consolida cunoștințele despre recursivitate

Sarcina 1: Scrie un program recursiv

Cerință: Scrie un program C++ care afișează, recursiv, pătratele numerelor de la n la 1, separate prin spații. De exemplu, pentru n = 4 se afișează 16 9 4 1.

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

void patrate(int n)
{
    if (n == 0)
        return;
    cout << n * n << " ";
    patrate(n - 1);
}

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

Verifică: pentru n = 4, cazul de bază este n == 0, iar afișarea pătratului are loc înaintea apelului recursiv.

Sarcina 2: Urmărește stiva apelurilor

Cerință: Pentru funcția numara(n) de mai jos, scrie valorile afișate pentru n = 3 și explică ordinea în care apar.

Soluție pentru Sarcina 2:
Apelurile se fac la coborârea pe stivă:
numara(3) -> numara(2) -> numara(1) -> numara(0) (oprire)

Afișarea are loc la întoarcere (deapilare), deci se afișează:
1 2 3

Verifică: deoarece cout este după apelul recursiv, valorile apar în ordine crescătoare.

Scrie pe caiet

Titlul lecției

Recursivitatea - concept și mecanism de executare. Prima lecție din Modulul 5 te introduce în lumea funcțiilor recursive.

Definiția lecției

Recursivitatea este tehnica prin care o funcție se apelează pe ea însăși pentru a rezolva o problemă prin descompunerea ei în subprobleme mai mici și asemănătoare. Orice funcție recursivă are două părți obligatorii: cazul de bază, care oprește apelurile, și pasul recursiv, care reduce problema. La fiecare apel, valorile parametrilor și adresa de revenire sunt impuse pe stiva apelurilor, o structură de tip LIFO. La întoarcerea din apeluri, ele sunt eliminate de pe stivă, în ordine inversă. Fără caz de bază, funcția se apelează la nesfârșit și stiva se umple, producând eroarea de depășire a stivei. Ordinea instrucțiunilor față de apelul recursiv schimbă rezultatul: afișarea dinaintea apelului se execută la coborâre, iar cea de după apel, la urcare pe stivă.

Definiții esențiale

Algoritmul cheie - pseudocod

Algoritm numara(n): dacă n == 0 atunci returnează altfel afișează n numara(n - 1)

Algoritmul cheie - cod C++

Program C++ - numărare descrescătoare recursivă
#include <iostream>
using namespace std;

void numara(int n)
{
    if (n == 0)
        return;
    cout << n << " ";
    numara(n - 1);
}

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

Greșeli comune de evitat

Exemplu practic

Scenariu real: vrei să afișezi numerele de la 10 la 1 înainte de startul unei curse, fără a folosi o buclă. Funcția numara(n) afișează valoarea lui n și se apelează cu n - 1 până la 0:

Program C++ - numărare descrescătoare (exemplu practic)
void numara(int n)
{
    if (n == 0)
        return;
    cout << n << " ";
    numara(n - 1);
}

Apelul numara(10) afișează 10 9 8 7 6 5 4 3 2 1.

Sfaturi practice și trucuri