Contact și feedback

Nu obții 100 de puncte sau ai nelămuriri în privința problemelor? Scrie-mi pe Instagram.


Ai găsit o greșeală, vrei să raportezi un utilizator sau vrei să comunici altceva? Folosește formularul de contact.


Vrei să ne transmiți o părere despre platformă? Folosește formularul de feedback.

Shortcuturi

Folosește următoarele shortcuturi pentru a naviga mai ușor pe platformă.

Generale

Meniu shortcuturi?
Căutare probleme sau utilizatori/
Navigare printre rezultatele căutării↑, ↓
Meniu de contact și feedbackCTRL + Shift + F
Ieșire din meniuriEsc

Editor probleme

Setări editorCTRL + Shift + S
Schimbare stil editorCTRL + Shift + E
Șabloane de codCTRL + Shift + 1/2/3
Golire editorCTRL + Shift + 4

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.

https://i.ibb.co/k4V2q3h/image.png

Î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:

https://i.ibb.co/bbg1J7N/image.png

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

https://i.ibb.co/zVVjSc8/image.png

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

https://i.ibb.co/XYg7PMN/image.png

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):

Variabilă / Expresie Valoare
factorial(4) ???4 * factorial(3)62424
factorial(3) ???3 * factorial(2)266
factorial(2) ???2 * factorial(1)122
factorial(1) ???1 * factorial(0)111
factorial(0) ???11

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:

Să se determine recursiv al n-lea termen tribonacci (elementul curent este egal cu suma ultimelor trei):

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

Să se afișeze crescător primele n numere naturale:

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

Alte resurse și bibliografie

Obține medalia mult dorită. Devino As la olimpiadă.

Curs complet de olimpiadă, pregătit de olimpici de la Oxford și TU Delft.

Cuprinsul lecției

Se încarcă…

Citește și

