Ce este recursivitatea?

Ce este recursivitatea?

Ce învățăm în această lecție

În această lecție învățăm ce este recursivitatea, cum funcționează, de ce este utilă și cum să o recunoști într-o problemă. Recursivitatea este una dintre ideile importante din informatică și apare frecvent la BAC în exerciții de la Subiectul 1 sau 2.

Ce trebuie să știi pentru BAC

La BAC, recursivitatea nu apare ca în facultate, cu explicații lungi sau programe mari. De obicei apar exerciții scurte în care trebuie să observi rapid:

• dacă funcția se apelează pe ea însăși
• care este cazul de oprire
• ce se întâmplă înainte de apelul recursiv
• ce se întâmplă după apelul recursiv
• ce valoare se întoarce sau ce se afișează

Notă: La BAC, recursivitatea se rezolvă mai ales prin urmărirea logicii funcției, nu prin memorarea unor definiții complicate.

Definiția simplă

O funcție este recursivă dacă se apelează pe ea însăși.

Asta înseamnă că funcția rezolvă problema cerută folosind aceeași idee, dar pentru un caz mai mic.

Cele 2 lucruri obligatorii

Orice funcție recursivă corectă are:

• caz de oprire
• apel recursiv

Fără caz de oprire, funcția ar continua la nesfârșit.

Cum arată ideea generală

tip f(parametru) {
    if (caz_de_baza) 
        return raspuns_simplu; //sau cout
    return ceva + f(parametru_mai_mic); //sau cout
}