Recursivitate în C++

Să ne gândim la un copac: acesta are ramuri, fiecare ramură având la rândul ei mai multe ramuri mai mici, și așa mai departe până la cele mai mici ramuri.

În matematică și în informatică întâlnim o noțiune similară, numită recursivitate (sau recurență), de a defini ceva cu ea însăși.

Vom folosi funcții în această lecție — altfel, nu am putea să folosim recursivitatea.

Definiția recursivității

Recursivitatea este proprietatea unui element de a se defini prin el însuși.

Exemple

Noțiunea de recursivitate poate părea destul de dificil de înțeles, așadar să considerăm câteva exemple.

Exemple în matematică

Factorialul unui număr n, n!, este egal cu produsul 1 × 2 × 3 × … × (n - 1) × n. Putem să rescriem factorialul astfel: n! = (n - 1)! × n. Astfel, am definit factorialul lui n pe baza factorialului lui n - 1.

Șirul Fibonacci este un șir cunoscut în matematică, cu primii doi termeni 1 și 1, iar termenul F(n) = F(n - 1) + F(n - 2).

Progresiile aritmetice și geometrice se pot scrie recursiv: a(n) = a(n - 1) + r, sau g(n) = g(n - 1) * r.

Exemple vizuale

Fractalii sunt un exemplu bun de recursivitate, în care nu există vreo limită de oprire (spre deosebire de șirul Fibonacci, spre exemplu, unde avem limita n = 1 sau n = 2). Iată un fractal în formă de pătrat, în care colțul din stânga sus este identic cu tot pătratul:

Un alt fractal — triunghiul Sierpinski. Triunghiul se împarte în 4 triunghiuri egale, iar în cele 3 din colțuri se repetă fractalul.

Un ultim exemplu este efectul Droste: un ambalaj care se conține pe el însuși:

Implementarea unei funcții recursive în C++

Să zicem că vrem să calculăm factorialul unui număr. Metoda clasică este următoarea:

#include <iostream>

using namespace std;

int factorial(int n) {
    int fact = 1;
    for(int i = 1; i <= n; i++) {
        fact *= i;
    }
    return fact;
}

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

Dacă am implementa recursiv soluția la această problemă, am crea o funcție care se definește pe ea însăși în apel:

#include <iostream>

using namespace std;

int factorial(int n) {
    if(n <= 0) { //Caz particular
        return 1;
    } else { //Formula generală
        return n * factorial(n - 1);
    }
}

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

Cum funcționează recursivitatea? (animație)

Iată o reprezentare pentru apelarea factorial(4):

Avantajele și dezavantajele recursivității

Avantaj: mod nou de gândire

Recursivitatea aduce o nouă metodă de a vizualiza problemele. Această metodă, de a împărți problema curentă în probleme mai mici, până când ajungem la probleme simple și rezolvabile instant, va fi mai târziu (în clasa a XI-a) folosită la programarea dinamică.

Avantaj: anumite probleme nu se pot implementa decât recursiv

Unele probleme sunt foarte greu — sau chiar imposibil — implementabile nerecursiv. În clasa a XI-a se vor folosi funcțiile recursive pentru backtracking.

Dezavantaj: programele sunt foarte încete

Soluțiile recursive, fără optimizări, pot lua mai mult timp să ruleze, astfel că implementările recursive nu sunt foarte utile în programe în care viteza este importantă. Cu toate acestea, de obicei acest lucru nu reprezintă un pericol.

Dezavantaj: multe funcții se pot implementa nerecursiv

După cum s-a observat și anterior, majoritatea noțiunilor pe care le putem implementa recursiv (Fibonacci, progresii aritmetice sau geometrice, factorialul, etc.) s-au implementat deja nerecursiv. Așadar, nu are sens să reinventăm roata.

Exerciții propuse

Completează următoarele secvențe de cod:

int tribo(int x) {
    if(x <= 3) {
        return 1;
    }
    ??? tribo(x - 1) + tribo(x - ???) + tribo(x - 3);
}

void f(int n) {
    if(n > 1) {
        ???(n - 1);
    }
    cout << ??? << " ";
}

Alte resurse și bibliografie

• programareliceu.wordpress.com
• PbInfo
• info.tm.edu.ro