Comentarii în C++Prima cifră a unui număr în C++CMMDC recursiv a două numere naturale în C++Șiruri de caractere în C++. Tot ce trebuie să știiCăutare binară în C++Verificarea unui an bisect în C++Pointer în C++. Variabile de tipul char * (char steluță)Transformarea unui număr din baza 2 în baza 10 în C++Sortare crescătoare recursivă în C++ - Merge sort și Bubble sortInstrucțiunea break (structuri repetitive)Verifică dacă un număr este par sau impar fără modulo în C++Cifra maximă și minimă a unui număr în C++Materia pentru olimpiada de informatică - tot ce trebuie să știiTipul struct în C++. Ce sunt structurile de date neomogeneCitirea și afișarea matricelor în C++Maximul și minimul a două valori în C++Aria și circumferința unui cerc în C++Oglinditul recursiv al unui număr în C++Afișarea elementelor unui vector recursiv în C++Aplicații cu ciurul lui Eratostene în C++: suma divizorilor, numărul divizorilorInstrucțiunea do while (structuri repetitive)Maximul și minimul a n valori în C++Generarea șirului Fibonacci generalizat în C++Tipuri de date în C++: numere întregi, reale, caractere și alteleCâte numere naturale sunt într-un interval dat? (C++)Factorialul unui număr în C++Cifrele unui număr. Prelucrarea cifrelor unui număr în C++Tutorial instalare CodeBlocks (ușor) - Introducere în informatică C++Calculul combinărilor de n luate câte k (nCk) în C++Complexitatea unui algoritm (timp și spațiu) în C++Maximul și minimul unui vector în C++Oglinditul unui număr în C++Valoarea absolută (modulul) unui număr în C++Verifică dacă un număr aparține șirului Fibonacci în C++Numărul de divizori al numerelor de la 1 la N (Folosind ciurul lui Eratostene)Codul ASCII (tabel complet)Aflarea sumei primelor N sume GaussCifra maximă a unui număr recursiv în C++Rădăcina cubică a unui număr în C++ (cube root)Cel mai mic număr cu suma cifrelor N în C++Structuri repetitive (while, do while, for, etc)Funcții în C++. Ce sunt subprogrameleBordarea unei matrice în C++Divide et Impera (metodă de programare C++)Ciurul lui Eratostene în C++Aria unui triunghi folosind coordonatele acestora în C++Transformarea unui număr din baza 10 în baza 2 în C++Cum să citești și să afișezi în fișiere în C++Verificare dacă un număr este palindrom în C++Ce este o funcție void în C++?CMMMC a două numere în C++ (cel mai mic multiplu comun)Matrice în C++. Declararea și parcurgerea tablourilor bidimensionaleInversarea unui șir de caractere în C++Distanța dintre două puncte în C++Matrice Fibonacci - al n-lea termen Fibonacci în timp logaritmicVectorii în C++: declarare și parcurgereCe este o variabilă unsigned în C++?Matrice pătratice în C++. Diagonala principală și secundarăDo while vs while în C++ - Care e diferența?Verifică dacă o literă este vocală în C++Algoritm recursiv pentru căutare binară (clasa a X-a)Vectori de frecvență (de apariții) în C++Maximul și minimul a trei valori în C++Numărul minim de peroane pentru o gară în C++Indicatorul lui Euler în C++Cum să calculezi instant 2 la puterea N în C++Suma elementelor unui vector recursiv în C++Al N-lea termen Fibonacci în C++Ce înseamnă endl în C++?Verifică dacă un bit de pe o anumită poziție este 1 sau 0 în C++Numărul combinărilor în C++ (formula combinărilor)Interschimbarea a două variabile în C++ (3 metode)Șirul lui Fibonacci în C++Numărul de cifre ale factorialului unui numărInstrucțiunea while (structuri repetitive)Citește un șir de caractere cu spații în C++Funcții predefinite în C++ (matematice, șiruri de caractere)Verificare număr prim în C++ (Clasa a IX-a)Verifică dacă trei puncte sunt coliniare C++Recursivitate în C++Verifică dacă o literă este mică sau mare în C++De ce cer unele probleme răspunsul modulo 666013 sau modulo 1.000.000.007?Numărul aranjamentelor în C++ (formula aranjamentelor)Instrucțiunea continue (structuri repetitive)Radicalul unui număr în C++ (rădăcina pătrată)Cifra de control a unui numărNumărul permutărilor în C++ (formula permutărilor)Operații cu numere mari în C++ - Toate funcțiile explicateSuma divizorilor unui număr în C++Numere triunghiulare. Verificarea unui număr triunghiularRidicarea la putere în timp logaritmic în C++. Exponențiere rapidăCum să afișezi partea întreagă a unui număr real în C++Al N-lea termen dintr-o progresie aritmeticăCel mai mic/mare divizor prim al numerelor de la 1 la N (Folosind ciurul lui Eratostene)Transformarea unei litere mici în literă mare în C++Verifică dacă un număr dat este o putere de 2 în C++Combinatorică în C++: permutări, aranjamente, combinări și alteleCea mai lungă secvență de elemente crescătoare în C++Verifică dacă un caracter este literă în C++Suma divizorilor numerelor de la 1 la N (Folosind ciurul lui Eratostene)Află secolul unui an citit de la tastatură în C++Instrucțiunea de decizie în C++: if, else, switch, caseSuma numerelor naturale dintr-un interval dat în C++Inversarea unui vector în C++Transformarea unei litere mari în literă mică în C++Mediana unui șir de valori în C++Ce înseamnă variabilă globală și locală în C++?Verificare dacă șir de caractere este palindrom în C++Cel mai mare divizor comun (CMMDC) a două numere în C++Interclasarea a doi vectori în C++Cel mai semnificativ bit în C++Numărul de apariții al unui număr într-un vector în C++Indicatorul lui Euler al numerelor de la 1 la N (Folosind ciurul lui Eratostene)Verifică dacă un caracter este cifră în C++Cel mai frecvent element dintr-un șir în C++Instrucțiunea for (structuri repetitive)Suma 1 + 2 + 3 + ... + N în C++Cel mai puțin semnificativ bit în C++Afișarea divizorilor primi ai unui număr în C++Numărul de divizori al unui număr în C++Copiuțe: Cifrele unui numărNumărul de divizori primi ai unui număr în C++Al N-lea termen dintr-o progresie geometricăVectorii în C++: citire și afișare

© Drepturi de autor

Echipa InfoAs își rezervă drepturile de autor pentru conținutul acestei pagini. Copierea conținutului fără acordul scris expres al InfoAs reprezintă o încălcare a Legii 8/1996 și va fi tratată ca atare.

Trimite lecția

Toată lecția

Doar videoclipul pe YouTube

Informatica devine ușoară cu InfoAs

Intră în cont